Embeddings and Ramsey numbers of sparse <Emphasis Type="Italic">κ</Emphasis>-uniform hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [3] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [6,23] the same result was proved for 3-uniform hypergraphs. Here we extend this result to κ-uniform hypergraphs for any integer κ ≥ 3. As in the 3-uniform case, the main new tool which we prove and use is an embedding lemma for κ-uniform hypergraphs of bounded maximum degree into suitable κ-uniform ‘quasi-random’ hypergraphs.     

On the Ramsey Number of Sparse 3-Graphs

We consider a hypergraph generalization of a conjecture of Burr and Erd?s concerning the Ramsey number of graphs with bounded degree. It was shown by Chvátal, Rödl, Trotter, and Szemerédi [The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), no. 3, 239–243] that the Ramsey number R(G) of a graph G of bounded maximum degree is linear in |V(G)|. We derive the analogous result for 3-uniform hypergraphs.     

Linear Ramsey Numbers for Bounded-Degree Hypergrahps

We show that the Ramsey number is linear for every uniform hypergraph with bounded degree. This is a hypergraph extension of the famous theorem for ordinary graphs which Chvátal et al. [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), pp. 239–243] showed in 1983. Our proof demonstrates the potential of a new regularity lemma by [Y. Ishigami, A simple regularization of hypergraphs, preprint, arXiv:math/0612838 (2006)].     

A rainbow blow‐up lemma

We prove a rainbow version of the blow‐up lemma of Komlós, Sárközy, and Szemerédi for μn‐bounded edge colorings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow‐up lemma can be used to transfer the bandwidth theorem of Böttcher, Schacht, and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of μn‐bounded edge colorings. Kim, Kühn, Kupavskii, and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow‐up lemma given by Rödl and Ruciński, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

On a conjecture of Thomassen concerning subgraphs of large girth

In 1983 C. Thomassen conjectured that for every k, g∈? there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. Kühn and Osthus [2004] proved the case g = 6. We give another proof for the case g = 6 which is based on a result of Füredi [1983] about hypergraphs. We also show that the analogous conjecture for directed graphs is true. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:316‐331,2011     

Perfect matchings in uniform hypergraphs with large minimum degree

A perfect matching in a k-uniform hypergraph on n vertices, n divisible by k, is a set of n/k disjoint edges. In this paper we give a sufficient condition for the existence of a perfect matching in terms of a variant of the minimum degree. We prove that for every k≥3 and sufficiently large n, a perfect matching exists in every n-vertex k-uniform hypergraph in which each set of k−1 vertices is contained in n/2+Ω(logn) edges. Owing to a construction in [D. Kühn, D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (1) (2006) 269–280], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to n/k rather than n/2.     

Regularity lemmas for hypergraphs and quasi-randomness

We give a simple proof for Szemerédi's Regularity Lemma and its generalization for k-uniform hypergraphs. For fixed k, there are altogether k -1 different versions of the regularity lemma for k-uniform hypergraphs. The connection between regularity lemmas for hypergraphs and quasi-random classes of hypergraphs is also investigated.     

On two problems in graph Ramsey theory

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K _N contains a monochromatic copy of H. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c′ such that $2^{c'\Delta } \leqslant c(\Delta ) \leqslant ^{c\Delta \log ^2 \Delta }$ . We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2 ^cΔlogΔ . The induced Ramsey number r _ind (H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd?s conjectured the existence of a constant c such that, for any graph H on n vertices, r _ind (H) ≤ 2 ^cnlogn . We move a step closer to proving this conjecture, showing that r _ind (H) ≤ 2 ^cnlogn . This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent.     

Partition properties of q-hypergraphs

A q-analogue to a partition theorem for finite hypergraphs of Nes̆etr̆il and Rödl [J. Combin. Theory Ser. A 22 (1977), 289–312 and 34 (1983), 183–201] is proven. This generalizes the vector space Ramsey theorem of Graham, Leeb, and Rothschild [Advan. in Math. 8 (1972), 417–433].     

Induced Ramsey-type theorems

We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rödl, Łuczak-Rödl, Prömel-Rödl, Erdős-Hajnal, and Nikiforov. The proofs are based on a simple lemma (generalizing one by Graham, Rödl, and Ruciński) that can be used as a replacement for Szemerédi's regularity lemma, thereby giving much better bounds. The same approach can be also used to show that pseudo-random graphs have strong induced Ramsey properties. This leads to explicit constructions for upper bounds on various induced Ramsey numbers.     

Loose Hamilton cycles in hypergraphs

We prove that any k-uniform hypergraph on n vertices with minimum degree at least contains a loose Hamilton cycle. The proof strategy is similar to that used by Kühn and Osthus for the 3-uniform case. Though some additional difficulties arise in the k-uniform case, our argument here is considerably simplified by applying the recent hypergraph blow-up lemma of Keevash.     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Density theorems and extremal hypergraph problems

We present alternative proofs of density versions of some combinatorial partition theorems originally obtained by E. Szemerédi, H. Furstenberg and Y. Katznelson. These proofs are based on an extremal hypergraph result which was recently obtained independently by W. T. Gowers and B. Nagle, V. Rödl, M. Schacht, J. Skokan by extending Szemerédi’s regularity lemma to hypergraphs.     

A variant of the hypergraph removal lemma

Recent work of Gowers [T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299-345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275-291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes.     

Monochromatic tree covers and Ramsey numbers for set-coloured graphs

We consider a generalisation of the classical Ramsey theory setting to a setting where each of the edges of the underlying host graph is coloured with a set of colours (instead of just one colour). We give bounds for monochromatic tree covers in this setting, both for an underlying complete graph, and an underlying complete bipartite graph. We also discuss a generalisation of Ramsey numbers to our setting and propose some other new directions.Our results for tree covers in complete graphs imply that a stronger version of Ryser’s conjecture holds for $k$-intersecting $r$-partite $r$-uniform hypergraphs: they have a transversal of size at most $r?k$. (Similar results have been obtained by Király et al., see below.) However, we also show that the bound $r?k$ is not best possible in general.     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

A hypergraph blow‐up lemma

We obtain a hypergraph generalisation of the graph blow‐up lemma proved by Komlós, Sarközy and Szemerédi, showing that hypergraphs with sufficient regularity and no atypical vertices behave as if they were complete for the purpose of embedding bounded degree hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 39, 275–376, 2011