论文标题
平均程度较大的无C4无C4
C4-free subgraphs with large average degree
论文作者
论文摘要
由托马森（Thomassen）长期以来的猜想，我们研究了图表的平均程度需要多大，以暗示它包含一个$ C_4 $ - 免费的子图，并具有平均程度至少至少$ t $。 Kühn和Osthus表明，在T中具有双重指数的平均度结合就足够了。在将其简化为单个指数之前，我们简短地证明了这种界限。也就是说，我们表明的任何图形$ g $具有平均度至少$ 2^{ct^2 \ log t} $（对于某些常数$ c> 0 $）都包含一个$ c_4 $ - free子图，平均度至少$ t $。最后，我们提供了一个改善此问题的下限的结构，表明此初始平均度必须至少为$ t^{3-o（1）} $。
Motivated by a longstanding conjecture of Thomassen, we study how large the average degree of a graph needs to be to imply that it contains a $C_4$-free subgraph with average degree at least $t$. Kühn and Osthus showed that an average degree bound which is double exponential in t is sufficient. We give a short proof of this bound, before reducing it to a single exponential. That is, we show that any graph $G$ with average degree at least $2^{ct^2\log t}$ (for some constant $c>0$) contains a $C_4$-free subgraph with average degree at least $t$. Finally, we give a construction which improves the lower bound for this problem, showing that this initial average degree must be at least $t^{3-o(1)}$.
