The Regularity Method for Sparse Graphs and Hypergraphs


The Regularity Lemma of E. Szemeredi for graphs asserts that every dense graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type. This observation is called Counting Lemma. The interplay of Szemeredi's Regularity Lemma and the Counting Lemma has had a series of successes in Discrete Mathematics. In recent years the Regularity Method was partly expanded to new types of discrete structures: sparse graphs and k-uniform hypergraphs. In particular, analogues of the Regularity Lemma for these combinatorial objects were established. In the proposed program, we seek a deeper understanding of the random-like behavior guaranteed by those Regularity Lemmas. Furthermore, we focus on applications of these novel techniques in the area of extremal combinatorics.


Projektleitung
Schacht, Mathias Prof. Ph. D. (Details) (Algorithmen und Komplexität I)

Laufzeit
Projektstart: 02/2005
Projektende: 01/2007

Publikationen

The hypergraph regularity method and its applications, Proceedings of the National Academy of Sciences USA, 102(23): 8109-8113 (with Vojtech Rödl, Brendan Nagle, Jozef Skokan, and Yoshiharu Kohayakawa).



Density theorems and extremal hypergraph problems, Israel Journal of Mathematics, 152: 371-380 (with Vojtech Rödl, Eduardo Tengan, and Norihide Tokushige).



Extremal hypergraph problems and the regularity method. In: M. Klazar, J. Kratochvil, Martin Loebl, J. Matousek, Robin Thomas, and Pavel Valtr (editor): Topics in Discrete Mathematics, volume 26 of series Algorithms Combin., pages 247-278. Springer, Berlin (with Brendan Nagle and Vojtech Rödl).



The counting lemma for regular k-uniform hypergraphs, Random Structures and Algorithms, 28(2): 113-179 (with Brendan Nagle and Vojtech Rödl).



On six problems posed by Jarik Nesetril. In: M. Klazar, J. Kratochvil, Martin Loebl, J. Matousek, Robin Thomas, and Pavel Valtr (editor): Topics in Discrete Mathematics, volume 26 of series Algorithms Combin., pages 613-627. Springer, Berlin (with Jørgen Bang-Jensen, Bruce Reed, Robert Sámal, Bjarne Toft, and Uli Wagner).



Turán's theorem for pseudo-random graphs, Journal of Combinatorial Theory (A). to appear (with Yoshiharu Kohayakawa, Vojtech Rödl, Papa Sissokho, and Jozef Skokan).



Note on the 3-graph counting lemma, Discrete Mathematics. to appear (with Brendan Nagle and Vojtech Rödl).



Regular partitions of hypergraphs, Combinatorics, Probability and Computing. to appear (with Vojtech Rödl).



Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory (B). to appear (with Vojtech Rödl, Mark Siggers, and Norihide Tokushige).


Zuletzt aktualisiert 2020-09-03 um 23:05