Common graph (original) (raw)

From Wikipedia, the free encyclopedia

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, F {\displaystyle F} is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of F {\displaystyle F} in any graph G {\displaystyle G} and its complement G ¯ {\displaystyle {\overline {G}}} is a large fraction of all possible copies of F {\displaystyle F} on the same vertices. Intuitively, if G {\displaystyle G} contains few copies of F {\displaystyle F} , then its complement G ¯ {\displaystyle {\overline {G}}} must contain lots of copies of F {\displaystyle 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.

A graph F {\displaystyle F} is common if the inequality:

t ( F , W ) + t ( F , 1 − W ) ≥ 2 − e ( F ) + 1 {\displaystyle t(F,W)+t(F,1-W)\geq 2^{-e(F)+1}}

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

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

Interpretations of definition

[edit]

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

p = 1 / 2 {\displaystyle p=1/2} . The above definition using the generalized homomorphism density can be understood in this way.

• 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 {\displaystyle K_{3}} is one simple example of non-bipartite common graph.[5]
• K 4 − {\displaystyle K_{4}^{-}} , the graph obtained by removing an edge of the complete graph on 4 vertices K 4 {\displaystyle 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 {\displaystyle K_{t}} is not common for t ≥ 4 {\displaystyle t\geq 4} .[7] In particular, K 4 {\displaystyle K_{4}} is not common even though K 4 − {\displaystyle K_{4}^{-}} is common.

Sidorenko graphs are common

[edit]

A graph F {\displaystyle F} is a Sidorenko graph if it satisfies t ( F , W ) ≥ t ( K 2 , W ) e ( F ) {\displaystyle t(F,W)\geq t(K_{2},W)^{e(F)}} for all graphons W {\displaystyle W} .

In that case, t ( F , 1 − W ) ≥ t ( K 2 , 1 − W ) e ( F ) {\displaystyle t(F,1-W)\geq t(K_{2},1-W)^{e(F)}} . Furthermore, t ( K 2 , W ) + t ( K 2 , 1 − W ) = 1 {\displaystyle 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 ) {\displaystyle f(x)=x^{e(F)}} :

t ( F , W ) + t ( F , 1 − W ) ≥ t ( K 2 , W ) e ( F ) + t ( K 2 , 1 − W ) e ( F ) ≥ 2 ( t ( K 2 , W ) + t ( K 2 , 1 − W ) 2 ) e ( F ) = 2 − e ( F ) + 1 {\displaystyle 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

[edit]

Expand the integral expression for t ( K 3 , 1 − W ) {\displaystyle t(K_{3},1-W)} and take into account the symmetry between the variables:

∫ [ 0 , 1 ] 3 ( 1 − W ( x , y ) ) ( 1 − W ( y , z ) ) ( 1 − W ( z , x ) ) d x d y d z = 1 − 3 ∫ [ 0 , 1 ] 2 W ( x , y ) + 3 ∫ [ 0 , 1 ] 3 W ( x , y ) W ( x , z ) d x d y d z − ∫ [ 0 , 1 ] 3 W ( x , y ) W ( y , z ) W ( z , x ) d x d y d z {\displaystyle \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:

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

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

∫ [ 0 , 1 ] 3 W ( x , y ) W ( y , z ) W ( z , x ) d x d y d z = t ( K 3 , W ) {\displaystyle \int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz=t(K_{3},W)}

where K 1 , 2 {\displaystyle K_{1,2}} denotes the complete bipartite graph on 1 {\displaystyle 1} vertex on one part and 2 {\displaystyle 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 1 , 2 , W ) {\displaystyle t(K_{3},W)+t(K_{3},1-W)=1-3t(K_{2},W)+3t(K_{1,2},W)} .

t ( K 1 , 2 , W ) {\displaystyle t(K_{1,2},W)} can be related to t ( K 2 , W ) {\displaystyle t(K_{2},W)} thanks to the symmetry between the variables y {\displaystyle y} and z {\displaystyle z} : t ( K 1 , 2 , W ) = ∫ [ 0 , 1 ] 3 W ( x , y ) W ( x , z ) d x d y d z = ∫ x ∈ [ 0 , 1 ] ( ∫ y ∈ [ 0 , 1 ] W ( x , y ) ) ( ∫ z ∈ [ 0 , 1 ] W ( x , z ) ) = ∫ x ∈ [ 0 , 1 ] ( ∫ y ∈ [ 0 , 1 ] W ( x , y ) ) 2 ≥ ( ∫ x ∈ [ 0 , 1 ] ∫ y ∈ [ 0 , 1 ] W ( x , y ) ) 2 = t ( K 2 , W ) 2 {\displaystyle {\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 ) ≥ 1 − 3 t ( K 2 , W ) + 3 t ( K 2 , W ) 2 = 1 / 4 + 3 ( t ( K 2 , W ) − 1 / 2 ) 2 ≥ 1 / 4 {\displaystyle 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]

• Sidorenko's conjecture

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.