In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of in any graph and its complement is a large fraction of all possible copies of on the same vertices. Intuitively, if contains few copies of , then its complement must contain lots of copies of 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.

Definition

edit

A graph   is common if the inequality:

 

holds for any graphon  , where   is the number of edges of   and   is the homomorphism density.[1]

The inequality is tight because the lower bound is always reached when   is the constant graphon  .

Interpretations of definition

edit

For a graph  , we have   and   for the associated graphon  , since graphon associated to the complement   is  . Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,[2]   to  , and see   as roughly the fraction of labeled copies of graph   in "approximate" graph  . Then, we can assume the quantity   is roughly   and interpret the latter as the combined number of copies of   in   and  . Hence, we see that   holds. This, in turn, means that common graph   commonly appears as subgraph.

In other words, if we think of edges and non-edges as 2-coloring of edges of complete graph on the same vertices, then at least   fraction of all possible copies of   are monochromatic. Note that in a Erdős–Rényi random graph   with each edge drawn with probability  , each graph homomorphism from   to   have probability  of being monochromatic. So, common graph   is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph   at the graph   with  

 . The above definition using the generalized homomorphism density can be understood in this way.

Examples

edit
  • As stated above, all Sidorenko graphs are common graphs.[3] Hence, any known Sidorenko graph is an example of a common graph, and, most notably, cycles of even length are common.[4] However, these are limited examples since all Sidorenko graphs are bipartite graphs while there exist non-bipartite common graphs, as demonstrated below.
  • The triangle graph   is one simple example of non-bipartite common graph.[5]
  •  , the graph obtained by removing an edge of the complete graph on 4 vertices  , is common.[6]
  • Non-example: It was believed for a time that all graphs are common. However, it turns out that   is not common for  .[7] In particular,   is not common even though   is common.

Proofs

edit

Sidorenko graphs are common

edit

A graph   is a Sidorenko graph if it satisfies   for all graphons  .

In that case,  . Furthermore,  , which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function  :

 

Thus, the conditions for common graph is met.[8]

The triangle graph is common

edit

Expand the integral expression for   and take into account the symmetry between the variables:

 

Each term in the expression can be written in terms of homomorphism densities of smaller graphs. By the definition of homomorphism densities:

 
 
 

where   denotes the complete bipartite graph on   vertex on one part and   vertices on the other. It follows:

 .

  can be related to   thanks to the symmetry between the variables   and  :  

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

 .

This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"[9]

See also

edit

References

edit
  1. ^ Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.
  2. ^ Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K. (2008-12-20). "Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing". Advances in Mathematics. 219 (6): 1801–1851. arXiv:math/0702004. doi:10.1016/j.aim.2008.07.008. ISSN 0001-8708. S2CID 5974912.
  3. ^ Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.
  4. ^ Sidorenko, A. F. (1992). "Inequalities for functionals generated by bipartite graphs". Discrete Mathematics and Applications. 2 (5). doi:10.1515/dma.1992.2.5.489. ISSN 0924-9265. S2CID 117471984.
  5. ^ Large Networks and Graph Limits. American Mathematical Society. p. 299. Retrieved 2022-01-13.
  6. ^ Large Networks and Graph Limits. American Mathematical Society. p. 298. Retrieved 2022-01-13.
  7. ^ Thomason, Andrew (1989). "A Disproof of a Conjecture of Erdős in Ramsey Theory". Journal of the London Mathematical Society. s2-39 (2): 246–255. doi:10.1112/jlms/s2-39.2.246. ISSN 1469-7750.
  8. ^ Lovász, László (2012). Large Networks and Graph Limits. United States: American Mathematical Society Colloquium publications. pp. 297–298. ISBN 978-0821890851.
  9. ^ Goodman, A. W. (1959). "On Sets of Acquaintances and Strangers at any Party". The American Mathematical Monthly. 66 (9): 778–783. doi:10.2307/2310464. ISSN 0002-9890. JSTOR 2310464.