首页|Disproof of a conjecture of Erd\H{o}s and Simonovits on the Tur\'an
number of graphs with minimum degree 3
Disproof of a conjecture of Erd\H{o}s and Simonovits on the Tur\'an number of graphs with minimum degree 3
Disproof of a conjecture of Erd\H{o}s and Simonovits on the Tur\'an number of graphs with minimum degree 3
In 1981, Erd\H{o}s and Simonovits conjectured that for any bipartite graph $H$ we have $\mathrm{ex}(n,H)=O(n^{3/2})$ if and only if $H$ is $2$-degenerate. Later, Erd\H{o}s offered 250 dollars for a proof and 500 dollars for a counterexample. In this paper, we disprove the conjecture by finding, for any $\varepsilon>0$, a $3$-regular bipartite graph $H$ with $\mathrm{ex}(n,H)=O(n^{4/3+\varepsilon})$.
Oliver Janzer
数学
Oliver Janzer.Disproof of a conjecture of Erd\H{o}s and Simonovits on the Tur\'an number of graphs with minimum degree 3[EB/OL].(2021-09-13)[2025-08-24].https://arxiv.org/abs/2109.06110.点此复制
评论