Tiling randomly perturbed multipartite graphs

2025/04/09 by Gomez-Leos, Enrique, Martin, Ryan R.
#05C35 #05C70 #05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.07284

Abstract

A perfect K_r-tiling in a graph G is a collection of vertex-disjoint copies of the graph K_r in G that covers all vertices of G. In this paper, we prove that the threshold for the existence of a perfect K_r-tiling of a randomly perturbed balanced r-partite graph on rn vertices is n^-2/r. This result is a multipartite analog of a theorem of Balogh, Treglown, and Wagner and extends our previous result, which was limited to the bipartite setting.

Related

• Tiling randomly perturbed bipartite graphs
• Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu
• Tilings in randomly perturbed dense graphs
• Tiling edge-ordered graphs with monotone paths and other structures
• A Ramsey-Turán theory for tilings in graphs