Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Homomorphism density
open-in-new
<h2 id="examples">Examples</h2> <ul><li>The edge density of a graph G {\displaystyle G} is given by t ( K 2 , G ) {\displaystyle t(K_{2},G)} .</li> <li>The number of walks with k − 1 {\displaystyle k-1} steps is given by hom ( P k , G ) {\displaystyle \operatorname {hom} (P_{k},G)} .</li> <li> hom ( C k , G ) = Tr ( A k ) {\displaystyle \operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})} where A {\displaystyle A} is the adjacency matrix of G {\displaystyle G} .</li> <li>The proportion of colorings using k {\displaystyle k} colors that are proper is given by t ( G , K k ) {\displaystyle t(G,K_{k})} .</li></ul> <p>Other important properties such as the number of stable sets or the maximum cut can be expressed or estimated in terms of homomorphism numbers or densities.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="subgraph-densities">Subgraph densities</h2> <p>We define the (labeled) subgraph density of H {\displaystyle H} in G {\displaystyle G} to be </p> d ( H , G ) := # labeled copies of H in G | V ( G ) | | V ( H ) | {\displaystyle d(H,G):={\frac {\#{\text{ labeled copies of }}H{\text{ in }}G}{|V(G)|^{|V(H)|}}}} . <p>Note that it might be slightly dubious to call this a density, as we are not quite dividing through by the total number of labeled subgraphs on | V ( H ) | {\displaystyle |V(H)|} vertices of G {\displaystyle G} , but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of H {\displaystyle H} in G {\displaystyle G} corresponds to a homomorphism of H {\displaystyle H} into G {\displaystyle G} . However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of H {\displaystyle H} are sent to the same vertex of G {\displaystyle G} . That said, the number of such degenerate homomorphisms is only O ( n | V ( H ) | − 1 ) {\displaystyle O(n^{|V(H)|-1})} , so we have t ( H , G ) = d ( H , G ) + O ( 1 / n ) {\displaystyle t(H,G)=d(H,G)+O(1/n)} . For instance, we see that for graphs with constant homomorphism density, the labeled subgraph density and homomorphism density are asymptotically equivalent. For H {\displaystyle H} being a complete graph K m {\displaystyle K_{m}} , the homomorphism density and subgraph density are in fact equal (for G {\displaystyle G} without self-loops), as the edges of K m {\displaystyle K_{m}} force all images under a graph homomorphism to be distinct. </p> <h2 id="generalization-to-graphons">Generalization to graphons</h2> <p>The notion of homomorphism density can be generalized to the case where instead of a graph G {\displaystyle G} , we have a <a href="/facts/Graphon/ezqevlSv">graphon</a> W {\displaystyle W} , </p> t ( H , W ) = ∫ [ 0 , 1 ] | V ( H ) | ∏ i j ∈ E ( H ) W ( x i , x j ) ∏ i ∈ V ( H ) d x i {\displaystyle t(H,W)=\int _{[0,1]^{|V(H)|}}\prod _{ij\in E(H)}W(x_{i},x_{j})\prod _{i\in V(H)}dx_{i}} <p>Note that the integrand is a product that runs over the edges in the subgraph H {\displaystyle H} , whereas the differential is a product running over the vertices in H {\displaystyle H} . Intuitively, each vertex i {\displaystyle i} in H {\displaystyle H} is represented by the variable x i . {\displaystyle x_{i}.} For example, the triangle density in a graphon is given by </p> t ( K 3 , W ) = ∫ [ 0 , 1 ] 3 W ( x , y ) W ( y , z ) W ( z , x ) d x d y d z {\displaystyle t(K_{3},W)=\int \limits _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz} . <p>This definition of homomorphism density is indeed a generalization, because for every graph G {\displaystyle G} and its associated step graphon W G {\displaystyle W_{G}} , t ( H , G ) = t ( H , W G ) {\displaystyle t(H,G)=t(H,W_{G})} .<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p><p>The definition can be further extended to all symmetric, measurable functions W {\displaystyle W} . The following example demonstrates the benefit of this further generalization. Relative to the function W ( x , y ) = 2 cos ( 2 π ( x − y ) ) {\displaystyle W(x,y)=2\cos(2\pi (x-y))} , the density of H {\displaystyle H} in W {\displaystyle W} is the number of <a href="/facts/Eulerian_cycle/4l2G67c7">Eulerian cycles</a> in H {\displaystyle H} . </p><p>This notion is helpful in understanding asymptotic behavior of homomorphism densities of graphs which satisfy certain property, since a graphon is a limit of a sequence of graphs. </p> <h2 id="inequalities">Inequalities</h2> <p>Many results in <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a> can be described by inequalities involving homomorphism densities associated to a graph. The following are a sequence of examples relating the density of triangles to the density of edges. </p> <h3>Turan's Theorem</h3> <p>A classic example is <a href="/facts/Tur%C3%A1n%27s_theorem/opMCT84y">Turán's Theorem</a>, which states that if t ( K r , W ) = 0 {\displaystyle t(K_{r},W)=0} , then t ( K 2 , W ) ≤ ( 1 − 1 r − 1 ) {\displaystyle t(K_{2},W)\leq \left(1-{\frac {1}{r-1}}\right)} . A special case of this is <a href="/facts/Mantel%27s_theorem/opMCT84y">Mantel's Theorem</a>, which states that if t ( K 3 , W ) = 0 {\displaystyle t(K_{3},W)=0} , then t ( K 2 , W ) ≤ 1 / 2 {\displaystyle t(K_{2},W)\leq 1/2} . </p> <h3>Goodman's Theorem</h3><p> An extension of Mantel's Theorem provides an explicit lower bound on triangle densities in terms of edge densities.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a></p><p>Theorem (Goodman). t ( K 3 , G ) ≥ t ( K 2 , G ) ( 2 t ( K 2 , G ) − 1 ) . {\displaystyle t(K_{3},G)\geq t(K_{2},G)(2t(K_{2},G)-1).} </p> <h3>Kruskal-Katona Theorem</h3> <p>A converse inequality to Goodman's Theorem is a special case of <a href="/facts/Kruskal%E2%80%93Katona_theorem/FQHSH46E">Kruskal–Katona theorem</a>, which states that t ( K 3 , G ) ≤ t ( K 2 , G ) 3 / 2 {\displaystyle t(K_{3},G)\leq t(K_{2},G)^{3/2}} . It turns out that both of these inequalities are tight for specific edge densities. </p><p><i>Proof.</i> It is sufficient to prove this inequality for any graph G {\displaystyle G} . Say G {\displaystyle G} is a graph on n {\displaystyle n} vertices, and { λ i } i = 1 n {\displaystyle \{\lambda _{i}\}_{i=1}^{n}} are the eigenvalues of its <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> A G {\displaystyle A_{G}} . By <a href="/facts/Spectral_graph_theory/tBttgGTh">spectral graph theory</a>, we know </p> hom ( K 2 , G ) = t ( K 2 , G ) | V ( G ) | 2 = ∑ i = 1 n λ i 2 {\displaystyle \operatorname {hom} (K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum _{i=1}^{n}\lambda _{i}^{2}} , and hom ( K 3 , G ) = t ( K 3 , G ) | V ( G ) | 3 = ∑ i = 1 n λ i 3 {\displaystyle \operatorname {hom} (K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum _{i=1}^{n}\lambda _{i}^{3}} . <p>The conclusion then comes from the following inequality: </p> hom ( K 3 , G ) = ∑ i = 1 n λ i 3 ≤ ( ∑ i = 1 n λ i 2 ) 3 / 2 = hom ( K 2 , G ) 3 / 2 {\displaystyle \operatorname {hom} (K_{3},G)=\sum _{i=1}^{n}\lambda _{i}^{3}\leq \left(\sum _{i=1}^{n}\lambda _{i}^{2}\right)^{3/2}=\operatorname {hom} (K_{2},G)^{3/2}} . <h3>Description of triangle vs edge density</h3><p> A more complete description of the relationship between t ( K 3 , G ) {\displaystyle t(K_{3},G)} and t ( K 2 , G ) {\displaystyle t(K_{2},G)} was proven by <a href="/facts/Alexander_Razborov/EmMX1W4K">Razborov</a>. His work from 2008 completes the understanding of a homomorphism inequality problem, the description of D 2 , 3 {\displaystyle D_{2,3}} , which is the region of feasible edge density, triangle density pairs in a graphon.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a></p><p> D 2 , 3 = { ( t ( K 2 , W ) , t ( K 3 , W ) ) : W is a graphon } ⊆ [ 0 , 1 ] 2 {\displaystyle D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ is a graphon}}\}\subseteq [0,1]^{2}} .</p><p>The upper boundary of the region is tight and given by the Kruskal-Katona Theorem. The lower boundary is main result of work by Razborov in providing a complete description.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><h2 id="useful-tools">Useful tools</h2> <h3>Cauchy-Schwarz</h3> <p>One particularly useful inequality to analyze homomorphism densities is the <a href="/facts/Cauchy%E2%80%93Schwarz_inequality/poMzQUIY">Cauchy–Schwarz inequality</a>. The effect of applying the Cauchy-Schwarz inequality is "folding" the graph over a line of symmetry to relate it to a smaller graph. This allows for the reduction of densities of large but symmetric graphs to that of smaller graphs. As an example, we prove that the cycle of length 4 is <a href="/facts/Sidorenko%27s_conjecture/jxzA8ffr">Sidorenko</a>. If the vertices are labelled 1,2,3,4 in that order, the diagonal through vertices 1 and 3 is a line of symmetry. Folding over this line relates C 4 {\displaystyle C_{4}} to the complete <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a> K 1 , 2 {\displaystyle K_{1,2}} . Mathematically, this is formalized as </p> t ( C 4 , G ) = ∫ 1 , 2 , 3 , 4 W ( 1 , 2 ) W ( 2 , 3 ) W ( 3 , 4 ) W ( 1 , 4 ) = ∫ 1 , 3 ( ∫ 2 W ( 1 , 2 ) W ( 2 , 3 ) ) ( ∫ 4 W ( 1 , 4 ) W ( 4 , 3 ) ) = ∫ 1 , 3 ( ∫ 2 W ( 1 , 2 ) W ( 2 , 3 ) ) 2 ≥ ( ∫ 1 , 2 , 3 W ( 1 , 2 ) W ( 2 , 3 ) ) 2 = t ( K 1 , 2 , G ) 2 {\displaystyle {\begin{aligned}t(C_{4},G)&=\int _{1,2,3,4}W(1,2)W(2,3)W(3,4)W(1,4)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)\left(\int _{4}W(1,4)W(4,3)\right)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)^{2}\\&\geq \left(\int _{1,2,3}W(1,2)W(2,3)\right)^{2}=t(K_{1,2},G)^{2}\end{aligned}}} <p>where we applied Cauchy-Schwarz to "fold" vertex 2 onto vertex 4. The same technique can be used to show t ( K 1 , 2 , G ) ≥ t ( K 2 , G ) 2 {\displaystyle t(K_{1,2},G)\geq t(K_{2},G)^{2}} , which combined with the above verifies that C 4 {\displaystyle C_{4}} is a Sidorenko graph. </p><p>The generalization <a href="/facts/H%C3%B6lder%27s_inequality/7I1ubTWw">Hölder's inequality</a> can also be used in a similar manner to fold graphs multiple times with a single step. It is also possible to apply the more general form of Cauchy-Schwarz to fold graphs in the case that certain edges lie on the line of symmetry. </p> <h3>Lagrangian</h3> <p>The Lagrangian can be useful in analyzing extremal problems. The quantity is defined to be </p> L ( H ) = max x 1 , … , x n ≥ 0 x 1 + ⋯ x n = 1 ∑ e ∈ E ( H ) ∏ v ∈ e x v {\displaystyle L(H)=\max _{\begin{matrix}x_{1},\ldots ,x_{n}\geq 0\\x_{1}+\cdots x_{n}=1\end{matrix}}\sum _{e\in E(H)}\prod _{v\in e}x_{v}} . <p>One useful fact is that a maximizing vector x {\displaystyle x} is equally supported on the vertices of a clique in H {\displaystyle H} . The following is an application of analyzing this quantity. </p><p> According to Hamed Hatami and Sergei Norine, one can convert any algebraic inequality between homomorphism densities to a linear inequality.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> In some situations, deciding whether such an inequality is true or not can be simplified, such as it is the case in the following theorem.</p><p>Theorem (<a href="/facts/B%C3%A9la_Bollob%C3%A1s/9T1eot5o">Bollobás</a>). Let a 1 , ⋯ , a n {\displaystyle a_{1},\cdots ,a_{n}} be real constants. Then, the inequality </p> ∑ i = 1 n a i t ( K i , G ) ≥ 0 {\displaystyle \sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0} <p> holds for every graph G {\displaystyle G} if and only if it holds for every complete graph K m {\displaystyle K_{m}} .<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></p><p> However, we get a much harder problem, in fact an <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a> one, when we have a homomorphism inequalities on a more general set of graphs H i {\displaystyle H_{i}} :</p><p>Theorem (Hatami, Norine). Let a 1 , ⋯ , a n {\displaystyle a_{1},\cdots ,a_{n}} be real constants, and { H i } i = 1 n {\displaystyle \{H_{i}\}_{i=1}^{n}} graphs. Then, it is an undecidable problem to determine whether the homomorphism density inequality </p> ∑ i = 1 n a r t ( H i , G ) ≥ 0 {\displaystyle \sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0} <p> holds for every graph G {\displaystyle G} . <a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></p><p>A recent observation<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> proves that any linear homomorphism density inequality is a consequence of the positive semi-definiteness of a certain infinite matrix, or to the positivity of a <a href="/facts/Quantum_graph/KcnTDMPt">quantum graph</a>; in other words, any such inequality would follow from applications of the Cauchy-Schwarz Inequality. <a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p><h2 id="see-also">See also</h2> <ul><li><a href="/facts/Common_graph/Wx74rrGk">Common graph</a></li> <li><a href="/facts/Sidorenko%27s_conjecture/jxzA8ffr">Sidorenko's conjecture</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T; Vestergombi, Katalin (2008). "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. <a href="/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz" target="_blank">/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Hatami, H., Norine, S. (2011). "Undecidability of linear inequalities in graph homomorphism densities" (PDF). Journal of the American Mathematical Society. 24 (2): 553. arXiv:1005.2382. doi:10.1090/S0894-0347-2010-00687-X. S2CID 3363894 – via MathSciNet.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf" target="_blank">https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Lovász, László (2012). Large networks and graph limits. Providence, Rhode Island. ISBN 978-0-8218-9085-1. OCLC 812530987.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-0-8218-9085-1" target="_blank">978-0-8218-9085-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T; Vestergombi, Katalin (2008). "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. <a href="/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz" target="_blank">/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Lovász, László (2012). Large networks and graph limits. Providence, Rhode Island. ISBN 978-0-8218-9085-1. OCLC 812530987.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-0-8218-9085-1" target="_blank">978-0-8218-9085-1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Razborov, Alexander (2008). "On the minimal density of triangles in graphs" (PDF). Combinatorics, Probability and Computing. 17 (4): 603–618. doi:10.1017/S0963548308009085. S2CID 26524353 – via MathSciNet (AMS). <a href="http://people.cs.uchicago.edu/~razborov/files/triangles.pdf" target="_blank">http://people.cs.uchicago.edu/~razborov/files/triangles.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Razborov, Alexander (2008). "On the minimal density of triangles in graphs" (PDF). Combinatorics, Probability and Computing. 17 (4): 603–618. doi:10.1017/S0963548308009085. S2CID 26524353 – via MathSciNet (AMS). <a href="http://people.cs.uchicago.edu/~razborov/files/triangles.pdf" target="_blank">http://people.cs.uchicago.edu/~razborov/files/triangles.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Hatami, H., Norine, S. (2011). "Undecidability of linear inequalities in graph homomorphism densities" (PDF). Journal of the American Mathematical Society. 24 (2): 553. arXiv:1005.2382. doi:10.1090/S0894-0347-2010-00687-X. S2CID 3363894 – via MathSciNet.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf" target="_blank">https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Bollobás, Bela (1986). Combinatorics: Set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge: Cambridge University Press. pp. 79-84. ISBN 0-521-33059-9. <a href="0-521-33059-9" target="_blank">0-521-33059-9</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Hatami, H., Norine, S. (2011). "Undecidability of linear inequalities in graph homomorphism densities" (PDF). Journal of the American Mathematical Society. 24 (2): 553. arXiv:1005.2382. doi:10.1090/S0894-0347-2010-00687-X. S2CID 3363894 – via MathSciNet.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf" target="_blank">https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Freedman, M., Lovász, L., Schrijver, A. (2007). "Reflection Positivity, Rank connectivity, and Homomorphism of Graphs" (PDF). Journal of the American Mathematical Society. 20 (1): 1.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://ams.org/journals/jams/2007-20-01/S0894-0347-06-00529-7/S0894-0347-06-00529-7.pdf" target="_blank">https://ams.org/journals/jams/2007-20-01/S0894-0347-06-00529-7/S0894-0347-06-00529-7.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Hatami, H., Norine, S. (2011). "Undecidability of linear inequalities in graph homomorphism densities" (PDF). Journal of the American Mathematical Society. 24 (2): 553. arXiv:1005.2382. doi:10.1090/S0894-0347-2010-00687-X. S2CID 3363894 – via MathSciNet.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf" target="_blank">https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> </ol>