论文标题
图中集团的平衡细分
Balanced subdivisions of cliques in graphs
论文作者
论文摘要
给定图形$ h $，$ h $的平衡细分是从$ h $获得的图形，通过将每个边缘用相同的次数细分。 1984年，托马森（Thomassen）猜想，对于每个整数$ k \ ge 1 $，高平均学位足以保证$ k_k $的平衡细分。最近，刘和蒙哥马利解决了这一猜想。我们通过证明存在$ c> 0 $的最佳估计，最高为绝对恒定的因素，以便对于足够大的$ d $，每张平均度至少$ d $的图表都包含一个平衡的分区，其中一个包含至少$ cd^{1/2} $ vertices的群集。它还确认了一个来自Verstra {ë} te的猜想：平均度$ CD^2 $的每张图，对于某些绝对常数$ C> 0 $，包含一对完整图$ k_d $的一对脱节异构成细分。我们还证明，存在一些绝对的$ c> 0 $，因此对于足够大的$ d $，每个$ c_4 $ free图，平均度至少$ d $包含完整图$ k_ {cd cd} $的平衡细分，这扩展了Balogh，Liu和Sharifzadeh的结果。
Given a graph $H$, a balanced subdivision of $H$ is a graph obtained from $H$ by subdividing every edge the same number of times. In 1984, Thomassen conjectured that for each integer $k\ge 1$, high average degree is sufficient to guarantee a balanced subdivision of $K_k$. Recently, Liu and Montgomery resolved this conjecture. We give an optimal estimate up to an absolute constant factor by showing that there exists $c>0$ such that for sufficiently large $d$, every graph with average degree at least $d$ contains a balanced subdivision of a clique with at least $cd^{1/2}$ vertices. It also confirms a conjecture from Verstra{ë}te: every graph of average degree $cd^2$, for some absolute constant $c>0$, contains a pair of disjoint isomorphic subdivisions of the complete graph $K_d$. We also prove that there exists some absolute $c>0$ such that for sufficiently large $d$, every $C_4$-free graph with average degree at least $d$ contains a balanced subdivision of the complete graph $K_{cd}$, which extends a result of Balogh, Liu and Sharifzadeh.
