Common graph: Difference between revisions

Revision as of 21:30, 4 February 2022

Revision as of 01:05, 12 February 2022

Line 23:

<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]] (see the book "''Large Networks and Graph Limits''"<ref>{{Cite web|title=Large Networks and Graph Limits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|website=bookstore.ams.org}}</ref> and a survey "''Very Large Graphs''"<ref>{{Cite journal|last=Lovasz|first=Laszlo|date=2009-02-01|title=Very large graphs|url=http://arxiv.org/abs/0902.0132|journal=arXiv:0902.0132 [math]|arxiv=0902.0132}}</ref> , both by [[László Lovász]], for introduction to the theory of [[graph limits]]). Here, note that the inequality attains the lower bound when <math>W</math> is the constant graphon <math>W \equiv 1/2</math>. So, the inequality is tight.       

== Interpretations of definition ==

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.|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|s2cid=5974912|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)+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>

Line 34:

== Examples ==

* As stated above, all Sidorenko graphs are common graphs. 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}}</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.

* <math>K_4 ^{-}</math>, the graph obtained by removing an edge of the [[complete graph]] on 4 vertices <math>K_4</math>, is common.

Line 48:

\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. This proof, along with proof of <math>K_4^{-}</math> being common graph, can be seen from page 297-298 of the aforementioned book of László Lovász<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-298297–298|language=English}}</ref>.

===The triangle graph is common===

Line 76:

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

This above proof can be obtained from taking continuous analog of Theorem 1 in Goodman 1959 paper, "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}}</ref>.

== See also ==