Erdős Problem #836 — Large intersections in 3-chromatic intersecting hypergraphs
Let be an integer, and let be a finite -uniform hypergraph: is a family of -element subsets of , and, as in the set-family convention, . Assume that is intersecting, so for all distinct , and has chromatic number exactly . Here a coloring is proper if no edge is monochromatic; chromatic number exactly means that a proper coloring with three colors exists but no proper coloring with two colors exists. The exact questions are whether there is an absolute constant such that every such satisfies
and whether there is an absolute constant such that, for all sufficiently large , every such has two distinct edges with
Erdős–Lovász (1975) LargeEdgeIntersection
Background
Erdős and Lovász studied finite uniform hypergraphs whose edges pairwise intersect, calling these hypergraphs cliques, and focused on those with chromatic number . Their work connects a global coloring obstruction—failure of two colors to color every edge properly—with restrictions on the number of vertices and on how closely edges can intersect. The Fano plane supplies a basic example: its lines form a -uniform intersecting hypergraph of chromatic number , with pairwise intersections of size . Erdős and Lovász also described constructions in uniformities with maximum pairwise intersection , obtained by iterating a product construction from the Fano plane. Erdős–Lovász (1975) LargeEdgeIntersection
The wording “there is a 3-colouring” alone does not specify chromatic number exactly : it also permits hypergraphs colorable with fewer colors. The questions concern the exactly -chromatic case, as in the classical results. The asymptotic formulations above make explicit that and ask for constants independent of both and the hypergraph. Erdős–Lovász (1975) LargeEdgeIntersection
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.