论文标题
解决ERD的解决方案和Hajnal的奇数问题
A solution to Erdős and Hajnal's odd cycle problem
论文作者
论文摘要
1981年，Erdős和Hajnal询问了无限色数的图中奇数循环长度的倒数之和是否必然是无限的。令$ \ MATHCAL {C}（G）$为图$ G $中的一组循环长度，让$ \ Mathcal {C} _ \ text {Odd}（g）$是$ \ Mathcal {C}（g）$中的奇数组。我们证明，如果$ g $具有色度$ k $，则$ \ sum _ {\ ell \ in \ Mathcal {c} _ \ text {odd}（g）}（g）} 1/\ ell \ geq（1/2-o_k（1/2-o_k（1））\ log k $。这解决了ERDS和Hajnal的奇数问题，此外，该结合在渐近上是最佳的。 1984年，Erds询问是否有大约$ d $，以便每个具有至少$ d $的色数（或者甚至平均程度至少至少$ d $）具有一个周期的循环，其长度为2。我们表明，平均度条件足以解决此问题，并以适用于2次序列的方法来求解它。 最后，我们使用我们的方法来表明，对于每$ k $，都有大约$ d $，因此每个平均度至少$ d $的图形都有一个完整的图形$ k_k $的细分，其中每个边缘都分为相同的次数。这证实了1984年以来托马森的猜想。
In 1981, Erdős and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph with infinite chromatic number is necessarily infinite. Let $\mathcal{C}(G)$ be the set of cycle lengths in a graph $G$ and let $\mathcal{C}_\text{odd}(G)$ be the set of odd numbers in $\mathcal{C}(G)$. We prove that, if $G$ has chromatic number $k$, then $\sum_{\ell\in \mathcal{C}_\text{odd}(G)}1/\ell\geq (1/2-o_k(1))\log k$. This solves Erdős and Hajnal's odd cycle problem, and, furthermore, this bound is asymptotically optimal. In 1984, Erdős asked whether there is some $d$ such that each graph with chromatic number at least $d$ (or perhaps even only average degree at least $d$) has a cycle whose length is a power of 2. We show that an average degree condition is sufficient for this problem, solving it with methods that apply to a wide range of sequences in addition to the powers of 2. Finally, we use our methods to show that, for every $k$, there is some $d$ so that every graph with average degree at least $d$ has a subdivision of the complete graph $K_k$ in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984.
