Logo
All Random Solved Random Open
4 solved out of 20 shown (show only solved or open)
SOLVED
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
SOLVED - $250
If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ is $2$-degenerate, that is, $G$ contains no induced subgraph with minimal degree at least 3.
Conjectured by Erdős and Simonovits. Erdős offered \$250 for a proof and \$100 for a counterexample. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [146] and [147] and the entry in the graphs problem collection.

Additional thanks to: Zachary Hunter
OPEN - $500
If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]
Conjectured by Erdős and Simonovits. Open even for $r=3$. Alon, Krivelevich, and Sudakov [AKS03] have proved \[\mathrm{ex}(n;H) \ll n^{2-1/4r}.\] They also prove the full Erdős-Simonovits conjectured bound if $H$ is bipartite and the maximum degree in one component is $r$.

See also [113] and [147].

See also the entry in the graphs problem collection.

SOLVED - $500
If $H$ is bipartite and is not $r$-degenerate, that is, there exists an induced subgraph of $H$ with minimum degree $>r$ then \[\mathrm{ex}(n;H) > n^{2-\frac{1}{r}+\epsilon}.\]
Conjectured by Erdős and Simonovits. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [113], [146], and [714].

See also the entry in the graphs problem collection.

Additional thanks to: Zachary Hunter
OPEN
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 $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]

A problem of Erdős and Simonovits.

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.

See also [575] and the entry in the graphs problem collection.

OPEN - $500
What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.
A problem of Turán. Turán observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that \[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\] This is probably the truth. The current best upper bound is \[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\] due to Razborov [Ra10].

See also [712] for the general case.

OPEN
Show that for any rational $\alpha \in (1,2)$ there exists a bipartite graph $G$ such that \[\mathrm{ex}(n;G)\asymp n^{\alpha}.\] Conversely, if $G$ is bipartite then must there exist some rational $\alpha$ such that\[\mathrm{ex}(n;G)\asymp n^{\alpha}?\]
A problem of Erdős and Simonovits.

See also [713] and the entry in the graphs problem collection.

OPEN
Show that for $k\geq 3$ \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.\]
It is easy to see that $\mathrm{ex}(n;C_{2k+1})=\lfloor n^2/4\rfloor$ for any $k\geq 1$ (and $n>2k+1$) (since no bipartite graph contains an odd cycle). Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$.

Erdős [Er64c] and Bondy and Simonovits [BoSi74] showed that \[\mathrm{ex}(n;C_{2k})\ll kn^{1+\frac{1}{k}}.\]

Benson [Be66] has proved this conjecture for $k=3$ and $k=5$. Lazebnik, Ustimenko, and Woldar [LUW95] have shown that, for arbitrary $k\geq 3$, \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{2}{3k-3+\nu}},\] where $\nu=0$ if $k$ is odd and $\nu=1$ if $k$ is even. See [LUW99] for further history and references.

See also [765] and the entry in the graphs problem collection.

OPEN
Is it true that \[\mathrm{ex}(n;\{C_3,C_4\})=(n/2)^{3/2}+O(n)?\]
A problem of Erdős and Simonovits, who proved that \[\mathrm{ex}(n;\{C_4,C_5\})=(n/2)^{3/2}+O(n).\]

See also [574] and the entry in the graphs problem collection.

OPEN
Is it true that, for $k\geq 2$, \[\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=(1+o(1))(n/2)^{1+\frac{1}{k}}.\]
A problem of Erdős and Simonovits.

See also [573] and the entry in the graphs problem collection.

OPEN
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}$, if there is a bipartite graph in $\mathcal{F}$ then there exists some bipartite $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]

A problem of Erdős and Simonovits.

See also [180] and the entry in the graphs problem collection.

OPEN
Let $Q_k$ be the $k$-dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of \[\mathrm{ex}(n;Q_k).\]
Erdős and Simonovits [ErSi70] proved that \[(\tfrac{1}{2}+o(1))n^{3/2}\leq \mathrm{ex}(n;Q_3) \ll n^{8/5}.\] In [Er81] Erdős asks whether it is $\asymp n^{8/5}$.

