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.[1] There is a connection between homomorphism densities and subgraph densities, which is elaborated on below. [2]

Examples

The edge density of a graph $G$ is given by $t(K_{2},G)$ .
In a graph with $n$ vertices, 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 be generalized to the case where instead of a graph $G$ , we have a graphon $W$ ,

$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 $H$ , whereas the differential is a product running over the vertices in $H$ . Intuitively, each vertex $i$ in $H$ is represented by the variable $x_{i}$ .

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

$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 $G$ and its associated step graphon $W_{G}$ , $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 $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.[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 $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}$ .[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 $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$ . [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 $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 of graphs is a graphon. [1]

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,[5] 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}}}$ .

References

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)
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)
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.
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)
Razborov, Alexander (2008). "On the minimal density of triangles in graphs" (PDF). Combinatorics, Probability and Computing. 17, no.4: 1 – via MathSciNet (AMS).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-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)

[:1-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).