2023/02/16 by Heckel, Annika, Kaufmann, Marc, Müller, Noela +1
#05C65 #05C70 #05C80 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2302.08340
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 Kr, the random graph process contains a Kr-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).