← All problems

Erdős Problem #836 — Large intersections in 3-chromatic intersecting hypergraphs

50 years old · documented by

Let r≥2r\ge 2 be an integer, and let G=(V,E)G=(V,E) be a finite rr-uniform hypergraph: EE is a family of rr-element subsets of VV, and, as in the set-family convention, V=⋃e∈EeV=\bigcup_{e\in E}e. Assume that GG is intersecting, so e∩f≠∅e\cap f\ne\varnothing for all distinct e,f∈Ee,f\in E, and has chromatic number exactly 33. Here a coloring is proper if no edge is monochromatic; chromatic number exactly 33 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 CC such that every such GG satisfies

∣V∣≤Cr2,|V|\le C r^2,

and whether there is an absolute constant c>0c>0 such that, for all sufficiently large rr, every such GG has two distinct edges e,f∈Ee,f\in E with

∣e∩f∣≥cr.|e\cap f|\ge cr.

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 33. 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 33-uniform intersecting hypergraph of chromatic number 33, with pairwise intersections of size 1=r−21=r-2. Erdős and Lovász also described constructions in uniformities r=3kr=3^k with maximum pairwise intersection r−2r-2, 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 33: it also permits hypergraphs colorable with fewer colors. The questions concern the exactly 33-chromatic case, as in the classical results. The asymptotic formulations above make explicit that O(r2)O(r^2) and ≫r\gg r ask for constants independent of both rr and the hypergraph. Erdős–Lovász (1975) LargeEdgeIntersection

References

Progress summary

Never refreshed

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.