Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let and be a -uniform hypergraph with chromatic number (that is, there is a -colouring of the vertices of such that no edge is monochromatic).
Suppose any two edges of have a non-empty intersection. Must contain many vertices? Must there be two edges which meet in many vertices?
Let and be a -uniform hypergraph with chromatic number (that is, there is a -colouring of the vertices of such that no edge is monochromatic, but no such -colouring), every vertex lying in an edge.
Suppose any two edges of have a non-empty intersection. Must contain many vertices? Must there be two edges which meet in many vertices?
Source: erdosproblems.com/836
No claim settles this problem.
Open on erdosproblems.com (label OPEN). The site credits a counterexample to the first question to Alon; the same construction gives the lower bound of Erdős and Lovász's Theorem 8, recorded on their claim page (Erdős and Lovász, 1975).
The site's parenthetical gloss says only that ; it does not express the preceding exact condition . Taken literally, the gloss makes both questions false: arbitrarily large stars are intersecting and -colorable, and every two of their edges meet in exactly one vertex. The site's commentary on Alon's counterexample states that "its chromatic number is 3", and Erdős and Lovász [ErLo75, Theorem 8 p. 613, construction (b) p. 620] work with exact chromatic number and count only points lying in edges. The corrected Statement adds the missing "no such -colouring" and the convention that every vertex lies in an edge; if isolated vertices were allowed, adjoining isolates would trivially falsify the first question even under the exact chromatic-number hypothesis.