We study Ramsey properties of randomly perturbed $3$-uniform hypergraphs. For~$t\geq 2$, write $\tilde K^{(3)}_t$ to denote the $3$-uniform {\it expanded} clique hypergraph obtained from the complete graph $K_t$ by expanding each of the edges of the latter with a new additional vertex. For an even integer $t\geq 4$, let~$M$ denote the asymmetric maximal density of the pair $(\tilde K^{(3)}_t,\tilde K^{(3)}_{t/2})$. We prove that adding a set~$F$ of random hyperedges satisfying $|F|\gg n^{3-1/M}$ to a given $n$-vertex $3$-uniform hypergraph~$H$ with non-vanishing edge density asymptotically almost surely results in a perturbed hypergraph enjoying the Ramsey property for $\tilde K^{(3)}_t$ and two colours. We conjecture that this result is asymptotically best possible with respect to the size of $F$ whenever $t\geq 6$ is even. The key tools of our proof are a new variant of the hypergraph regularity lemma accompanied with a \emph{tuple lemma} providing appropriate control over joint link graphs. Our variant combines the so called strong and the weak hypergraph regularity lemmata.

Rödl and Ruciński [Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995)] established Ramsey's theorem for random graphs. In particular, for fixed integers r and ℓ ≥ 2 they showed that ˆpkℓ,r(n) = n-2/ℓ+1 is a threshold for the Ramsey property that every r-colouring of the edges of the binomial random graph G(n,p) yields a monochromatic copy of Kℓ. We investigate how this result extends to arbitrary colourings of G(n,p) with an unbounded number of colours. In this situation, Erdős and Rado [A combinatorial theorem, J. London Math. Soc. 25 (1950)] showed that canonically coloured copies of Kℓ can be ensured in the deterministic setting. We transfer the Erdős-Rado theorem to the random environment and show that both thresholds coincide when ℓ ≥ 4. As a consequence, the proof yields Kℓ+1-free graphs G for which every edge colouring contains a canonically coloured Kℓ. The 0-statement of the threshold is a direct consequence of the corresponding statement of the Rödl-Ruciński theorem and the main contribution is the 1-statement. The proof of the 1-statement employs the transference principle of Conlon and Gowers [Combinatorial theorems in sparse random sets, Ann. of Math. (2) 184 (2016)].

We study sufficient conditions for the existence of Hamilton cycles in uniformly dense 3-uniform hypergraphs. Problems of this type were first considered by Lenz, Mubayi, and Mycroft for loose Hamilton cycles, and Aigner-Horev and Levy considered them for tight Hamilton cycles for a fairly strong notion of uniformly dense hypergraphs. We focus on tight cycles and obtain optimal results for a weaker notion of uniformly dense hypergraphs. We show that if an $n$-vertex 3-uniform hypergraph $H=(V,E)$ has the property that for any set of vertices $X$ and for any collection $P$ of pairs of vertices, the number of hyperedges composed by a pair belonging to $P$ and one vertex from $X$ is at least $(1/4+o(1))|X||P| - o(|V|^3)$ and $H$ has minimum vertex degree at least $\Omega(|V|^2)$, then $H$ contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context.

We show that 3-uniform hypergraphs with the property that all vertices have a quasirandom link graph with density bigger than 1/3 contain a clique on five vertices. This result is asymptotically best possible.

We prove that for all $k\geq 4$ and $1\leq\ell

Szemerédi's Regularity Lemma [22, 23] is a powerful tool in graph theory. It asserts that all large graphs G admit a bounded partition of E(G), most classes of which are bipartite subgraphs with uniformly distributed edges. The original proof of this result was non-constructive. A constructive proof was given by Alon, Duke, Lefmann, Rödl and Yuster [1], which allows one to efficiently construct a regular partition for any large graph. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl [3] gave one such extension to 3-uniform hypergraphs, and Rödl and Skokan [19] extended this result to k-uniform hypergraphs. W.T. Gowers [4, 5] gave another such extension. Similarly to the graph case, all of these proofs are non-constructive. We present an efficient algorithmic version of the Hypergraph Regularity Lemma for k-uniform hypergraphs.

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”

Let $s

Thomason and Chung, Graham, and Wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a deterministic sense. Their concepts of quasi-randomness match the notion of ∊-regularity from the earlier Szemerédi regularity lemma. In contrast, there exists no “natural” hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors. We study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of Frankl and Rödl, Gowers and Haxell, Nagle and Rödl. We establish an equivalence among the three notions of regularity of these lemmas. Since the regularity lemma of Haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of Frankl–Rödl (a special case thereof) and Gowers as corollaries. As a further corollary, we obtain that the special case of the Frankl–Rödl lemma (which we can make algorithmic) admits a corresponding counting lemma. (This corollary follows by the equivalences and that the regularity lemma of Gowers or that of Haxell et al. admits a counting lemma.)

The hypergraph of the Fano plane is the unique 3-uniform hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. This hypergraph is not 2-colorable, but becomes so on deleting any hyperedge from it. We show that taking uniformly at random a labeled 3-uniform hypergraph H on n vertices not containing the hypergraph of the Fano plane, H turns out to be 2-colorable with probability at least 1 – 2−Ω(n2). For the proof of this result we will study structural properties of Fano-free hypergraphs.

We study sufficient $\ell$-degree ($1\leq\ell

Property testers are efficient, randomized algorithms which recognize if an input graph (or other combinatorial structure) satisfies a given property or if it is "far" from exhibiting it.Generalizing several earlier results, Alon and Shapira showed thathereditary graph properties are testable (with one-sided error). In this paper we prove the analogous result for hypergraphs.This result is an immediate consequence of a (hyper)graph theoretic statement, which is an extension of the so-called removal lemma. The proof of this generalization relies on the regularity method for hypergraphs.

Recently Alon and Shapira [Every monotone graph property is testable, New York, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, ACM Press, 2005, pp. 128–137] have established that every monotone graph property is testable. They raised the question whether their results can be extended to hypergraphs. The aim of this paper is to address this problem. Based on the recent regularity lemma of Rödl and Schacht [Regular partitions of hypergraphs, Combin. Probab. Comput., to appear], we prove that any monotone property of 3‐uniform hypergraphs is testable answering in part the question of Alon and Shapira. Our approach is similar to the one developed by Alon and Shapira for graphs. We believe that based on the general version of the hypergraph regularity lemma the proof presented in this article extends to k‐uniform hypergraphs.

We investigate the threshold probability for the property that every r-coloring of the edges of a random binomial k-uniform hypergraph ${\mathbb G }^{(k)}(n,p)$ yields a monochromatic copy of some fixed hypergraph G. In this paper we solve the problem for arbitrary $k\geq 3$ and k-partite, k-uniform hypergraphs G.