Clique-factors in sparse pseudorandom graphs

DOI10.1016/J.EJC.2019.102999MaRDI QIDQ2323252zbMATH OpenOpenAlexWikidataFDO

Authors Jie Han, Yoshiharu Kohayakawa, Patrick Morris, Yury Person

Publication date 30 August 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.01676

zbMATH Keywords

jumbled graphs

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove that for any $tge3$ there exist constants $c>0$ and $n_0$ such that any $d$-regular $n$-vertex graph $G$ with $tmidngeq{n}_0$ and second largest eigenvalue in absolute value $lambda$ satisfying $lambdalec{d}^t/n^{t-1}$ contains a $K_t$-factor, that is, vertex-disjoint copies of $K_t$ covering every vertex of $G$.

Recommendations

• Near-perfect clique-factors in sparse pseudorandom graphs
• Near-perfect clique-factors in sparse pseudorandom graphs
• Triangle‐factors in pseudorandom graphs
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
• Triangle factors in sparse pseudo-random graphs

Cites work

• Blow-up lemma
• Explicit construction of linear sized tolerant networks
• Explicit Ramsey graphs and orthonormal labelings
• Hall's theorem for hypergraphs
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Near-perfect clique-factors in sparse pseudorandom graphs
• Powers of Hamilton cycles in pseudorandom graphs
• Pseudo-random graphs
• Spanning universality in random graphs
• Triangle factors in sparse pseudo-random graphs
• Triangle‐factors in pseudorandom graphs
• Turán's theorem for pseudo-random graphs

Cited in

(14)

• On a simple randomized algorithm for finding a 2-factor in sparse graphs
• Near-perfect clique-factors in sparse pseudorandom graphs
• On the product dimension of clique factors
• A construction for clique-free pseudorandom graphs
• 1‐Factorizations of pseudorandom graphs
• Triangle factors in sparse pseudo-random graphs
• Near-perfect clique-factors in sparse pseudorandom graphs
• Embedding clique-factors in graphs with low -independence number
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Clique-factors in graphs with sublinear -independence number
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• A Ramsey–Turán theory for tilings in graphs
• Clique factors in pseudorandom graphs

This page was built for publication: Clique-factors in sparse pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2323252)