On Komlós’ tiling theorem in random graphs
On Komlós’ tiling theorem in random graphs
复制标题
关于随机图中的 Komlós 平铺定理
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
N. Skoric
中科院分区：
文献类型：
--
作者：
R. Nenadov;N. Skoric
给定图G和H，H在G中的一族顶点不相交的复本称为H-平铺。Conlon，Gowers，Samotj和Schacht证明了对于给定的图H和常数γ>；0，存在C>；0使得如果
$p GE C{n^{-1/{m_2}(H)}}$
，则随机图？(n，p)的每个支撑子图G几乎必然至少具有最小度
$Delta(G)ge(1-Frc{1}{{chi_{{
M{cr}(H)}}+Gamma)Np$
包含覆盖除最多γn个顶点之外的所有顶点的H平铺。这里，χcr(H)表示临界色数，这是由KomlóS引入的一个参数，m 2(H)是H的2-密度.我们证明了这个定理可以自举得到一个H-平铺覆盖，除了至多
$Gamma{(C/p)^{{m_2}(H)}}$
顶点，当出现以下情况时，它将严格减小
$p GE C{n^{-1/{m_2}(H)}}$
。在H=K3的情况下，这回答了Balogh，Lee和Samotj的问题。此外，对于任意图H，我们给出了p的一个上界，其中p的一些剩余是不可避免的，并且给出了p的最大H-平铺的大小的界。
Abstract Given graphs G and H, a family of vertex-disjoint copies of H in G is called an H-tiling. Conlon, Gowers, Samotij and Schacht showed that for a given graph H and a constant γ >0, there exists C>0 such that if
$p ge C{n^{ - 1/{m_2}(H)}}$
, then asymptotically almost surely every spanning subgraph G of the random graph ?(n, p) with minimum degree at least
$delta (G) ge (1 - frac{1}{{{chi _{{
m{cr}}}}(H)}} + gamma )np$
contains an H-tiling that covers all but at most γn vertices. Here, χ cr(H) denotes the critical chromatic number, a parameter introduced by Komlós, and m 2(H) is the 2-density of H. We show that this theorem can be bootstrapped to obtain an H-tiling covering all but at most
$gamma {(C/p)^{{m_2}(H)}}$
vertices, which is strictly smaller when
$p ge C{n^{ - 1/{m_2}(H)}}$
. In the case where H = K3, this answers the question of Balogh, Lee and Samotij. Furthermore, for an arbitrary graph H we give an upper bound on p for which some leftover is unavoidable and a bound on the size of a largest H -tiling for p below this value.
关于随机图中的 KÅR 猜想
影响因子：
1
作者：
D. Conlon;W. T. Gowers;W. Samotij;M. Schacht
通讯作者：
M. Schacht
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus