Common graph: Difference between revisions

Revision as of 18:58, 24 May 2022

Revision as of 15:53, 27 May 2022

Line 10:

<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 webbook|title=Large Networks and Graph Limits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|websitepublisher=bookstore.ams.org}}</ref>American and a survey "''Very Large Graphs''"<ref>{{CiteMathematical journalSociety|lastpage=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.0132297}}</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.       

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 ==

Line 21 ⟶ 23:

== 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}}</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=297}}</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=297}}</ref>

* Non-example: It was believed for a time that all graphs are common. However, shockingly, it turns out that <math>K_{t}</math> is not common for <math>t \ge 4</math>, as proved by Thomason in 1989.<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}}</ref> In particular, <math>K_4</math> is not common even though <math>K_{4} ^{-}</math> is common.

== Proofs ==

Line 35 ⟶ 37:

\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–298|language=English}}</ref>.

===The triangle graph is common===