Common graph

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 $\bar{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 $\bar{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}$ holds for any graphon $W$, where $e(F)$ is the number of edges of $F$ and $t(F,W)$ is the homomorphism density. 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,\bar{G})=t(F,1-W_G)$ for the associated graphon $W_G$, since graphon associated to the complement $\bar{G}$ is $W_{\bar{G}}=1-W_G$. Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means, $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,\bar{G})$ and interpret the latter as the combined number of copies of $F$ in $G$ and $\bar{G}$. Hence, we see that $t(F,G)+t(F,\bar{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\cdot 2^{-e(F)}=2^{-e(F)+1}$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. Hence, any known Sidorenko graph is an example of a common graph, and, most notably, cycles of even length are common. 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 $K_3$ is one simple example of non-bipartite common graph.
• $K_4^{-}$, the graph obtained by removing an edge of the complete graph on 4 vertices $K_4$, is common.
• 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$. 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(\frac{t(K_2,W)+t(K_2,1-W)}{2}{)}^{e(F)}=2^{-e(F)+1}$ Thus, the conditions for common graph is met.

The triangle graph is common

Expand the integral expression for $t(K_3,1-W)$ and take into account the symmetry between the variables: $\underset{[0,1{]}^3}{\int }(1-W(x,y))(1-W(y,z))(1-W(z,x))dxdydz=1-3\underset{[0,1{]}^2}{\int }W(x,y)+3\underset{[0,1{]}^3}{\int }W(x,y)W(x,z)dxdydz-\underset{[0,1{]}^3}{\int }W(x,y)W(y,z)W(z,x)dxdydz$ Each term in the expression can be written in terms of homomorphism densities of smaller graphs. By the definition of homomorphism densities:

$\underset{[0,1{]}^2}{\int }W(x,y)dxdy=t(K_2,W)$

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

$\underset{[0,1{]}^3}{\int }W(x,y)W(y,z)W(z,x)dxdydz=t(K_3,W)$

where $K_{1,2}$ 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-3t(K_2,W)+3t(K_{1,2},W)$.

$t(K_{1,2},W)$ can be related to $t(K_2,W)$ thanks to the symmetry between the variables $y$ and $z$: $$\begin{array}{rlrl}t(K_{1,2},W)& =\underset{[0,1{]}^3}{\int }W(x,y)W(x,z)dxdydz& & \\ & =\underset{x\in [0,1]}{\int }(\underset{y\in [0,1]}{\int }W(x,y))(\underset{z\in [0,1]}{\int }W(x,z))& & \\ & =\underset{x\in [0,1]}{\int }(\underset{y\in [0,1]}{\int }W(x,y){)}^2& & \\ & \ge (\underset{x\in [0,1]}{\int }\underset{y\in [0,1]}{\int }W(x,y){)}^2=t(K_2,W{)}^2\end{array}$$ where the last step follows from the integral Cauchy–Schwarz inequality. Finally: $t(K_3,W)+t(K_3,1-W)\ge 1-3t(K_2,W)+3t(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"

See also

• Sidorenko's conjecture