skip to main content
Idioma:

A robust Corrádi–Hajnal theorem

Allen, Peter ; Böttcher, Julia ; Corsten, Jan ; Davies, Ewan ; Jenssen, Matthew ; Morris, Patrick ; Roberts, Barnaby ; Skokan, Jozef

Random structures & algorithms, 2024-08, Vol.65 (1), p.61-130 [Periódico revisado por pares]

New York: John Wiley & Sons, Inc

Texto completo disponível

Citações Citado por
  • Título:
    A robust Corrádi–Hajnal theorem
  • Autor: Allen, Peter ; Böttcher, Julia ; Corsten, Jan ; Davies, Ewan ; Jenssen, Matthew ; Morris, Patrick ; Roberts, Barnaby ; Skokan, Jozef
  • Assuntos: clique factors ; extremal graph theory ; Lower bounds ; random graphs ; robustness ; Theorems
  • É parte de: Random structures & algorithms, 2024-08, Vol.65 (1), p.61-130
  • Descrição: 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.
  • Editor: New York: John Wiley & Sons, Inc
  • Idioma: Inglês
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  8 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.