Hypergraph limits: A regularity approach. Issue 2 (21st March 2014)

• Record Type: Journal Article
• Authors: Zhao, Yufei
• Is Part Of: Random structures & algorithms. Volume 47:Issue 2(2015)
• Page Start: 205
• Page End: 226
• Publication Date: 2014-03-21
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20537
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>A sequence of <italic>k</italic>‐uniform hypergraphs <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjdbg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20537:rsa20537-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>H</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:msub><mml:mi>H</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:mo>…</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is convergent if the sequence of homomorphism densities <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjdc1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20537:rsa20537-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>t</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>F</mml:mi><mml:mo>, </mml:mo><mml:msub><mml:mi>H</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>, </mml:mo><mml:mi>t</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>F</mml:mi><mml:mo>, </mml:mo><mml:msub><mml:mi>H</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>, </mml:mo><mml:mo>…</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> converges for every <italic>k</italic>‐uniform hypergraph <italic>F</italic>. For graphs, Lovász and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjddk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20537:rsa20537-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>W</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>→</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. For hypergraphs, analogous limits <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twjdf4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20537:rsa20537-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>W</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo>→</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> 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</p> </abstract>