Homomorphism density

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

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

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

Examples

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

Subgraph densities

We define the (labeled) subgraph density of $H$ in $G$ to be

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

Generalization to graphons

The notion of homomorphism density can also be assigned to the case where instead of $G$, we have a graphon,

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

For example, the triangle density in a graphon is equal to

$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 a generalization, because for every graph $G$ and its associated step graphon $W_{G}$, $t(H,G)=t(H,W_{G})$.

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

Homomorphism density 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 $t(K_{3},W)=0$, then $t(K_{2},W)\leq 1/2$. Another example is Turán's Theorem, which states that if $t(K_{r},W)=0$, then $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. 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 $a_{1},\cdots ,a_{n}$ be real constants. Then, the inequality

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

holds for every graph $G$ if and only if it holds for every complete graph $K_{m}$.

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

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

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

holds for every graph $G$.

A recent observation 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.

Description of $D_{2,3}$

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

$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 o graphs is a graphon.

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

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

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

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

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

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

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

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

$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

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

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

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

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

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

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