Homomorphism density

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph ${\displaystyle H}$ is a parameter ${\displaystyle t(H,-)}$ that is associated to each graph ${\displaystyle G}$ in the following manner:

${\displaystyle t(H,G):={\frac {|hom(H,G)|}{|V(G)|^{|V(H)|}}}}$.

Above, ${\displaystyle hom(H,G)}$ is the set of graph homomorphisms, or adjacency preserving maps, from ${\displaystyle H}$ to ${\displaystyle G}$. Density can also be interpreted as the probability that a map from the vertices of ${\displaystyle H}$ to the vertices of ${\displaystyle G}$ chosen uniformly at random is a graph homomorphism.[1] There is a connection between homomorphism densities and subgraph densities, which is elaborated on below. [2]

Examples

• The edge density of a graph ${\displaystyle G}$ is given by ${\displaystyle t(K_{2},G)}$.
• In a graph with ${\displaystyle n}$ vertices, where the average degree is greater than or equal than ${\displaystyle pn}$, the edge density is at least ${\displaystyle p}$.
• The density of triangles in a graph ${\displaystyle G}$ is given by ${\displaystyle t(K_{3},G)}$.
• The density of 4-cycles in a graph ${\displaystyle G}$ is given by ${\displaystyle t(C_{4},G)}$.

Subgraph densities

We define the (labeled) subgraph density of ${\displaystyle H}$ in ${\displaystyle G}$ to be

${\displaystyle d(H,G):={\frac {\#{\text{ labeled copies of }}H{\text{ in }}G}{|V(G)|^{|V(H)|}}}}$.

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 ${\displaystyle |V(H)|}$ vertices of ${\displaystyle G}$, but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of ${\displaystyle H}$ in ${\displaystyle G}$ corresponds to a homomorphism of ${\displaystyle H}$ into ${\displaystyle G}$. However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of ${\displaystyle H}$ are sent to the same vertex of ${\displaystyle G}$. That said, the number of such degenerate homomorphisms is only ${\displaystyle O(n^{|V(H)|-1})}$, so we have ${\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 ${\displaystyle H}$ being a complete graph ${\displaystyle K_{m}}$, the homomorphism density and subgraph density are in fact equal (for ${\displaystyle G}$ without self-loops), as the edges of ${\displaystyle K_{m}}$ 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 ${\displaystyle G}$, we have a graphon ${\displaystyle W}$,

${\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}}$

Note that the integrand is a product that runs over the edges in the subgraph ${\displaystyle H}$, whereas the differential is a product running over the vertices in ${\displaystyle H}$. Intuitively, each vertex ${\displaystyle i}$ in ${\displaystyle H}$ is represented by the variable ${\displaystyle x_{i}}$.

For example, the triangle density in a graphon is given by

${\displaystyle t(K_{3},W)=\int \limits _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz}$.

This definition of homomorphism density is indeed a generalization, because for every graph ${\displaystyle G}$ and its associated step graphon ${\displaystyle W_{G}}$, ${\displaystyle t(H,G)=t(H,W_{G})}$.[1]

This notion is helpful in understanding assymptotical behavior of homomorphism densities of graphs which satisfy certain property, since a graphon is a limit of a sequence of graphs.

Important results: inequalities

Many results in extremal graph theory can be described by inequalities involving homomorphism densities associated to a graph. For instance, Mantel's Theorem states, in the context of graphons, that if ${\displaystyle t(K_{3},W)=0}$, then ${\displaystyle t(K_{2},W)\leq 1/2}$. Another example is Turán's Theorem, which states that if ${\displaystyle t(K_{r},W)=0}$, then ${\displaystyle t(K_{2},W)\leq (r-2/r-1)}$.

According to Hamed Hatami and Sergei Norine, one can convert any algebraic inequality between homomorphism densities to a linear inequality.[2] 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.

Theorem (Bollobás). Let ${\displaystyle a_{1},\cdots ,a_{n}}$ be real constants. Then, the inequality

${\displaystyle \sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0}$

holds for every graph ${\displaystyle G}$ if and only if it holds for every complete graph ${\displaystyle K_{m}}$.[3]

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 ${\displaystyle H_{i}}$:

Theorem (Hatami, Norine). Let ${\displaystyle a_{1},\cdots ,a_{n}}$ be real constants, and ${\displaystyle \{H_{i}\}_{i=1}^{n}}$ graphs. Then, it is an undecidable problem to determine whether the homomorphism density inequality

${\displaystyle \sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0}$

holds for every graph ${\displaystyle G}$. [2]

A recent observation[4] 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. [2]

Description of ${\displaystyle D_{2,3}}$

Another recent development consists in the completion of the understanding of a homomorphism inequality problem, the description of ${\displaystyle D_{2,3}}$, which is the region of feasible edge density, triangle density pairs in a graphon:

${\displaystyle D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ is a graphon}}\}\subseteq [0,1]^{2}}$

