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.

Definition

A graph $F$ is common if 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.^[1]

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,{\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,^[2] $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}})\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.^[3] 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.^[5]
$K_{4}^{-}$ , the graph obtained by removing an edge of the complete graph on 4 vertices $K_{4}$ , is common.^[6]
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\geq 4$ .^[7] 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)\geq t(K_{2},W)^{e(F)}$ for all graphons $W$ .

In that case, $t(F,1-W)\geq 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)\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.^[8]

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 _{[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$

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

\int _{[0,1]^{2}}W(x,y)dxdy=t(K_{2},W)

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

\int _{[0,1]^{3}}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{alignedat}{4}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}\end{alignedat}}

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

$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$ .

This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"^[9]

References

↑ Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.
↑ 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. arXiv:math/0702004. doi:10.1016/j.aim.2008.07.008. ISSN 0001-8708. S2CID 5974912.
↑ Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.
↑ 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. S2CID 117471984.
↑ Large Networks and Graph Limits. American Mathematical Society. p. 299. Retrieved 2022-01-13.
↑ Large Networks and Graph Limits. American Mathematical Society. p. 298. Retrieved 2022-01-13.
↑ 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.
↑ 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 is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.

[2] 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. arXiv:math/0702004. doi:10.1016/j.aim.2008.07.008. ISSN 0001-8708. S2CID 5974912.

[3] Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.

[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. S2CID 117471984.

[5] Large Networks and Graph Limits. American Mathematical Society. p. 299. Retrieved 2022-01-13.

[6] Large Networks and Graph Limits. American Mathematical Society. p. 298. Retrieved 2022-01-13.

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

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

[9] 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]

[8]

[9]