Logo
All Random Solved Random Open
1 solved out of 7 shown (show only solved or open)
OPEN
Let $n\geq k+1$. Every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains every tree on $k+1$ vertices.
A problem of Erdős and Sós, who also conjectured that every graph with at least \[\max\left( \binom{2k-1}{2}+1, (k-1)n-(k-1)^2+\binom{k-1}{2}+1\right)\] many edges contains every forest with $k$ edges. (Erdős and Gallai [ErGa59] proved that this is the threshold which guarantees containing $k$ independent edges.)

It can be easily proved by induction that every graph on $n$ vertices with at least $n(k-1)+1$ edges contains every tree on $k+1$ vertices.

Brandt and Dobson [BrDo96] have proved this for graphs of girth at least $5$. Wang, Li, and Liu [WLL00] have proved this for graphs whose complements have girth at least $5$. Saclé and Woznik [SaWo97] have proved this for graphs which contain no cycles of length $4$. Yi and Li [YiLi04] have proved this for graphs whose complements contain no cycles of length $4$.

Implies [547] and [557].

See also 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
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
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$.