We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

math.CO

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Mathematics > Combinatorics

Title: The hitting time of clique factors

Abstract: In a recent paper, Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let $r \ge 3 $ and let $n$ be divisible by $r$. Then, in the random $r$-uniform hypergraph process on $n$ vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we transfer this hitting time result to the setting of clique factors in the random graph process: At the time that the last vertex joins a copy of the complete graph $K_r$, the random graph process contains a $K_r$-factor. Our proof draws on a novel sequence of couplings, extending techniques of Riordan and the first author. An analogous result is proved for clique factors in the $s$-uniform hypergraph process ($s \ge 3$).
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)
MSC classes: 05C80, 05C70, 05C65
Cite as: arXiv:2302.08340 [math.CO]
  (or arXiv:2302.08340v1 [math.CO] for this version)

Submission history

From: Marc Kaufmann [view email]
[v1] Thu, 16 Feb 2023 14:50:20 GMT (42kb)

Link back to: arXiv, form interface, contact.