Erdős Problem #747
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: combinatorics, 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
Take a uniformly random three-uniform hypergraph on 3n labelled vertices with exactly ℓ(n) distinct triple edges. What number of random edges makes it have a perfect matching (n pairwise vertex-disjoint triples covering all 3n vertices) with probability tending to one? Shamir's problem, Erdős #747, is SOLVED in threshold scale: \(\ell(n)\sim n\log n\) by Kahn's 2023 sharp result, after Johansson–Kahn–Vu 2008 determined the \(\Theta(n\log n)\) order. 'Almost surely' refers to n→∞ and a random edge sample, not every hypergraph with that many edges.
A small example
With n=2 there are six vertices and a perfect matching is any partition into two disjoint triples. Choosing {1,2,3} and {4,5,6} succeeds, and there are \(\binom{6}{3}\)/2=10 distinct perfect matchings. Two triples sharing a vertex cannot form a perfect matching. This exact finite combinatorial fixture does not establish an asymptotic probability threshold.
What is known
A necessary obstruction is an isolated vertex: a perfect matching covers every vertex. A random edge contains a given vertex with probability 3/(3n)=1/n, so after ℓ independently sampled edges a vertex is isolated with probability approximately \(\exp(-\ell/n)\); expected isolated count about \(3n\exp(-\ell/n)\). This predicts transition near n log n but is only a heuristic until dependence and remaining matching obstructions are controlled. Johansson–Kahn–Vu [JKV08] proves threshold order, and Kahn [Ka23] proves sharp \(\ell(n)\sim n\log n\) (also general uniformity). Full author proofs not independently replayed in GCL.
GCL's current state
The authenticated original source return remains in its original BOUNDED_TASK_DESIGNED state. This is an editorially reviewed explanatory article in protected EC-BULK-005-R7, subject to that PR's protected merge. Original research theorem proofs and any external formalizations are attributed to their authors, not newly GCL-certified. The historical source and proof-review limitations recorded in the return remain applicable.
What remains
ERDOS-747-PERFECT_MATCHING_THRESHOLD. Prove exact n=2 ten-matchings fixture and expectation of isolated vertices under G(3n,ℓ) WITHOUT replacement, and inspect Kahn's sharp threshold theorem for probability window and admissibility 3n divisible by3. Acceptance is an exact source-grounded probabilistic threshold, not a GCL new proof.
Sources and claim boundaries
Maintained Problem #747; original GCL issue return. Full historical proof papers and external Lean kernels unreviewed. no independent theorem proof certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2018 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.