Skip to content

Erdős Problem #836

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, hypergraphs, chromatic number.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Pairwise-intersecting hypergraphs requiring three vertex colors can have exponentially many vertices, refuting the hoped-for quadratic vertex bound. A different overlap question asks whether two edges must intersect in a fixed positive fraction of their lengths and remains open.

Let \(G\) be a hypergraph of uniformity \(r\) with vertex chromatic number 3 and any two distinct edges intersect. Two questions: must the number of vertices be \(O(r^2)\)? NO; must some pair of edges intersect in \(\Omega(r)\) vertices? OPEN. Require all vertices of G to be incident to an edge when interpreting vertex bound; arbitrary isolated vertices already make literal first question false.

A small example

At \(r=3\), take \(X=\{0,1,2,3\}\); \(Y\) has three partition vertices, for seven vertices in total. There are four 3-subsets of X and six triples consisting of two vertices from \(X\) and one from \(Y\), ten edges. Every pair of edges intersects; exhaustive 2-colorability fails, and a 3-coloring exists. This finite fixture validates combinatorial definition, not exponential asymptotic alone.

This finite calculation is not an asymptotic or all-parameter proof.

What is known

Maintained /latex/836 read 2026-10-14. Erdős–Lovász [ErLo75] show a pair of edges intersects in at least \(\Omega(r/\log r)\) vertices, weaker than the target of \(\Omega(r)\) vertices. In Alon's construction, \(X\) has \(2r-2\) vertices and \(Y\) has one vertex for each unordered balanced bipartition of \(X\) into sets of size \(r-1\), giving \(|Y|=\tfrac12\binom{2r-2}{r-1}\). Hyperedges comprise all subsets of size \(r\) of \(X\) and one subset of size \(r-1\) plus its associated \(Y\) vertex for every bipartition class. It is intersecting, non-2-colorable but 3-colorable, and \(|V|\sim 4^r/\sqrt r\). The \(r=3\) finite construction has been independently checked using all ten explicit hyperedges, verifying pairwise intersections and the absence of a proper two-colouring. The infinite-r theorem remains attributed to Alon, not certified afresh by that fixture.

Alon's construction has a part \(X\) with \(2r-2\) vertices and a part \(Y\) indexing unordered balanced bipartitions of \(X\). Therefore

\[ |V|=2r-2+\frac12\binom{2r-2}{r-1}. \]

The binomial coefficient grows exponentially, so this grows faster than \(O(r^2)\). Hyperedges consist of all subsets of \(X\) of size \(r\), plus a subset of \(X\) of size \(r-1\) with its associated vertex from \(Y\). These edges intersect pairwise and the hypergraph requires three colors. It does not settle whether two edges must intersect in \(\Omega(r)\) vertices.

GCL's current state

The authenticated source return has disposition STATUS_CONFLICT. This is an editorially reviewed explanatory article under protected batch EC-BULK-005-R5; its original STATUS_CONFLICT source remains preserved. Published results remain attributed to their authors; original source conflicts and independent full-proof-review limits are not silently cleared by publishing the manuscript.

What remains

Build the \(r=3\) Alon construction, verify pairwise intersecting and 3-chromatic by brute force. Prove count for Y and asymptotic growth; keep the second \(\Omega(r)\) overlap question open.

The original primary mathematical proofs, quantified status, finite definitions and deployed rendering must be independently checked before protected admission. No such admission is claimed here.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2107 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction