Hypergraph limits: A regularity approach. Issue 2 (21st March 2014) - Zhao, Yufei
<x xml:space="preserve">Abstract</x> A sequence of k‐uniform hypergraphs <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjdbg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />H1, H2, …</alternatives> is convergent if the sequence of homomorphism densities <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjdc1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />t(F, H1), t(F, H2), …</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjddk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />W:[0, 1]2→[0, 1]</alternatives>. For hypergraphs, analogous limits <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjdf4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />W:[0, 1]2k−2→[0, 1]</alternatives> 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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 205–226, 2015