Homomorphism density

{{Short description|Fraction of graph maps that are homomorphisms}} In the mathematical field of extremal graph theory, '''homomorphism density''' with respect to a graph <math>H</math> is a parameter <math>t(H,-)</math> that is associated to each graph <math>G</math> in the following manner:

: <math>t(H,G):=\frac{\left|\operatorname{hom}(H,G)\right|}{|V(G)|^{|V(H)|}}</math>.

Above, <math>\operatorname{hom}(H,G)</math> is the set of graph homomorphisms, or adjacency preserving maps, from <math>H</math> to <math>G</math>. Density can also be interpreted as the probability that a map from the vertices of <math>H</math> to the vertices of <math>G</math> chosen uniformly at random is a graph homomorphism.<ref name=":0">{{Cite journal | last1=Borgs | first1=Christian | last2=Chayes | first2=Jennifer T. | last3=Lovász | first3=László | authorlink3=László Lovász | last4=Sós | first4= Vera T | authorlink4=Vera Sós | last5=Vestergombi | first5=Katalin | year=2008 | title=Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing | journal=Advances in Mathematics | volume=219 | issue=6 | pages=1801–1851 | doi=10.1016/j.aim.2008.07.008 | doi-access=free| arxiv=math/0702004 }}</ref> There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.<ref name=":1">{{Cite journal|last=Hatami, H., Norine, S.|date=2011|title=Undecidability of linear inequalities in graph homomorphism densities.|url=https://www.ams.org/journals/jams/2011-24-02/S0894-0347-2010-00687-X/S0894-0347-2010-00687-X.pdf|journal=Journal of the American Mathematical Society|volume=24|issue=2|pages=553|doi=10.1090/S0894-0347-2010-00687-X|s2cid=3363894|via=MathSciNet|arxiv=1005.2382}}</ref>

== Examples ==

* The edge density of a graph <math>G</math> is given by <math>t(K_{2},G)</math>. * The number of walks with <math>k-1</math> steps is given by <math>\operatorname{hom}(P_k, G)</math>. *<math>\operatorname{hom}(C_k, G) = \operatorname{Tr}(A^k)</math> where <math>A</math> is the adjacency matrix of <math>G</math>. *The proportion of colorings using <math>k</math> colors that are proper is given by <math>t(G, K_k)</math>. 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.<ref name=":2" />

== Subgraph densities == We define the (labeled) subgraph density of <math>H</math> in <math>G</math> to be

: <math>d(H,G):=\frac{\# \text{ labeled copies of } H \text{ in } G}{|V(G)|^{|V(H)|}}</math>.

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 <math>|V(H)|</math> vertices of <math>G</math>, but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of <math>H</math> in <math>G</math> corresponds to a homomorphism of <math>H</math> into <math>G</math>. However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of <math>H</math> are sent to the same vertex of <math>G</math>. That said, the number of such degenerate homomorphisms is only <math>O(n^{|V(H)|-1})</math>, so we have <math>t(H,G)=d(H,G)+O(1/n)</math>. For instance, we see that for graphs with constant homomorphism density, the labeled subgraph density and homomorphism density are asymptotically equivalent. For <math>H</math> being a complete graph <math>K_m</math>, the homomorphism density and subgraph density are in fact equal (for <math>G</math> without self-loops), as the edges of <math>K_m</math> force all images under a graph homomorphism to be distinct.

== Generalization to graphons == The notion of homomorphism density can be generalized to the case where instead of a graph <math>G</math>, we have a graphon <math>W</math>,

: <math>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}</math>

Note that the integrand is a product that runs over the edges in the subgraph <math>H</math>, whereas the differential is a product running over the vertices in <math>H</math>. Intuitively, each vertex <math>i</math> in <math>H</math> is represented by the variable <math>x_{i}.</math> For example, the triangle density in a graphon is given by

: <math>t(K_3, W) = \int\limits_{[0,1]^3} W(x,y)W(y,z)W(z,x) dx dy dz</math>.

This definition of homomorphism density is indeed a generalization, because for every graph <math>G</math> and its associated step graphon <math>W_{G}</math>, <math>t(H,G)=t(H,W_{G})</math>.<ref name=":0" />

The definition can be further extended to all symmetric, measurable functions <math>W</math>. The following example demonstrates the benefit of this further generalization. Relative to the function <math>W(x,y) = 2\cos(2\pi(x-y))</math>, the density of <math>H</math> in <math>W</math> is the number of Eulerian cycles in <math>H</math>.

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.

== Inequalities == Many results in extremal graph theory 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.

=== Turan's Theorem === A classic example is Turán's Theorem, which states that if <math>t(K_{r},W)=0</math>, then <math>t(K_{2},W) \leq \left(1-\frac{1}{r-1}\right)</math>. A special case of this is Mantel's Theorem, which states that if <math>t(K_{3},W)=0</math>, then <math>t(K_{2},W)\leq 1/2</math>.

=== Goodman's Theorem === An extension of Mantel's Theorem provides an explicit lower bound on triangle densities in terms of edge densities.<ref name=":2">{{Cite book|last=Lovász|first=László|title=Large networks and graph limits|date=2012|isbn=978-0-8218-9085-1|location=Providence, Rhode Island|oclc=812530987}}</ref><blockquote>'''Theorem (Goodman).''' <math>t(K_3, G) \geq t(K_2, G)(2t(K_2, G) - 1).</math></blockquote>

=== Kruskal-Katona Theorem === A converse inequality to Goodman's Theorem is a special case of Kruskal–Katona theorem, which states that <math>t(K_3, G) \leq t(K_2, G)^{3/2}</math>. It turns out that both of these inequalities are tight for specific edge densities.

''Proof.'' It is sufficient to prove this inequality for any graph <math>G</math>. Say <math>G</math> is a graph on <math>n</math> vertices, and <math>\{\lambda_{i}\}_{i=1}^{n}</math> are the eigenvalues of its adjacency matrix <math>A_{G}</math>. By spectral graph theory, we know

: <math>\operatorname{hom}(K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum_{i=1}^{n}\lambda_{i}^{2}</math>, and <math>\operatorname{hom}(K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum_{i=1}^{n}\lambda_{i}^{3}</math>.

The conclusion then comes from the following inequality:

: <math>\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}</math>.

=== Description of triangle vs edge density === A more complete description of the relationship between <math>t(K_3, G)</math> and <math>t(K_2, G)</math> was proven by Razborov. His work from 2008 completes the understanding of a homomorphism inequality problem, the description of <math>D_{2,3}</math>, which is the region of feasible edge density, triangle density pairs in a graphon.<ref name=":3">{{Cite journal|last=Razborov|first=Alexander|date=2008|title=On the minimal density of triangles in graphs.|url=https://people.cs.uchicago.edu/~razborov/files/triangles.pdf|journal=Combinatorics, Probability and Computing|volume=17|issue=4|pages=603–618|doi=10.1017/S0963548308009085|via=MathSciNet (AMS)|s2cid=26524353}}</ref><blockquote><math>D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W\text{ is a graphon}\}\subseteq [0,1]^{2}</math>.</blockquote>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.<ref name=":3" />

== Useful tools ==

=== Cauchy-Schwarz === One particularly useful inequality to analyze homomorphism densities is the Cauchy–Schwarz inequality. 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 Sidorenko. 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 <math>C_4</math> to the complete bipartite graph <math>K_{1,2}</math>. Mathematically, this is formalized as

: <math>\begin{align} 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{align}</math>

where we applied Cauchy-Schwarz to "fold" vertex 2 onto vertex 4. The same technique can be used to show <math>t(K_{1,2}, G) \geq t(K_2, G)^2</math>, which combined with the above verifies that <math>C_4</math> is a Sidorenko graph.

The generalization Hölder's inequality 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.

=== Lagrangian === The Lagrangian can be useful in analyzing extremal problems. The quantity is defined to be

: <math>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</math>.

One useful fact is that a maximizing vector <math>x</math> is equally supported on the vertices of a clique in <math>H</math>. The following is an application of analyzing this quantity.

According to Hamed Hatami and Sergei Norine, one can convert any algebraic inequality between homomorphism densities to a linear inequality.<ref name=":1" /> 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.<blockquote>'''Theorem (Bollobás).''' Let <math>a_{1},\cdots,a_{n}</math> be real constants. Then, the inequality

: <math>\sum_{i=1}^{n}a_{i}t(K_{i},G)\geq 0</math>

holds for every graph <math>G</math> if and only if it holds for every complete graph <math>K_{m}</math>.<ref>{{Cite book|last=Bollobás|first=Bela|url=https://archive.org/details/combinatorics00bela/page/79|title=Combinatorics: Set systems, hypergraphs, families of vectors and combinatorial probability.|publisher=Cambridge University Press|year=1986|isbn=0-521-33059-9|location=Cambridge|pages=[https://archive.org/details/combinatorics00bela/page/79 79-84]}}</ref></blockquote>

However, we get a much harder problem, in fact an undecidable one, when we have a homomorphism inequalities on a more general set of graphs <math>H_{i}</math>:<blockquote>'''Theorem (Hatami, Norine).''' Let <math>a_{1},\cdots,a_{n}</math> be real constants, and <math>\{H_{i}\}_{i=1}^{n}</math> graphs. Then, it is an undecidable problem to determine whether the homomorphism density inequality

: <math>\sum_{i=1}^{n}a_{r}t(H_{i},G)\geq 0</math>

holds for every graph <math>G</math>. <ref name=":1" /></blockquote>A recent observation<ref>{{Cite journal|last=Freedman, M., Lovász, L., Schrijver, A.|date=2007|title=Reflection Positivity, Rank connectivity, and Homomorphism of Graphs|url=https://ams.org/journals/jams/2007-20-01/S0894-0347-06-00529-7/S0894-0347-06-00529-7.pdf|journal=Journal of the American Mathematical Society|volume=20|issue=1|pages=1}}</ref> 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 quantum graph; in other words, any such inequality would follow from applications of the Cauchy-Schwarz Inequality. <ref name=":1" />

== See also == *Common graph *Sidorenko's conjecture

== References ==  {{reflist}}

Category:Extremal graph theory