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{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 (graphs with Sidorenko's property).

Definition

Formally, a common graph is a graph $F$ such that the inequality:

$t (F, W) + t (F, 1 - W) \geq 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 (see the book "Large Networks and Graph Limits"^[1] and a survey "Very Large Graphs"^[2] , both by László Lovász, for introduction to the theory of graph limits). Here, note that the inequality attains the lower bound when $W$ is the constant graphon $W \equiv 1 / 2$ . So, the inequality is tight.

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,^[3] $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}) ≳ 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^[4].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, shockingly, it turns out that $K_{t}$ is not common for $t \geq 4$ , as proved by Thomason in 1989.^[5] In particular, $K_{4}$ is not common even though $K_{4}^{-}$ is common.

Proofs

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

Sidorenko graphs are common

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

$t (F, W) + t (F, 1 - W) \geq t (K_{2}, W)^{e (F)} + t (K_{2}, 1 - W)^{e (F)} \geq 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. This proof, along with proof of $K_{4}^{-}$ being common graph, can be seen from page 297-298 of the aforementioned book of László Lovász^[6].

The triangle graph is common

Here, we will 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)) d x d y d z = 1 - 3 \int_{[0, 1]^{2}} W (x, y) + 3 \int_{[0, 1]^{3}} W (x, y) W (x, z) d x d y d z - \int_{[0, 1]^{3}} W (x, y) W (y, z) W (z, x) d x d y d z$

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:

\int_{[0, 1]^{2}} W (x, y) d x d y = t (K_{2}, W)

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

\int_{[0, 1]^{3}} W (x, y) W (y, z) W (z, x) d x d y d z = t (K_{3}, W)

(Note that $K_{1, 2}$ denotes the complete bipartite graph on $1$ vertex on one part and $2$ vertices on the other.) Hence, we get:

t (K_{3}, W) + t (K_{3}, 1 - W) = 1 - 3 t (K_{2}, W) + 3 t (K_{1, 2}, W)

.

Now, in order to relate $t (K_{1, 2}, W)$ to $t (K_{2}, W)$ , note that we can exploit the symmetry between the variables $y$ and $z$ to write: $\begin{aligned} t (K_{1, 2}, W) & = \int_{[0, 1]^{3}} W (x, y) W (x, z) d x d y d z \\ = \int_{x \in [0, 1]} (\int_{y \in [0, 1]} W (x, y)) (\int_{z \in [0, 1]} W (x, z)) \\ = \int_{x \in [0, 1]} (\int_{y \in [0, 1]} W (x, y))^{2} \\ \geq (\int_{x \in [0, 1]} \int_{y \in [0, 1]} W (x, y))^{2} = t (K_{2}, W)^{2} \end{aligned}$ where we used the integral Cauchy–Schwarz inequality in the last step. Finally, our desired result follows from the above inequality:

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

This above proof can be obtained from taking continuous analog of Theorem 1 in Goodman 1959 paper, "On Sets Of Acquaintances And Strangers At Any Party"^[7].

References

↑ "Large Networks and Graph Limits". bookstore.ams.org. Retrieved 2022-01-13.
↑ Lovasz, Laszlo (2009-02-01). "Very large graphs". arXiv:0902.0132 [math]. arXiv:0902.0132.
↑ 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. Unknown parameter |s2cid= ignored (help)
↑ Sidorenko, A. F. (1992). "Inequalities for functionals generated by bipartite graphs". Discrete Mathematics and Applications. 2 (5). doi:10.1515/dma.1992.2.5.489. ISSN 0924-9265. Unknown parameter |s2cid= ignored (help)
↑ 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.
↑ Lovász, László (2012). Large Networks and Graph Limits. United States: American Mathematical Society Colloquium publications. pp. 297–298. ISBN 978-0821890851. Search this book on
↑ Goodman, A. W. (1959). "On Sets of Acquaintances and Strangers at any Party". The American Mathematical Monthly. 66 (9): 778–783. doi:10.2307/2310464. ISSN 0002-9890. JSTOR 2310464.

This article "Common graph" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Common graph. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

This page exists already on Wikipedia.

[1] "Large Networks and Graph Limits". bookstore.ams.org. Retrieved 2022-01-13.

[2] Lovasz, Laszlo (2009-02-01). "Very large graphs". arXiv:0902.0132 [math]. arXiv:0902.0132.

[3] 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. Unknown parameter |s2cid= ignored (help)

[4] Sidorenko, A. F. (1992). "Inequalities for functionals generated by bipartite graphs". Discrete Mathematics and Applications. 2 (5). doi:10.1515/dma.1992.2.5.489. ISSN 0924-9265. Unknown parameter |s2cid= ignored (help)

[5] 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.

[6] Lovász, László (2012). Large Networks and Graph Limits. United States: American Mathematical Society Colloquium publications. pp. 297–298. ISBN 978-0821890851. Search this book on

[7] Goodman, A. W. (1959). "On Sets of Acquaintances and Strangers at any Party". The American Mathematical Monthly. 66 (9): 778–783. doi:10.2307/2310464. ISSN 0002-9890. JSTOR 2310464.

[1]

[2]

[3]

[4]

[5]

[6]

[7]