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 $\overline$ 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$ 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^$

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_)$ and $t(F, \overline)=t(F, 1 - W_G)$ for the associated graphon $W_G$, since graphon associated to the complement $\overline$ is $W_=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, \overline)$ and interpret the latter as the combined number of copies of $F$ in $G$ and $\overline$. Hence, we see that $t(F, G) + t(F, \overline) \gtrsim 2^$ 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^$ 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^ = 2^$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_$ 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_$ is not common for $t \ge 4$. In particular, $K_4$ is not common even though $K_ ^$ 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)^$ for all graphons $W$.

In that case, $t(F, 1 - W) \ge t(K_2, 1 - W)^$. 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^$:

$t(F, W) + t(F, 1 - W) \ge t(K_2, W)^ + t(K_2, 1 - W)^ \ge 2 \bigg( \frac \bigg)^ = 2^$

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:

$\int_ (1 - W(x, y))(1 - W(y, z))(1 - W(z, x)) dx dy dz = 1 - 3 \int_ W(x, y) + 3 \int_ W(x, y) W(x, z) dx dy dz - \int_ 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_ W(x, y) dx dy = t(K_2, W)$
: $\int W(x, y) W(x, z) dx dy dz = t(K_, W)$
: $\int_ W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W)$

where $K_$ 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_, W)$.

$t(K_, W)$ can be related to $t(K_2, W)$ thanks to the symmetry between the variables $y$ and $z$:
$\begin t(K_, W) &= \int_ W(x, y) W(x, z) dx dy dz && \\ &= \int_ \bigg( \int_ W(x, y) \bigg) \bigg( \int_ W(x, z) \bigg) && \\ &= \int_ \bigg( \int_ W(x, y) \bigg)^2 && \\ &\ge \bigg( \int_ \int_ W(x, y) \bigg)^2 = t(K_2, W)^2 \end$

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_, W)^2 = 1/4 + 3 \big( t(K_2, W) - 1/2 \big)^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

References

{{reflist

Graph families
Extremal graph theory