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[]