Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
3 solved out of 5 shown
Is it true that the number of graphs on $n$ vertices which do not contain $G$ is \[\leq 2^{(1+o(1))\mathrm{ex}(n;G)}?\]
If $G$ is not bipartite the answer is yes, proved by Erdős, Frankl, and Rödl [ErFrRo86]. The answer is no for $G=C_6$, the cycle on 6 vertices. Morris and Saxton [MoSa16] have proved there are at least \[2^{(1+c)\mathrm{ex}(n;C_6)}\] such graphs for infinitely many $n$, for some constant $c>0$. It is still possible (and conjectured by Morris and Saxton) that the weaker bound of \[2^{O(\mathrm{ex}(n;G))}\] holds for all $G$.
Additional thanks to: Tuan Tran
If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ contains no induced subgraph with minimal degree at least 3.
Conjectured by Erdős and Simonovits. Disproved by Janzer [Ja21].
Additional thanks to: Zachary Hunter
$500
If $H$ is bipartite and every induced subgraph of $H$ has minimum degree $<r$ then \[\mathrm{ex}(n;H) \ll n^{2-1/(r-1)}.\]
Conjectured by Erdős and Simonovits. Open even for $r=3$.
$500
If $H$ is bipartite and there exists an induced subgraph of $H$ with minimum degree $\geq r$ then \[\mathrm{ex}(n;H) > n^{2+\epsilon-1/(r-1)}.\]
Conjectured by Erdős and Simonovits. Disproved by Janzer [Ja21].
Additional thanks to: Zachary Hunter
If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs from $\mathcal{F}$. Note that it is trivial that $\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G)$ for every $G\in\mathcal{F}$.

Is it true that, for every $\mathcal{F}$, there exists some constant $C_{\mathcal{F}}>0$ and $G\in\mathcal{F}$ such that for all large $n$ \[\mathrm{ex}(n;G)\leq C_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]

This is trivially true if $\mathcal{F}$ does not contain any bipartite graphs, since by the Erdős-Stone theorem if $H\in\mathcal{F}$ has minimal chromatic number $r\geq 2$ then \[\mathrm{ex}(n;H)=\mathrm{ex}(n;\mathcal{F})=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}.\] Erdős and Simonovits observe that this is false for infinite families $\mathcal{F}$, e.g. the family of all cycles.