Common graph: Difference between revisions

Revision as of 03:40, 28 May 2022

Revision as of 11:56, 24 June 2022

Line 6:

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

Line 12:

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]].<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>

Here,The noteinequality thatis thetight inequalitybecause it always 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 ==