The uniformity lemma for hypergraphs

DOI10.1007/BF02351586MaRDI QIDQ1205340zbMATH OpenOpenAlexWikidataFDO

Authors Vojtěch Rödl, Peter Frankl

Publication date 1 April 1993

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02351586

zbMATH Keywords

hypergraphsSzemerédi's theoremuniformity lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Review text

This is an extension of Szemerédi's theorem called the Uniformity Lemma for Graphs (see \textit{E. Szemerédi} [Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 399-401 (1978; Zbl 0413.05055)]) to \(r\)-uniform hypergraphs. Two applications of the result are announced: proof of a conjecture of Erdős concerning Turán-type problem, and giving an alternative condition for quasirandomness.

Recommendations

• Regularity Lemma for k-uniform hypergraphs
• The counting lemma for regular k‐uniform hypergraphs
• Regularity lemmas for hypergraphs and quasi-randomness
• Applications of the regularity lemma for uniform hypergraphs
• On Ramsey - Turan type theorems for hypergraphs

Cites work

• Exact solution of some Turán-type problems
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

Cited in

(40)

• A Tverberg-type result on multicolored simplices
• An Erdős-Gallai type theorem for uniform hypergraphs
• On the irregularity of uniform hypergraphs
• Uniform edge distribution in hypergraphs is hereditary
• The Erdős matching conjecture and concentration inequalities
• Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
• The 3-colour Ramsey number of a 3-uniform Berge cycle
• Weak quasi-randomness for uniform hypergraphs
• Counting in hypergraphs via regularity inheritance
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• A Folkman linear family
• On colourings of hypergraphs without monochromatic Fano planes
• On vertex independence number of uniform hypergraphs
• Extremal problems on set systems
• On a generalisation of Mantel’s Theorem to Uniformly Dense Hypergraphs
• Counting subgraphs in quasi‐random 4‐uniform hypergraphs
• On characterizing hypergraph regularity
• Regularity Lemma for k-uniform hypergraphs
• Rainbow Erdös-Rothschild problem for the Fano plane
• On the Hamiltonicity of triple systems with high minimum degree
• Loose Hamiltonian cycles forced by large (k-2)-degree-approximate version
• Constructive packings by linear hypergraphs
• Eigenvalues and linear quasirandom hypergraphs
• Quasirandomness in hypergraphs
• Linear quasi-randomness of subsets of abelian groups and hypergraphs
• Partitioning problems in dense hypergraphs
• Hypergraph regularity and random sampling
• On the irregularity of uniform hypergraphs
• Some Cubic Time Regularity Algorithms for Triple Systems
• Embedding loose spanning trees in 3-uniform hypergraphs
• Quasi-random Boolean functions
• A pair degree condition for Hamiltonian cycles in 3-uniform hypergraphs
• A tower lower bound for the degree relaxation of the regularity lemma
• A characterization of testable hypergraph properties
• Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs
• The Ramsey number for hypergraph cycles. I.
• A variant of the hypergraph removal lemma
• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
• Weak hypergraph regularity and linear hypergraphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs

This page was built for publication: The uniformity lemma for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1205340)