Common graph explained

In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking,

F is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of F in any graph G and its complement \overline{G} is a large fraction of all possible copies of F on the same vertices. Intuitively, if G contains few copies of F , then its complement \overline{G} must contain lots of copies of F 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

A graph

F is common if the inequality:t(F, W) + t(F, 1 - W) \ge 2 ^{-e(F)+1} W , where e(F) is the number of edges of F and t(F, W) is the homomorphism density.^[1]

The inequality is tight because the lower bound is always reached when

W is the constant graphon W \equiv 1 / 2 .

Interpretations of definition

For a graph

G , we have t(F, G) = t(F, W _{G} ) and t(F, \overline{G}) = t(F, 1 - W _{G)} for the associated graphon W _{G} , since graphon associated to the complement \overline{G} is W _{\overline{G} }=1 - W_G. Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,^[2] W to W _{G} , and see t(F, W) as roughly the fraction of labeled copies of graph F in "approximate" graph G . Then, we can assume the quantity t(F, W) + t(F, 1 - W) is roughly t(F, G) + t(F, \overline{G}) and interpret the latter as the combined number of copies of F in G and \overline{G} . Hence, we see that t(F, G) + t(F, \overline{G}) \gtrsim 2 ^{-e(F)+1} holds. This, in turn, means that common graph F 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

2 ^{-e(F)+1} fraction of all possible copies of F are monochromatic. Note that in a Erdős–Rényi random graph G = G(n, p) with each edge drawn with probability p =1 / 2 , each graph homomorphism from F to G have probability 2 ⋅ 2 ^{-e(F)} = 2 ^{-e(F)} of being monochromatic. So, common graph F is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph G at the graph G = G(n, p) with p =1 / 2 p =1 / 2 . The above definition using the generalized homomorphism density can be understood in this way.

Examples

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

K _{3} is one simple example of non-bipartite common graph.^[5] K ^{-} _{4} , the graph obtained by removing an edge of the complete graph on 4 vertices K _{4} , is common.^[6]

• Non-example: It was believed for a time that all graphs are common. However, it turns out that

K _{t} is not common for t \ge 4 .^[7] In particular, K _{4} is not common even though K _{4} ^{-} is common.

Proofs

Sidorenko graphs are common

A graph

F is a Sidorenko graph if it satisfies t(F, W) \ge t(K _{2,} W) ^{e(F)} for all graphons W .

In that case,

t(F, 1 - W) \ge t(K _{2,} 1 - W) ^{e(F)} . Furthermore, t(K _{2,} W) + t(K _{2,} 1 - W) = 1 , which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function f(x) = x ^{e(F)} :t(F, W) + t(F, 1 - W) \ge t(K _{2,} W) ^{e(F)} + t(K _{2,} 1 - W) ^{e(F)} \ge 2 ( (t(K _{2,} W) + t(K _{2,} 1- W))/(2) ) ^{e(F)} = 2 ^{-e(F)}

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

The triangle graph is common

Expand the integral expression for

t(K _{3,} 1 - W) and take into account the symmetry between the variables:\int _{[ 0 , 1 ] ^{3}} ( 1 - W(x, y))( 1 - W(y, z))( 1 - W(z, x)) dx dy dz = 1 - 3 \int _{[ 0 , 1 ] ^{2}} W(x, y) + 3 \int _{[ 0 , 1 ] ^{3}} W(x, y) W(x, z) dx dy dz - \int _{[ 0 , 1 ] ^{3}} W(x, y) W(y, z) W(z, x) dx dy dz

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

\int _{[ 0 , 1 ] ^{2}} W(x, y) dx dy = t(K _{2,} W) \int{[ 0 , 1 ] ^{3}} W(x, y) W(x, z) dx dy dz = t(K _{1,} , W) \int _{[ 0 , 1 ] ^{3}} W(x, y) W(y, z) W(z, x) dx dy dz = t(K _{3,} W)

where

K _{1,} denotes the complete bipartite graph on 1 vertex on one part and 2 vertices on the other. It follows:t(K _{3,} W) + t(K _{3,} 1 - W) = 1 - 3 t(K _{2,} W) + 3 t(K _{1,} , W) .t(K _{1,} , W) can be related to t(K _{2,} W) thanks to the symmetry between the variables y and z :

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

t(K _{3,} W) + t(K _{3,} 1 - W) \ge 1 - 3 t(K _{2,} W) + 3 t(K _{2} , W) ^{2} = 1 / 4 + 3 ( t(K _{2,} W) - 1 / 2 ) ^{2} \ge 1 / 4 .

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

• Sidorenko's conjecture

Notes and References

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