Common graph: Difference between revisions

Revision as of 01:49, 22 December 2021

Latest revision as of 22:26, 26 May 2025

(21 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|InConcept in extremal graph theory, common graphs arise as an interesting concept}}

{{AFC submission|d|nn|u=Unubold Lake Munkhbat Choros|ns=118|decliner=Bilorv|declinets=20211222014800|ts=20211221072630}} <!-- Do not remove this line! -->

{{AFC comment|1=Really interesting read, but the Wikipedia style isn't there yet. I've gone through rewriting and formatting to be more in line with the Wikipedia style, but the referencing remains to be done.

We need more papers than this that mention/use/introduce theory around common graphs, and every fact in Wikipedia needs to be clearly attributed to a particular source. Which reference does each proof come from? Where does the definition, the intuitions and the examples come from? — [[User:Bilorv|Bilorv]] ('''[[User talk:Bilorv|<span style="color:purple">talk</span>]]''') 01:48, 22 December 2021 (UTC)}}

----

{{Short description|In extremal graph theory, common graphs arise as an interesting concept}}

{{Draft topics|stem}}

{{AfC topic|stem}}

In [[graph theory]], an area of mathematics, '''common graphs''' belong to a branch of [[extremal graph theory]] concerning [[Homomorphism density|inequalities in homomorphism densities]]. Roughly speaking, <math>F</math> is a common [[Graph (discrete mathematics)|graph]] if it "commonly" appears as a subgraph, in a sense that the total number of copies of <math>F</math> in any graph <math>G</math> and its [[Complement graph|complement]] <math>\overline{G}</math> is a large fraction of all possible copies of <math>F</math> on the same vertices. Intuitively, if <math>G</math> contains few copies of <math>F</math>, then its complement <math>\overline{G}</math> must contain lots of copies of <math>F</math> in order to compensate for it.

Common graphs are closely related to other graph notions dealing with homomorphism density inequalities. For example, common graphs are a more general case of Sidorenko graphs (graphs with [[Sidorenko's conjecture#Statement|Sidorenko's propertygraphs]]).

== Definition ==

Formally, a common graph is aA graph <math>F</math> suchis common thatif the inequality:

<math>t(F, W) + t(F, 1 - W) \ge 2^{-e(F)+1}</math>

holds for any [[graphon]] <math>W</math>, where <math>e(F)</math> is the number of edges of <math>F</math> and <math>t(F, W)</math> is the [[homomorphism density]]. Here, note that the inequality attains the lower bound when <math>W</mathref>{{Cite isbook|title=Large theNetworks constantand graphonGraph <math>W \equiv 1Limits|url=https:/2</math>bookstore. So, the inequality is tightams.org/coll-60/|access-date=2022-01-13|publisher=American Mathematical Society|page=297}}</ref>

The inequality is tight because the lower bound is always reached when <math>W</math> is the constant graphon <math>W \equiv 1/2</math>.

