Erdős Problem #719
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, hypergraphs.
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
For \(r\ge2\), define the extremal function
It is the maximum number of r-edges in an n-vertex r-uniform hypergraph containing no complete \(K_{r+1}^r\). Erdős–Sauer ask whether EVERY n-vertex r-uniform hypergraph G can be covered by at most \(t_r(n)\) copies of \(K_r^r\) (single r-edges) and \(K_{r+1}^r\) (complete (r+1)-vertex cliques), with no two chosen copies sharing an r-edge. This is OPEN. 'No sharing an r-edge' is an edge-disjoint packing condition, not merely different vertex sets.
A small example
For r=2, \(G=K_4\) has six edges. One triangle covers three edges and the other three edges become singleton \(K_2\) copies: four pieces, equal to \(\mathrm{ex}(4,K_3)=4\). For \(G=K_5\), two edge-disjoint triangles (e.g. on {1,2,3} and {1,4,5}) cover six edges and the four remaining edges give six pieces, equal to \(\mathrm{ex}(5,K_3)=6\). These are finite certificates, not a general packing theorem.
What is known
If G has e r-edges and we choose t pairwise r-edge-disjoint copies of \(K_{r+1}^r\), each replaces r+1 singleton edge pieces by ONE block. The total number of pieces is \(e-rt\). Therefore the requested decomposition is equivalent (for the chosen G) to finding at least \(\lceil(e-t_r(n))/r\rceil\) edge-disjoint complete (r+1)-vertex r-hypergraphs whenever \(e>t_r(n)\). This reduction is elementary and source-faithful; the existence of such a packing is the hard point. The maintained Erdős #719 still says OPEN, a conjecture of Erdős and Sauer. No original 1981 paper pages or exact recent upstream formal statement was independently inspected, and no file is in the GCL-pinned FC provider.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: open hypergraph decomposition; packing reduction not full proof. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
ERDOS-719-EDGE_DISJOINT_CLIQUE_PACKING. For r=2 or 3 and n≤6 enumerate hypergraphs, compute maximum packing and compare \(e-rt\) against the extremal bound \(t_r(n)\) defined above. Acceptance: exact finite certificate plus a formal equivalence lemma connecting the decomposition count to a clique packing, not a claim of the arbitrary-n result.
Sources and claim boundaries
Maintained Erdős Problem #719; authenticated issue audit. Full original proof text and branch-protected formal dependencies not independently replayed. no new independent primary theorem certification, browser MathJax review or V2 admission.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1990 — 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.