Common graph: Difference between revisions

Revision as of 02:54, 29 November 2021

Latest revision as of 22:26, 26 May 2025

(25 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Concept in extremal graph theory}}

{{AfC submission|t||ts=20211129025414|u=Unubold Lake Munkhbat Choros|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

'''Common graphs''' appear inIn [[graph theory]], andan itarea of mathematics, '''common graphs''' belongsbelong to a branch of [[extremal graph theory]] concerning [[Homomorphism density|inequalities in homomorphism densities]]. Roughly speaking, common graph <math>F</math> is a common [[Graph (discrete mathematics)|graph]] thatif it "commonly" appears as a subgraph, in a sense that the total number of copies of <math>F</math> one can find in any graph <math>G</math> and it'sits [[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> doesn't containcontains manyfew 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]]). Indeed, we will prove below that all Sidorenko graphs are common graphs.

== Definition ==

Formally, definition of common graph is aA graph <math>F </math> suchis common if thatthe inequality:

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

inequality 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 graphon <math>W \equivGraph 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>.

Now let's try to build intuition to better understand this definition. For a graph <math>G</math>, we would 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 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. 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.

== Interpretations of definition ==

Now let's try to build intuition to better understand this definition. For a graph <math>G</math>, we would 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)}</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.

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 automatically becomesare common graphs.<ref>{{Cite Hence,book|title=Large allNetworks graphsand notedGraph inLimits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|publisher=American Mathematical Society|page=297}}</ref> Hence, thisany [[Sidorenko's conjecture#Partial results|partial list of known Sidorenko graphsgraph]] areis an example of a common graphsgraph, and, most notably, [[Cycle (graph theory)|cycles of even length]] are common.<ref>{{Cite graphjournal|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 one 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>

* An interesting example of a common graph is the <math>K_4 ^{-}</math>, the graph obtained by removing an edge of the [[complete graph]] on 4 vertices <math>4K_4</math>, verticesis common.<mathref>K_4{{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}}</mathref>.

* Non-example: It was believed for a time that all graphs are common graphs. However, it came as a surprise when Thomasonturns 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.

'''Proposition 1. ===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.

'''Proposition 2. ===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> and <math>\int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, 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, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) </math>. :

: <math>t(K_{1, 2}, W)= \int_{[0, 1]^32} W(x, y) Wdx dy = t(xK_2, zW) dx dy dz </math>

Now, in order to relate <math>t(K_{1, 2}, W)</math> to <math>t(K_2, W)</math>, note that we can exploit the symmetry between the variables <math>y </math> and <math>z</math> to write

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

\ge \bigg(: <math>\int_{x \in [0, 1]^3} \int_{W(x, y) \in [0W(y, 1]}z) W(xz, yx) \bigg)^2dx dy dz = t(K_2K_3, W)^2</math>

where <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. It follows:

<math>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)

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

\ge \bigg( \int_{x \in [0, 1]} \int_{y \in [0, 1]} W(x, y) \bigg)^2 = t(K_2, W)^2</math>

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

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

Now, in order to relate <math>t(K_{1, 2}, W)</math> can be related to <math>t(K_2, W)</math>, notethanks that we can exploitto the symmetry between the variables <math>y </math> and <math>z</math> to write :

<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) && \\

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

&\ge \bigg( \int_{x \in [0, 1]} \int_{y \in [0, 1]} W(x, y) \bigg)^2 = t(K_2, W)^2

\end{alignat}</math>

where the last step follows from the integral [[Cauchy–Schwarz inequality]]. Finally:

<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 59 ⟶ 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]]