For a graph <math>G</math>, we have <math>t(F, G) = t(F, W_{G}) </math> and <math>t(F, \overline{G})=t(F, 1 - W_G)</math> for the [[Graphon#Analytic Formulation|associated graphon]] <math>W_G</math>, since graphon associated to the complement <math>\overline{G}</math> is <math>W_{\overline{G}}=1 - W_G</math>. Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,<ref>{{Cite journal|last=Borgs|first=C.|last2=Chayes|first2=J. T.|last3=Lovász|first3=L.|last4=Sós|first4=V. T.|last5=Vesztergombi|first5=K.|date=2008-12-20|title=Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing|url=https://www.sciencedirect.com/science/article/pii/S0001870808002053|journal=Advances in Mathematics|language=en|volume=219|issue=6|pages=1801–1851|doi=10.1016/j.aim.2008.07.008|issn=0001-8708}}</ref> <math>W</math> to <math>W_G</math>, and see <math>t(F, W)</math> as roughly the fraction of labeled copies of graph <math>F</math> in "approximate" graph <math>G</math>. Then, we can assume the quantity <math>t(F, W) + t(F, 1 - W)</math> is roughly <math>t(F, G) + t(F, \overline{G})</math> and interpret the latter as the combined number of copies of <math>F</math> in <math>G</math> and <math>\overline{G}</math>. Hence, we see that <math>t(F, G) + t(F, \overline{G}) \gtrsim 2^{-e(F)+1}</math> holds. This, in turn, means that common graph <math>F</math> commonly appears as subgraph.

== Interpretations of definition ==

In other words, if we think of edges and non-edges as [[Edge coloring|2-coloring of edges]] of complete graph on the same vertices, then at least <math>2^{-e(F)}</math> fraction of all possible copies of <math>F</math> are monochromatic. The above definition using the generalized homomorphism density can be understood in this way.

For a graph <math>G</math>, we have <math>t(F, G) = t(F, W_{G}) </math> and <math>t(F, \overline{G})=t(F, 1 - W_G)</math> for the [[Graphon#Analytic Formulation|associated graphon]] <math>W_G</math>, since graphon associated to the complement <math>\overline{G}</math> is <math>W_{\overline{G}}=1 - W_G</math>. Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,<ref>{{Cite journal|lastlast1=Borgs|firstfirst1=C.|last2=Chayes|first2=J. T.|last3=Lovász|first3=L.|authorlink3=László Lovász|last4=Sós|first4=V. T.|authorlink4=Vera T. Sós|last5=Vesztergombi|first5=K.|authorlink5=Katalin Vesztergombi|date=2008-12-20|title=Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing|url=https://www.sciencedirect.com/science/article/pii/S0001870808002053|journal=[[Advances in Mathematics]]|language=en|volume=219|issue=6|pages=1801–1851|doi=10.1016/j.aim.2008.07.008|doi-access=free|s2cid=5974912|issn=0001-8708|arxiv=math/0702004}}</ref> <math>W</math> to <math>W_G</math>, and see <math>t(F, W)</math> as roughly the fraction of labeled copies of graph <math>F</math> in "approximate" graph <math>G</math>. Then, we can assume the quantity <math>t(F, W) + t(F, 1 - W)</math> is roughly <math>t(F, G) + t(F, \overline{G})</math> and interpret the latter as the combined number of copies of <math>F</math> in <math>G</math> and <math>\overline{G}</math>. Hence, we see that <math>t(F, G) + t(F, \overline{G}) \gtrsim 2^{-e(F)+1}</math> holds. This, in turn, means that common graph <math>F</math> commonly appears as subgraph.

In other words, if we think of edges and non-edges as [[Edge coloring|2-coloring of edges]] of complete graph on the same vertices, then at least <math>2^{-e(F)+1}</math> fraction of all possible copies of <math>F</math> are monochromatic. Note that in a [[Erdős–Rényi model|Erdős–Rényi random graph]] <math>G = G(n, p)</math> with each edge drawn with probability <math>p=1/2 </math>, each [[graph homomorphism]] from <math>F</math> to <math>G</math> have probability <math>2 \cdot 2^{-e(F)} = 2^ {-e(F) +1}</math>of being monochromatic. So, common graph <math>F</math> is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph <math>G</math> at the graph <math>G=G(n, p)</math> with <math>p=1/2</math>

<math>p=1/2</math>. The above definition using the generalized homomorphism density can be understood in this way.

== Examples ==

* As stated above, all Sidorenko graphs are common graphs.<ref>{{Cite book|title=Large Networks and Graph Limits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|publisher=American Mathematical Society|page=297}}</ref> Hence, any [[Sidorenko's conjecture#Partial results|known Sidorenko graph]] is an example of a common graph, and, most notably, [[Cycle (graph theory)|cycles of even length]] are common.<ref>{{Cite journal|last=Sidorenko|first=A. F.|date=1992|title=Inequalities for functionals generated by bipartite graphs|url=https://www.degruyter.com/document/doi/10.1515/dma.1992.2.5.489/html|journal=Discrete Mathematics and Applications|volume=2|issue=5|doi=10.1515/dma.1992.2.5.489|s2cid=117471984|issn=0924-9265|url-access=subscription}}</ref> However, these are limited examples since all Sidorenko graphs are [[Bipartite graph|bipartite graphs]] while there exist non-bipartite common graphs, as demonstrated below.

* The [[triangle graph]] <math>K_{3}</math> is aone simple example of non-bipartite common graph.<ref>{{Cite book|title=Large Networks and Graph Limits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|publisher=American Mathematical Society|page=299}}</ref>

* <math>K_4 ^{-}</math>, the graph obtained by removing an edge of the [[complete graph]] on 4 vertices <math>K_4</math>, is common.<ref>{{Cite book|title=Large Networks and Graph Limits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|publisher=American Mathematical Society|page=298}}</ref>

* Non-example: It was believed for a time that all graphs are common. However, Thomasonit turns provedout that <math>K_{t}</math> is not common for <math>t \ge 4</math>.<ref>{{Cite journal|last=Thomason|first=Andrew|date=1989|title=A Disproof of a Conjecture of Erdős in Ramsey Theory|url=https://onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s2-39.2.246|journal=Journal of the London Mathematical Society|language=en|volume=s2-39|issue=2|pages=246–255|doi=10.1112/jlms/s2-39.2.246|issn=1469-7750|url-access=subscription}}</ref> In particular, <math>K_4</math> is not common even though <math>K_{4} ^{-}</math> is common.

== Proofs ==

In this section, we will prove some of the above examples.

===Sidorenko graphs are common===

A graph <math>F</math> is a Sidorenko graph if it satisfies <math>t(F, W) \ge t(K_2, W)^{e(F)}</math> for all graphons <math>W</math>.

RecallIn that a Sidorenko graph <math>F</math> is a graph satisfying <math>t(Fcase, W) \ge t(K_2, W)^{e(F)}</math> for all graphons <math>W</math>. Hence, we should also have <math>t(F, 1 - W) \ge t(K_2, 1 - W)^{e(F)}</math>. NowFurthermore, observe that <math>t(K_2, W) + t(K_2, 1 - W) = 1 </math>, which follows from the definition of homomorphism density. Combining this with [[Jensen's inequality]] for the function <math>f(x) = x^{e(F)}</math>, we can see that :

<math>t(F, W) + t(F, 1 - W) \ge t(K_2, W)^{e(F)} + t(K_2, 1 - W)^{e(F)}

\ge 2 \bigg( \frac{t(K_2, W) + t(K_2, 1 - W)}{2} \bigg)^{e(F)} = 2^{-e(F) + 1}</math>

Thus, the conditions for common graph is met.<ref>{{Cite book|last=Lovász|first=László|title=Large Networks and Graph Limits|publisher=American Mathematical Society Colloquium publications|year=2012|isbn=978-0821890851|___location=United States|pages=297–298|language=English}}</ref>

Thus, the conditions for common graph is met.

===The triangle graph is common===

Here, we will expandExpand the integral expression for <math>t(K_3, 1 - W)</math> and take into account the symmetry between the variables:

Here, we will expand the integral expression for <math>t(K_3, 1 - W)</math> and take into account the symmetry between the variables:

<math>\int_{[0, 1]^3} (1 - W(x, y))(1 - W(y, z))(1 - W(z, x)) dx dy dz

= 1 - 3 \int_{[0, 1]^2} W(x, y) + 3 \int_{[0, 1]^3} W(x, y) W(x, z) dx dy dz - \int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz</math>

Now, observe that eachEach term in the expression can be written in terms of homomorphism densities of smaller graphs. Indeed, byBy the definition of homomorphism densities, we have:

:<math>\int_{[0, 1]^2} W(x, y) dx dy = t(K_2, W) </math>

:<math>\int{[0, 1]^3} W(x, y) W(x, z) dx dy dz = t(K_{1, 2}, W) </math>

:<math>\int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W)</math>

: <math>\int_{[0, 1]^2} W(x, y) dx dy = t(K_2, W) </math>

(Note that <math>K_{1, 2}</math> denotes the [[complete bipartite graph]] on <math>1</math> vertex on one part and <math>2</math> vertices on the other.) Hence, we get:

: <math>t(K_3\int{[0, 1]^3} W) + t(K_3x, 1 -y) W) = 1 - 3 t(K_2x, Wz) +dx 3dy dz = t(K_{1, 2}, W) </math>.

: <math>\intint_{[0, 1]^3} W(x, y) W(xy, z) W(z, x) dx dy dz = t(K_{1, 2}K_3, W) </math>

Now, in order to relatewhere <math>t(K_{1, 2}, W)</math> to <math>t(K_2, W)</math>, note that we can exploitdenotes the symmetry[[complete betweenbipartite thegraph]] variableson <math>y 1</math> vertex on one part and <math>z2</math> tovertices on the other. It writefollows:

: <math>t(K_3, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) </math>.

<math display=block>\begin{alignat}{4}

<math>t(K_{1, 2}, W)</math> can be related to <math>t(K_2, W)</math> thanks to the symmetry between the variables <math>y </math> and <math>z</math>:

<math display="block">\begin{alignat}{4}

t(K_{1, 2}, W) &= \int_{[0, 1]^3} W(x, y) W(x, z) dx dy dz && \\

&= \int_{x \in [0, 1]} \bigg( \int_{y \in [0, 1]} W(x, y) \bigg) \bigg( \int_{z \in [0, 1]} W(x, z) \bigg) && \\

Line 69 ⟶ 64:

\end{alignat}</math>

where wethe usedlast step follows from the integral [[Cauchy–Schwarz inequality]] in the last step. Finally, our desired result follows from the above inequality:

<math>t(K_3, W) + t(K_3, 1 - W) \ge 1 - 3 t(K_2, W) + 3 t(K_{2}, W)^2

= 1/4 + 3 \big( t(K_2, W) - 1/2 \big)^2 \ge 1/4</math>.

This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"<ref>{{Cite journal|last=Goodman|first=A. W.|date=1959|title=On Sets of Acquaintances and Strangers at any Party|url=https://www.jstor.org/stable/2310464|journal=The American Mathematical Monthly|volume=66|issue=9|pages=778–783|doi=10.2307/2310464|jstor=2310464|issn=0002-9890|url-access=subscription}}</ref>

== See also ==

Line 79 ⟶ 76:

== References ==

<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->

{{reflist}}

[[Category:Graph families]]

[[Category:Extremal graph theory]]