Common graph

Common graphs appear in graph theory, and it belongs to branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, common graph ${\displaystyle F}$ is a graph that "commonly" appears as a subgraph, in a sense that the total number of copies of ${\displaystyle F}$ one can find in any graph ${\displaystyle G}$ and it's complement ${\displaystyle {\overline {G}}}$ is a large fraction of all possible copies of ${\displaystyle F}$ on the same vertices. Intuitively, if ${\displaystyle G}$ doesn't contain many copies of ${\displaystyle F}$, then its complement ${\displaystyle {\overline {G}}}$ must contain lots of copies of ${\displaystyle 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 (graphs with Sidorenko's property). Indeed, we will prove below that all Sidorenko graphs are common graphs.

Definition

Formally, definition of common graph is a graph ${\displaystyle F}$  such that

${\displaystyle t(F,W)+t(F,1-W)\geq 2^{-e(F)+1}}$ 

inequality holds for any graphon ${\displaystyle W}$ , where ${\displaystyle e(F)}$  is the number of edges of ${\displaystyle F}$  and ${\displaystyle t(F,W)}$  is the homomorphism density . Here, note that the inequality attains the lower bound when ${\displaystyle W}$  is the constant graphon ${\displaystyle W\equiv 1/2}$ . So, the inequality is tight.

Now let's try to build intuition to better understand this definition. For a graph ${\displaystyle G}$ , we would have ${\displaystyle t(F,G)=t(F,W_{G})}$  and ${\displaystyle t(F,{\overline {G}})=t(F,1-W_{G})}$  for the associated graphon ${\displaystyle W_{G}}$ , since graphon associated to the complement ${\displaystyle {\overline {G}}}$  is ${\displaystyle W_{\overline {G}}=1-W_{G}}$ . Hence, this formula provides us with the very informal intuition to take close enough approximation, whatever that means^[1], ${\displaystyle W}$  to ${\displaystyle W_{G}}$  and see ${\displaystyle t(F,W)}$  as roughly the fraction of labeled copies of graph ${\displaystyle F}$  in "approximate" graph ${\displaystyle G}$ . Then, we can assume the quantity ${\displaystyle t(F,W)+t(F,1-W)}$  is roughly ${\displaystyle t(F,G)+t(F,{\overline {G}})}$  and interpret the latter as the combined number of copies of ${\displaystyle F}$  in ${\displaystyle G}$  and ${\displaystyle {\overline {G}}}$ . Hence, we see that ${\displaystyle t(F,G)+t(F,{\overline {G}})\gtrsim 2^{-e(F)+1}}$  holds. This, in turn, means that common graph ${\displaystyle 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 ${\displaystyle 2^{-e(F)}}$  fraction of all possible copies of ${\displaystyle F}$  are monochromatic. The above definition using the generalized homomorphism density can be understood in this way.

Examples

• As stated above, all Sidorenko graphs automatically becomes common graphs. Hence, all graphs noted in this partial list of known Sidorenko graphs are common graphs, and, most notably, cycles of even length are common graph. 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 ${\displaystyle K_{3}}$  is one simple example of non-bipartite common graph.
• An interesting example of a common graph is the ${\displaystyle K_{4}^{-}}$  graph obtained by removing an edge of complete graph on ${\displaystyle 4}$  vertices ${\displaystyle K_{4}}$ .
• Non-example: It was believed for a time that all graphs are common graphs. However, it came as a surprise when Thomason proved that ${\displaystyle K_{t}}$  is not common for ${\displaystyle t\geq 4}$ .^[2] In particular, ${\displaystyle K_{4}}$  is not common even though ${\displaystyle K_{4}^{-}}$  is common.

Proofs

In this section, we will prove some of the above examples.

Proposition 1. Sidorenko graphs are common.

Recall that a Sidorenko graph ${\displaystyle F}$  is a graph satisfying ${\displaystyle t(F,W)\geq t(K_{2},W)^{e(F)}}$  for all graphons ${\displaystyle W}$ . Hence, we should also have ${\displaystyle t(F,1-W)\geq t(K_{2},1-W)^{e(F)}}$ . Now, observe that ${\displaystyle 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 ${\displaystyle f(x)=x^{e(F)}}$ , we can see that

${\displaystyle t(F,W)+t(F,1-W)\geq t(K_{2},W)^{e(F)}+t(K_{2},1-W)^{e(F)}\geq 2{\bigg (}{\frac {t(K_{2},W)+t(K_{2},1-W)}{2}}{\bigg )}^{e(F)}=2^{-e(F)+1}}$ 

Thus, the conditions for common graph is met.

Proposition 2. The triangle graph is common.

Here, we will expand the integral expression for ${\displaystyle t(K_{3},1-W)}$  and take into account the symmetry between the variables :

${\displaystyle \int _{[0,1]^{3}}(1-W(x,y))(1-W(y,z))(1-W(z,x))dxdydz=1-3\int _{[0,1]^{2}}W(x,y)+3\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz-\int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz}$ 

Now, observe that each term in the expression can be written in terms of homomorphism densities of smaller graphs. Indeed, by the definition of homomorphism densities, we have ${\displaystyle \int _{[0,1]^{2}}W(x,y)dxdy=t(K_{2},W)}$ , ${\displaystyle \int {[0,1]^{3}}W(x,y)W(x,z)dxdydz=t(K_{1,2},W)}$  and ${\displaystyle \int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz=t(K_{3},W)}$  (note that ${\displaystyle K_{1,2}}$  denotes the complete bipartite graph on ${\displaystyle 1}$  vertex on one part and ${\displaystyle 2}$  vertices on the other). Hence, we get ${\displaystyle t(K_{3},W)+t(K_{3},1-W)=1-3t(K_{2},W)+3t(K_{1,2},W)}$ .

Now, in order to relate ${\displaystyle t(K_{1,2},W)}$  to ${\displaystyle t(K_{2},W)}$ , note that we can exploit the symmetry between the variables ${\displaystyle y}$  and ${\displaystyle z}$  to write

${\displaystyle t(K_{1,2},W)=\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz=\int _{x\in [0,1]}{\bigg (}\int _{y\in [0,1]}W(x,y){\bigg )}{\bigg (}\int _{z\in [0,1]}W(x,z){\bigg )}=\int _{x\in [0,1]}{\bigg (}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}\geq {\bigg (}\int _{x\in [0,1]}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}=t(K_{2},W)^{2}}$ 

where we used the integral Cauchy–Schwarz inequality in the last step. Finally, our desired result follows from the above inequality :

${\displaystyle t(K_{3},W)+t(K_{3},1-W)\geq 1-3t(K_{2},W)+3t(K_{2},W)^{2}=1/4+3{\big (}t(K_{2},W)-1/2{\big )}^{2}\geq 1/4}$ 

See also

• Sidorenko's conjecture

References

1. 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. doi:10.1016/j.aim.2008.07.008. ISSN 0001-8708.
2. 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.