On the 3‐Local Profiles of Graphs. Issue 3 (23rd August 2013)

• Record Type: Journal Article
• Authors: Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny
• Is Part Of: Journal of graph theory. Volume 76:Issue 3(2014)
• Page Start: 236
• Page End: 248
• Publication Date: 2013-08-23
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21762
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>For a graph <italic>G</italic>, let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z0g6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>, </mml:mo><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mo>.</mml:mo><mml:mo>.</mml:mo><mml:mo>.</mml:mo><mml:mo>, </mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></alternatives> be the probability that three distinct random vertices span exactly <italic>i</italic> edges. We call <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z0cj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>, </mml:mo><mml:mo>.</mml:mo><mml:mo>.</mml:mo><mml:mo>.</mml:mo><mml:mo>, </mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives> the <italic>3‐local profile</italic> of <italic>G</italic>. We investigate the set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z09f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>⊂</mml:mo><mml:msup><mml:mi mathvariant="double-struck">R</mml:mi><mml:mn>4</mml:mn></mml:msup></mml:mrow></mml:math></alternatives> of all vectors <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1gq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:mo>.</mml:mo><mml:mo>.</mml:mo><mml:mo>.</mml:mo><mml:mo>, </mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives> that are arbitrarily close to the 3‐local profiles of arbitrarily large graphs. We give a full description of the projection of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1jt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mn>3</mml:mn></mml:msub></mml:math></alternatives> to the <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z19z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives> plane. The upper envelope of this planar domain is obtained from cliques on a fraction of the vertex set and complements of such graphs. The lower envelope is Goodman's inequality <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1c2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>+</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mn>4</mml:mn></mml:mfrac></mml:mrow></mml:math></alternatives>. We also give a full description of the triangle‐free case, i.e. the intersection of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1p1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mn>3</mml:mn></mml:msub></mml:math></alternatives> with the hyperplane <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1qk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21762:jgt21762-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives>. This planar domain is characterized by an SDP constraint that is derived from Razborov's flag algebra theory.</p> </abstract>