Common graph: Difference between revisions

Revision as of 15:53, 27 May 2022

Revision as of 16:31, 27 May 2022

Line 24:

* 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=297299}}</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=297298}}</ref>

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