Hypergraph limits: a regularity approach, Random Structures and Algorithms

Abstract. A sequence of k-uniform hypergraphs H1, H2,... is convergent if the sequence of homo-morphism densities t(F,H1), t(F,H2),... converges for every k-uniform hypergraph F. For graphs, Lovász and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function W: [0, 1]2 → [0, 1]. For hypergraphs, analogous limits W: [0, 1]2k−2 → [0, 1] were constructed by Elek and Szegedy using ultraproducts. These limits had also been studied earlier by Hoover, Aldous, and Kallenberg in the setting of exchangeable random arrays. In this paper, we give a new proof and construction of hypergraph limits. Our approach is inspired by the original approach of Lovász and Szegedy, with the key ingredient being a weak Frieze-Kannan type regularity lemma. 1