pith. sign in

arxiv: 1611.09466 · v1 · pith:WJEP3JA4new · submitted 2016-11-29 · 🧮 math.CO

On Koml\'os' tiling theorem in random graphs

classification 🧮 math.CO
keywords gammapackinggraphkomlmathrmrandomsamotijtheorem
0
0 comments X
read the original abstract

Conlon, Gowers, Samotij, and Schacht showed that for a given graph $H$ and a constant $\gamma > 0$, there exists $C > 0$ such that if $p \ge Cn^{-1/m_2(H)}$ then asymptotically almost surely every spanning subgraph $G$ of the random graph $\mathcal{G}(n,p)$ with minimum degree at least $\delta(G) \ge (1 - 1/\chi_{\mathrm{cr}}(H) + \gamma )np$ contains an $H$-packing that covers all but at most $\gamma n$ vertices. Here, $\chi_{\mathrm{cr}}(H)$ denotes the critical chromatic threshold, a parameter introduced by Koml\'os. We show that this theorem can be bootstraped to obtain an $H$-packing covering all but at most $\gamma (C/p)^{m_2(H)}$ vertices, which is strictly smaller when $p > C n^{-1/m_2(H)}$. In the case where $H = K_3$ this answers the question of Balogh, Lee, and Samotij. Furthermore, we give an upper bound on the size of an $H$-packing for certain ranges of $p$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.