The intersection spectrum of 3‐chromatic intersecting hypergraphs

DOI10.1112/PLMS.12436MaRDI QIDQ6051524zbMATH OpenOpenAlexFDO

Authors Matija Bucić, Stefan Glock, Benny Sudakov

Publication date 20 September 2023

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/2010.00495

zbMATH Keywords

density increment approachErdős-Lovász conjectureRamsey-type arguments

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Extremal set theory (05D05) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: For a hypergraph $H$, define its intersection spectrum $I(H)$ as the set of all intersection sizes $|EcapF|$ of distinct edges $E,FinE(H)$. In their seminal paper from 1973 which introduced the local lemma, ErdH{o}s and Lov'asz asked: how large must the intersection spectrum of a $k$-uniform $3$-chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with $k$. Despite the problem being reiterated several times over the years by ErdH{o}s and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the ErdH{o}s-Lov'asz conjecture in a strong form by showing that there are at least $k^{1/2-o(1)}$ intersection sizes. Our proof consists of a delicate interplay between Ramsey type arguments and a density increment approach.

Recommendations

• On the degree, size, and chromatic index of a uniform hypergraph
• The Erdős-Faber-Lovász conjecture for dense hypergraphs
• Adding evidence to the Erdős-Faber-Lovász conjecture
• On the Erdős-Hajnal problem for 3-uniform hypergraphs
• Coloring 2-intersecting hypergraphs

Cites work

• A few remarks on Ramsey--Turán-type problems
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• A note on random greedy coloring of uniform hypergraphs
• Coloring n-sets red and blue
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász
• Dependent random choice
• Ein kombinatorisches Problem von P. Erdős und A. Hajnal
• Extremal problems in hypergraph colourings
• Greedy colorings of uniform hypergraphs
• scientific article; zbMATH DE number 3754700 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1317271 (Why is no real title available?)
• scientific article; zbMATH DE number 736294 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 3414305 (Why is no real title available?)
• scientific article; zbMATH DE number 3188524 (Why is no real title available?)
• Improved bounds and algorithms for hypergraph 2-coloring
• Invitation to intersection problems for finite sets
• On 3-chromatic hypergraphs
• On a Combinatorial Problem of Erdös and Hajnal
• On a combinatorial problem of P. Erdős and L. Lovasz
• On a combinatorial problem. II
• On a problem of Erdős and Lovász: Random lines in a projective plane
• On a Problem of Erdos and Lovasz. II: n(r) = O(r)
• On a property of families of sets
• On graphs with small Ramsey numbers
• On the construction of 3-chromatic hypergraphs with few edges
• Problems and results in discrete mathematics
• The probabilistic method

Cited in

(1)

• The chromatic spectrum of 3-uniform bi-hypergraphs

This page was built for publication: The intersection spectrum of 3‐chromatic intersecting hypergraphs

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