Intersecting $r$-uniform hypergraphs of chromatic number 3: must two edges share $\gg r$ vertices? (Erdős #836)
Statement
Let $r\geq 2$ and let $G$ be an $r$-uniform hypergraph with chromatic number $3$ (that is, the vertices of $G$ can be $3$-coloured so that no edge is monochromatic, but cannot be so $2$-coloured). Suppose any two edges of $G$ have a non-empty intersection. Must $G$ contain $O(r^2)$ many vertices? Must there be two edges which meet in $\gg r$ many vertices (i.e. in at least $cr$ vertices for some absolute constant $c>0$)?
Acceptance. FULLY RESOLVES (second question, the open one): a proof that every intersecting $r$-uniform hypergraph of chromatic number $3$ contains two edges meeting in at least $cr$ vertices for an explicit constant $c>0$; OR a refutation — a family of such hypergraphs (one for each $r$ in an infinite set) whose maximum pairwise edge-intersection is $o(r)$, with complete proofs that each member is intersecting, has chromatic number exactly $3$, and satisfies the intersection bound; explicit finite members must come with machine-checkable certificates (colouring witness plus verified non-2-colourability, e.g. by SAT/UNSAT certificate). Machine-checkable (Lean) proofs preferred for the asymptotic claims. ADVANCES: a proof strictly improving the Erdős–Lovász $\gg r/\log r$ bound stated in the background; progress on the Fano sub-question — a new example with no two edges meeting in $r-1$ vertices (with machine-checkable certificates), or a proof that none exists for a stated range of $r$ (exhaustive-search code plus certificate acceptable for finite ranges); or exact determination for small $r$ of the minimum possible maximum pairwise edge-intersection, with code and exhaustiveness certificate. Deliver the proof file, or the construction plus certificates, or the search code plus certificate and attained results.
Background
A problem of Erdős and Shelah [Er74d]; listed as open on erdosproblems.com/836 (fetched 2026-07-13, status 'open', tagged 'graph theory | hypergraphs | chromatic number'; note the page's activity widget reports partial-result claims in its 3 forum comments not yet incorporated into the remarks). Known frontier: Erdős and Lovász [ErLo75] proved that two edges must meet in $\gg r/\log r$ vertices, so the second question asks to close a $\log r$ gap. The first question — whether such a hypergraph must have $O(r^2)$ vertices — is answered in the NEGATIVE by a construction of Alon recorded on the page: take vertex sets $X$ and $Y$ with $|X|=2r-2$ and $|Y|=\frac{1}{2}\binom{2r-2}{r-1}$, the elements of $Y$ indexing the partitions of $X$ into two equal halves; the edges are all $r$-subsets of $X$, together with every set formed by an $(r-1)$-subset of $X$ plus the element of $Y$ corresponding to the induced partition. This hypergraph is intersecting, has chromatic number $3$, and has $\asymp 4^r/\sqrt{r}$ vertices — so the second question is the live one. A further sub-question from the page: the Fano plane gives an example (at $r=3$) in which no two edges meet in $r-1$ vertices — are there any other examples? Related in spirit to the venue problem on $m(5)$ (fewest edges in a non-2-colourable 5-uniform hypergraph, Erdős #901), which comes from the same Erdős–Lovász circle of problems on hypergraph colouring. The attacker's tool: extremal set-system arguments sharpening the Erdős–Lovász $r/\log r$ bound, and SAT/ILP-assisted exhaustive search over small-$r$ intersecting $r$-uniform hypergraphs of chromatic number 3 to map extremal pairwise edge-intersections and hunt for non-Fano examples.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #836 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.