论文标题
在常规子图上的Erdős-Sauer问题解决
Resolution of the Erdős-Sauer problem on regular subgraphs
论文作者
论文摘要
在本文中，我们从1975年开始完全解决了众所周知的ERDS和SAUER问题，该问题要求最大数量的边缘数量$ n $ vertex图可以在不包含$ k $的子图中，对于某些固定整数$ k \ geq 3 $。我们证明，任何$ n $ vertex图具有平均水平至少$ C_K \ log \ log n $包含$ k $ -Regular子图。这与Pyber，Rödl和Szemerédi的下边界相匹配，并大大改善了Pyber的旧结果，Pyber表明平均程度至少$ C_K \ log n $就足够了。 我们的方法还可以用来渐近地解决Erds和Simonovits在1970年几乎常规的稀疏图子图中提出的问题，并在1983年从托马森（Thomassen）的著名问题上取得了进展，该问题在发现具有较大giirth和较大平均水平的子绘画方面。
In this paper we completely resolve the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log \log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough. Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.
