Dual View Random Solved Random Open
SOLVED This has been resolved in some other way than a proof or disproof.
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}$?
A problem of Daykin and Erdős. Daykin and Frankl proved that if there are $(1+o(1))\binom{m}{2}$ edges then $m^{1/n}\to 1$ as $n\to \infty$.

For the first question we need to take $\epsilon>0$ since since if $n$ is even and $m=2^{n/2+1}$ one could take $\mathcal{F}$ to be all subsets of $\{1,\ldots,n/2\}$ together with $\{1,\ldots,n/2\}$ union all subsets of $\{n/2+1,\ldots,n\}$, which produces $2^{n}$ edges.

The third question was answered in the affirmative by Alon and Frankl [AlFr85], who proved that, for every $k\geq 1$, if $m=2^{(\frac{1}{k+1}+\delta)n}$ for some $\delta>0$ then the number of edges is\[< \left(1-\frac{1}{k}\right)\binom{m}{2}+O(m^{2-\Omega_k(\delta^{k+1})}).\]They also answer the second question in the negative, noting that if $\mathcal{F}$ is the family of sets which either intersect $\{n/2+1,\ldots,n\}$ in at most $1$ element or intersect $\{1,\ldots,n/2\}$ in at least $n/2-1$ elements then $m \gg n2^{n/2}$ and there are at least $2^{-5}\binom{m}{2}$ edges.

Finally, an affirmative answer to the first question follows from Theorem 1.4 and Corollary 1.5 of Alon, Das, Glebov, and Sudakov [ADGS15].

View the LaTeX source

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #777, https://www.erdosproblems.com/777, accessed 2026-01-16