| Autor: |
Allen, Peter, Böttcher, Julia, Corsten, Jan, Davies, Ewan, Jenssen, Matthew, Morris, Patrick, Roberts, Barnaby, Skokan, Jozef |
| Předmět: |
|
| Zdroj: |
Random Structures & Algorithms; Aug2024, Vol. 65 Issue 1, p61-130, 70p |
| Abstrakt: |
For a graph G$$ G $$ and p∈[0,1]$$ p\in \left[0,1\right] $$, we denote by Gp$$ {G}_p $$ the random sparsification of G$$ G $$ obtained by keeping each edge of G$$ G $$ independently, with probability p$$ p $$. We show that there exists a C>0$$ C>0 $$ such that if p≥C(logn)1/3n−2/3$$ p\ge C{\left(\log n\right)}^{1/3}{n}^{-2/3} $$ and G$$ G $$ is an n$$ n $$‐vertex graph with n∈3ℕ$$ n\in 3\mathbb{N} $$ and δ(G)≥2n3$$ \delta (G)\ge \frac{2n}{3} $$, then with high probability Gp$$ {G}_p $$ contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of C$$ C $$, are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to p=1$$ p=1 $$ in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in G(n,p)$$ G\left(n,p\right) $$ (corresponding to G=Kn$$ G={K}_n $$ in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least 2n3$$ \frac{2n}{3} $$ which gets close to the truth. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Plný text