Observation 1. This region is closed, since the limit of a sequence of graphs is a graphon. [1]

Observation 2. For every ${\displaystyle 0\leq r\leq 1}$, the set ${\displaystyle D_{2,3}\cap [0,1]\times \{r\}}$ is a vertical line segment, with no gaps.

Proof: Consider two graphons ${\displaystyle W_{0}}$, ${\displaystyle W_{1}}$ with the same edge density; then, the family of graphons of the following form, as ${\displaystyle t}$ varies from 0 to 1

${\displaystyle W_{t}=(1-t)W_{0}+tW_{1}}$

achieves every possible triangle density between the values ${\displaystyle t(K_{3},W_{0})}$ and ${\displaystyle t(K_{3},W_{1})}$, by continuity of this map.

Observation 3. For every , graphon ${\displaystyle W:[0,1]^{2}\rightarrow [0,1]}$, we have the upper bound ${\displaystyle t(K_{3},W)\leq t(K_{2},W)^{3/2}}$

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

${\displaystyle hom(K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum _{i=1}^{n}\lambda _{i}^{2}}$,

${\displaystyle hom(K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum _{i=1}^{n}\lambda _{i}^{3}}$.

The conclusion then comes from the following inequality:

${\displaystyle hom(K_{3},G)=\sum _{i=1}^{n}\lambda _{i}^{3}\leq \left(\sum _{i=1}^{n}\lambda _{i}^{2}\right)^{3/2}=hom(K_{2},G)^{3/2}}$

Observation 3. The extremal points of the convex hull of

${\displaystyle D_{2,3,\cdots ,r}=\{(t(K_{2},W),t(K_{3},W),\cdots ,t(K_{r},W))\;:\;W{\text{ is a graphon}}\}\subseteq [0,1]^{r-1}}$

are given by ${\displaystyle W=K_{m}}$ for each ${\displaystyle m}$ positive integer. In particular, The extrema of ${\displaystyle D_{2,3}}$ are given by the following discrete set of points in the curve ${\displaystyle y=x(2x-1)}$:

${\displaystyle p_{m}=\left({\frac {m-1}{m}},{\frac {(m-1)(m-2)}{m^{2}}}\right)}$

Observation 3. This is a theorem due to Razborov,[5] which states that for a given edge density ${\displaystyle r=t(K_{2},W)}$, if

${\displaystyle {\frac {k-1}{k}}<r<{\frac {k}{k+1}}}$,

for some positive integer ${\displaystyle k}$, then the minimum feasible triangle density is attained by a unique step function graphon ${\displaystyle W}$ with node weights ${\displaystyle a_{1},\cdots a_{k}}$ with sum equal to 1 and such that ${\displaystyle a_{1}=\cdots =a_{k-1}\geq a_{k}}$. More explicitly, the minimum possible ${\displaystyle t(K_{3},W)}$ is

${\displaystyle {\frac {(k-1)\left(k-2{\sqrt {k(k-r(k+1))}}\right)\left(k+{\sqrt {k(k-r(k+1))}}\right)^{2}}{k^{2}(k+1)^{2}}}}$.

See also

• Sidorenko's conjecture

References

1. Borgs, C., Chayes, J.T., Lovász, L., Sós, V.T., Vestergombi, K. (2008). "Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing". Advances in Mathematics. 219, no.6: 1805, 1811 – via ELSEVIER Science Project.CS1 maint: multiple names: authors list (link)
2. Hatami, H., Norine, S. (2011). "Undecidability of linear inequalities in graph homomorphism densities" (PDF). Journal of the American Mathematical Society. 24, no.2: 553 – via MathSciNet.CS1 maint: multiple names: authors list (link)
3. 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.
4. Freedman, M., Lovász, L., Schrijver, A. (2007). "Reflection Positivity, Rank connectivity, and Homomorphism of Graphs" (PDF). Journal of the American Mathematical Society. 20, no.1: 1.CS1 maint: multiple names: authors list (link)
5. Razborov, Alexander (2008). "On the minimal density of triangles in graphs" (PDF). Combinatorics, Probability and Computing. 17, no.4: 1 – via MathSciNet (AMS).