A theorem of Sudakov and Tomon [SuTo22] implies \[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\] Janzer and Sudakov [JaSu22b] have improved this to \[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\] See also the entry in the graphs problem collection.

OPEN
Let $\epsilon>0$ and $n$ be sufficiently large. Show that, if $G$ is a graph on $n$ vertices which does not contain $K_{2,2,2}$ and $G$ has at least $\epsilon n^2$ many edges, then $G$ contains an independent set on $\gg_\epsilon n$ many vertices.
A problem of Erdős, Hajnal, Sós, and Szemerédi.

See also the entry in the graphs problem collection.

OPEN - $500
Determine, for any $k>r>2$, the value of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where $\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$-edges which can placed on $n$ vertices so that there exists no $K_k^r$, a set of $k$ vertices which is covered by all $\binom{k}{r}$ possible $r$-edges.
Turán proved that, when $r=2$, this limit is \[\frac{1}{2}\left(1-\frac{1}{k-1}\right).\] Erdős [Er81] offered \$500 for the determination of this value for any fixed $k>r>2$, and \$1000 for 'clearing up the whole set of problems'.

See also [500] for the case $r=3$ and $k=4$.

OPEN - $500
Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [0,1)$ such that \[\lim_{n\to \infty}\frac{\mathrm{ex}(n;G)}{n^{1+\alpha}}\] exists and is in $(0,\infty)$?
A problem of Erdős and Simonovits. This is not true for hypergraphs, as shown by Ruzsa and Szemerédi [RuSz78], who proved that if $G$ is a $3$-uniform hypergraph on $6$ vertices containing $3$ $3$-edges then $\mathrm{ex}_3(n;G)=o(n^2)$ and yet for every $\epsilon >0$ \[\mathrm{ex}_3(n;G) >n^{2-\epsilon}\] for all large enough $n$.

See also [571].

OPEN
Is it true that \[\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?\]
Kövári, Sós, and Turán [KST54] proved \[\mathrm{ex}(n; K_{r,r}) \ll n^{2-1/r}.\] Brown [Br66] proved the conjectured lower bound when $r=3$.

See also [147].

Additional thanks to: Rishika Agrawal
SOLVED
Give an asymptotic formula for $\mathrm{ex}(n;C_4)$.
Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$. Reiman [Re] proved \[\frac{1}{2\sqrt{2}}\leq \lim \frac{\mathrm{ex}(n;C_4)}{n^{3/2}}\leq \frac{1}{2}.\] Erdős and Rényi, and independently Brown, gave a construction that proved if $n=q^2+q+1$, where $q$ is a prime power, then \[\mathrm{ex}(n;C_4)\geq\frac{1}{2}q(q+1)^2.\] Coupled with the upper bound of Reiman this implies that $\mathrm{ex}(n;C_4)\sim\frac{1}{2}n^{3/2}$ for all large $n$. Füredi [Fu83] proved that if $q>13$ then \[\mathrm{ex}(n;C_4)=\frac{1}{2}q(q+1)^2.\]

See also [572].

Additional thanks to: Rishika Agrawal
OPEN
Let $f(n;k,l)=\min \mathrm{ex}(n;G)$, where $G$ ranges over all graphs with $k$ vertices and $l$ edges.

Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$. For fixed $k$ and large $n$ is $f(n;k,l)$ a strictly monotone function of $l$?

Dirac and Erdős proved independently that when $l=\lfloor k^2/4\rfloor+1$ \[f(n;k,l)\leq \lfloor n^2/4\rfloor+1.\]
OPEN
Let $c(k)$ be minimal such that every graph on $n$ vertices with at least $kn+c(k)$ edges contains a cycle with at least $k-1$ diagonals adjacent to a single vertex. Is it true that $c(k)=1-k^2$?
Czipszer proved that $c(k)$ exists for all $k$. Erdős wrote it is 'easy to see' that $c(k)\geq 1-k^2$. Pósa proved $c(2)=-3$. Erdős could prove this when $k=3$ or $k=4$.
OPEN
Is it true that every $3$-uniform hypergraph on $3n$ vertices with at least $n^3+1$ edges must contain either a subgraph on $4$ vertices with $3$ edges or a subgraph on $5$ vertices with $7$ edges?
Additional thanks to: Rishika Agrawal