Erdős Problem #777
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: graph theory, combinatorics.
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
Given a family of distinct subsets of \({1,\ldots,n}\), draw a graph joining two family members whenever one is contained in the other. Erdős Problem #777 asks how dense this comparability graph can be, especially for families with size near \(2^{n/2}\).
The registered problem contains three separate conjectural implications, not a single yes/no assertion. According to the maintained catalogue, the first has an affirmative answer, the second a negative answer, and the third an affirmative answer. The status label SOLVED must not conceal these opposite outcomes.
A small example
For \(n=2\), consider the family
There are six unordered pairs of its four members. Every pair is comparable except \(\{1\}\) and \(\{2\}\), so the comparability graph has exactly five edges. No self-comparisons are counted.
A chain of \(m\) distinct nested sets has all \(\binom m2\) possible edges. But in an \(n\) element Boolean lattice, a strict chain has at most \(n+1\) members, so this elementary example cannot establish density for exponential-size families.
What is known
Let \(m=|\mathcal F|\) and let \(c(\mathcal F)\) denote the number of strict comparable pairs. The three parts ask, roughly, whether (1) if \(m\leq(2-\varepsilon)2^{n/2}\) then \(c(\mathcal F)<2^n\) for large \(n\), (2) if \(c(\mathcal F)\geq cm^2\) then necessarily \(m=O_c(2^{n/2})\), and (3) if \(c(\mathcal F)>m^{2-\delta}\) then \(m<(2+\varepsilon)^{n/2}\) for some \(\delta=\delta(\varepsilon)>0\).
In Comparable pairs in families of sets, Noga Alon, Shagnik Das, Roman Glebov and Benny Sudakov study the maximal possible comparable-pair count. Their paper appeared in Journal of Combinatorial Theory, Series B 115 (2015), 164–185. The authors' abstract establishes, among other things, that \(c(n,m)=o(m^2)\) when \(m=n^{\omega(1)}2^{n/2}\). The catalogue more specifically attributes an affirmative answer to (1) to their Theorem 1.4 and Corollary 1.5; the inference requires their precise hypotheses, not the abstract statement alone.
The maintained catalogue attributes the affirmative third part to Alon and Frankl (1985), and reports their construction disproving the second: families can have \(m\gg n2^{n/2}\) yet a positive proportion of all \(\binom m2\) pairs comparable. Thus positive density of comparabilities does not force the claimed scale.
The threshold constants \(2-\varepsilon\) and \(2+\varepsilon\) occur in different implications. Confusing the base \(2\) with a multiplicative constant would change their substance.
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
Check the exact 2015 Theorem 1.4/Corollary 1.5 and its parameters against part (1). Expand the original 1985 dense-family construction into an auditable cardinality and comparable-pair count. Finite tests should enumerate comparability edges and verify that they are between distinct family members, preventing diagonal overcounting. Submit a separate critical review of all three quantifier statements before protected admission.
Sources and claim boundaries
- Erdős problem #777 and authenticated source return.
- N. Alon, S. Das, R. Glebov, B. Sudakov, Comparable pairs in families of sets, JCTB 115 (2015), 164–185; DOI; arXiv:1411.4196.
- Alon–Frankl 1985 result attributed in the maintained catalogue; its full original proof is pending. no independent theorem proof certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2048 — 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.