Problem 777

If $\mathcal{F}$ is a family of subsets of $\{1,\ldots,n\}$ then we write $G_{\mathcal{F}}$ for the graph on $\mathcal{F}$ where $A\sim B$ if $A$ and $B$ are comparable - that is, $A\subseteq B$ or vice versa.

Is it true that, if $\epsilon>0$ and $n$ is sufficiently large, whenever $m\leq (2-\epsilon)2^{n/2}$ the graph $G_\mathcal{F}$ has $<2^{n}$ many edges?

Is it true that if $G_{\mathcal{F}}$ has $\geq cm^2$ edges then $m\ll_c 2^{n/2}$ ?

Is it true that, for any $\epsilon>0$ , there exists some $\delta>0$ such that if there are $>m^{2-\delta}$ edges then $m<(2+\epsilon)^{n/2}$ ?

Source: erdosproblems.com/777

Graph theory
Combinatorics

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved. The site's label is SOLVED, crediting Alon and Frankl with the answers to the second question (no) and the third (yes), and Alon, Das, Glebov and Sudakov with the first (yes). The parts q1, q2 and q3 are the three questions in order; the frontmatter standing is derived from the accepted partial claim pages Alon, Das, Glebov and Sudakov (settles q1) and Alon and Frankl (settles q2 and q3), whose acceptance evidence is the refereed journals and the site's own commentary. A third-party Lean file proving all three answers is linked on both pages and recorded under Formalization. The site's commentary also records Daykin and Frankl's theorem that $(1+o(1))\binom m2$ comparable pairs force $m^{1/n}\to1$ ; it settles none of the three questions, so it has no claim page.

Gu83: Guy, R. K., A miscellany of Erdős problems. Amer. Math. Monthly 90 (1983), no. 2, 118--120, doi:10.2307/2975810; the site's source key for the problem, which the site's commentary calls a problem of Daykin and Erdős.
ADGS15: Alon, Noga and Das, Shagnik and Glebov, Roman and Sudakov, Benny, Comparable pairs in families of sets. J. Combin. Theory Ser. B 115 (2015), 164--185, doi:10.1016/j.jctb.2015.05.009 (the site's reference text gives no volume).
AlFr85: Alon, N. and Frankl, P., The maximum number of disjoint pairs in a family of subsets. Graphs Combin. 1 (1985), 13--21, doi:10.1007/BF02582924 (the site's reference text gives no volume).

Problem 777

Status

Proof claims

Discussion