Erdős Problems

Tags Prizes

1 solved out of 2 shown (show only solved or open)

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).\]

#576: [Er64c][ErSi70][Er81]

graph theory, turan number

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.

SOLVED

We call a graph $H$ $D$-balanced if the maximum degree of $H$ is at most $D$ times the minimum degree of $H$.

Is it true that for every $m\geq 1$, if $n$ is sufficiently large, any graph on $n$ vertices with $\geq n\log_2n$ edges contains a $O(1)$-balanced subgraph with $m$ vertices and $\gg m\log m$ edges (where the implied constants are absolute)?

#803: [ErSi70]

graph theory

A problem of Erdős and Simonovits [ErSi70], who proved a similar claim replacing $\log n$ and $\log m$ by $n^{c}$ and $m^c$ respectively, for any constant $c>0$ (where the balance parameter may depend on $c$).

Alon [Al08] proved this is actually false: for every $D>1$ and $n>10^5$ there is a graph $G$ with $\leq 2n$ vertices and $\geq 2n\log(2n)$ edges such that if $H$ is a $D$-balanced subgraph then $H$ has $\ll m(\sqrt{\log m}+\log D)$ many edges.