Common graph

Short description: Concept in extremal graph theory

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

[math]\displaystyle{ t(F, W) + t(F, 1 - W) \ge 2^{-e(F)+1} }[/math]

holds for any graphon [math]\displaystyle{ W }[/math], where [math]\displaystyle{ e(F) }[/math] is the number of edges of [math]\displaystyle{ F }[/math] and [math]\displaystyle{ t(F, W) }[/math] is the homomorphism density.

The inequality is tight because the lower bound is always reached when [math]\displaystyle{ W }[/math] is the constant graphon [math]\displaystyle{ W \equiv 1/2 }[/math].

Interpretations of definition

For a graph [math]\displaystyle{ G }[/math], we have [math]\displaystyle{ t(F, G) = t(F, W_{G}) }[/math] and [math]\displaystyle{ t(F, \overline{G})=t(F, 1 - W_G) }[/math] for the associated graphon [math]\displaystyle{ W_G }[/math], since graphon associated to the complement [math]\displaystyle{ \overline{G} }[/math] is [math]\displaystyle{ W_{\overline{G}}=1 - W_G }[/math]. Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means, [math]\displaystyle{ W }[/math] to [math]\displaystyle{ W_G }[/math], and see [math]\displaystyle{ t(F, W) }[/math] as roughly the fraction of labeled copies of graph [math]\displaystyle{ F }[/math] in "approximate" graph [math]\displaystyle{ G }[/math]. Then, we can assume the quantity [math]\displaystyle{ t(F, W) + t(F, 1 - W) }[/math] is roughly [math]\displaystyle{ t(F, G) + t(F, \overline{G}) }[/math] and interpret the latter as the combined number of copies of [math]\displaystyle{ F }[/math] in [math]\displaystyle{ G }[/math] and [math]\displaystyle{ \overline{G} }[/math]. Hence, we see that [math]\displaystyle{ t(F, G) + t(F, \overline{G}) \gtrsim 2^{-e(F)+1} }[/math] holds. This, in turn, means that common graph [math]\displaystyle{ F }[/math] 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 [math]\displaystyle{ 2^{-e(F)+1} }[/math] fraction of all possible copies of [math]\displaystyle{ F }[/math] are monochromatic. Note that in a Erdős–Rényi random graph [math]\displaystyle{ G = G(n, p) }[/math] with each edge drawn with probability [math]\displaystyle{ p=1/2 }[/math], each graph homomorphism from [math]\displaystyle{ F }[/math] to [math]\displaystyle{ G }[/math] have probability [math]\displaystyle{ 2 \cdot 2^{-e(F)} = 2^ {-e(F) +1} }[/math]of being monochromatic. So, common graph [math]\displaystyle{ F }[/math] is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph [math]\displaystyle{ G }[/math] at the graph [math]\displaystyle{ G=G(n, p) }[/math] with [math]\displaystyle{ p=1/2 }[/math]

[math]\displaystyle{ p=1/2 }[/math]. 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 [math]\displaystyle{ K_{3} }[/math] is one simple example of non-bipartite common graph.
• [math]\displaystyle{ K_4 ^{-} }[/math], the graph obtained by removing an edge of the complete graph on 4 vertices [math]\displaystyle{ K_4 }[/math], is common.
• Non-example: It was believed for a time that all graphs are common. However, it turns out that [math]\displaystyle{ K_{t} }[/math] is not common for [math]\displaystyle{ t \ge 4 }[/math]. In particular, [math]\displaystyle{ K_4 }[/math] is not common even though [math]\displaystyle{ K_{4} ^{-} }[/math] is common.

Proofs

Sidorenko graphs are common

A graph [math]\displaystyle{ F }[/math] is a Sidorenko graph if it satisfies [math]\displaystyle{ t(F, W) \ge t(K_2, W)^{e(F)} }[/math] for all graphons [math]\displaystyle{ W }[/math].

In that case, [math]\displaystyle{ t(F, 1 - W) \ge t(K_2, 1 - W)^{e(F)} }[/math]. Furthermore, [math]\displaystyle{ t(K_2, W) + t(K_2, 1 - W) = 1 }[/math], which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function [math]\displaystyle{ f(x) = x^{e(F)} }[/math]:

[math]\displaystyle{ t(F, W) + t(F, 1 - W) \ge t(K_2, W)^{e(F)} + t(K_2, 1 - W)^{e(F)} \ge 2 \bigg( \frac{t(K_2, W) + t(K_2, 1 - W)}{2} \bigg)^{e(F)} = 2^{-e(F) + 1} }[/math]

Thus, the conditions for common graph is met.

The triangle graph is common

Expand the integral expression for [math]\displaystyle{ t(K_3, 1 - W) }[/math] and take into account the symmetry between the variables:

[math]\displaystyle{ \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 }[/math]

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

[math]\displaystyle{ \int_{[0, 1]^2} W(x, y) dx dy = t(K_2, W) }[/math]

[math]\displaystyle{ \int{[0, 1]^3} W(x, y) W(x, z) dx dy dz = t(K_{1, 2}, W) }[/math]

[math]\displaystyle{ \int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W) }[/math]

where [math]\displaystyle{ K_{1, 2} }[/math] denotes the complete bipartite graph on [math]\displaystyle{ 1 }[/math] vertex on one part and [math]\displaystyle{ 2 }[/math] vertices on the other. It follows:

[math]\displaystyle{ t(K_3, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) }[/math].

[math]\displaystyle{ t(K_{1, 2}, W) }[/math] can be related to [math]\displaystyle{ t(K_2, W) }[/math] thanks to the symmetry between the variables [math]\displaystyle{ y }[/math] and [math]\displaystyle{ z }[/math]: [math]\displaystyle{ \begin{alignat}{4} t(K_{1, 2}, W) &= \int_{[0, 1]^3} W(x, y) W(x, z) dx dy dz && \\ &= \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 && \\ &\ge \bigg( \int_{x \in [0, 1]} \int_{y \in [0, 1]} W(x, y) \bigg)^2 = t(K_2, W)^2 \end{alignat} }[/math]

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

[math]\displaystyle{ 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 \big( t(K_2, W) - 1/2 \big)^2 \ge 1/4 }[/math].

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