The hitting time of clique factors
share
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 ≥ 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 ≥ 3).
READ FULL TEXT