1 Definition and intuition

1.1 Homomorphisms between structured objects

A homomorphism is a structure-preserving map from a small object to a larger one. In graph settings, a homomorphism from a pattern graph \(H\) to a graph \(G\) is a vertex map that takes edges of \(H\) to edges of \(G\). Non-edges are not required to map to non-edges. This “edge-respecting” property makes homomorphisms a flexible way to count how well a pattern fits inside a host structure.

1.2 Raw counts versus normalized quantities

The most direct quantity is the homomorphism count \(\mathrm{hom}(H,G)\), the number of homomorphisms \(H \to G\). To compare across host graphs of different sizes, one typically normalizes by a function of \(V(G)\) (and sometimes by additional combinatorial factors). The result is a homomorphism density, often denoted \(t(H,G)\), intended to behave like a stable “frequency” of \(H\) inside \(G\).

1.3 Density as a probability-like measure

After normalization, \(t(H,G)\) can be interpreted through random mappings: choose a random function from \(V(H)\) to \(V(G)\) (or choose a random way to map vertices of the pattern into the host) and ask for the probability that the mapping is edge-respecting. With appropriate denominators, this probability interpretation becomes exact for graphs and many relational structures, which is why the term “density” is natural.

1.4 Examples with small graphs and patterns

For very small patterns, densities reduce to familiar statistics. If \(H\) is a single edge, \(t(H,G)\) essentially measures edge density of \(G\). If \(H\) is a triangle, \(t(H,G)\) captures how often edge relationships align in a triangular pattern, even when the mapping is allowed to identify vertices (depending on conventions). Examples such as complete graphs, empty graphs, and simple bipartite patterns illustrate that densities can distinguish global structure beyond simple counts of edges.

2 Formal setup in graph theory

2.1 Graph homomorphism density

2.1.1 Counting homomorphisms from a pattern graph

Let \(H\) and \(G\) be finite simple graphs. A homomorphism \(\varphi:V(H)\to V(G)\) satisfies: if \((u,v)\in E(H)\), then \((\varphi(u),\varphi(v))\in E(G)\). The homomorphism count is \[

\mathrm{hom}(H,G)=\left\{\varphi: V(H)\to V(G) \,:\, \varphi \text{ is a homomorphism}\}\right.

\] This counts mappings where vertices of \(H\) may collapse onto the same vertex of \(G\) when that does not violate edge constraints.

2.1.1.1 Normalization conventions and denominators

A common normalization is \[

t(H,G)=\frac{\mathrm{hom}(H,G)}{V(G)^{V(H)}}.

\] This uses the total number of all functions \(V(H)\to V(G)\) as denominator, aligning with the probability-like viewpoint. Other conventions exist in the literature, particularly when one insists on injective maps (often related to subgraph counts), but \(t(H,G)\) defined above is standard in graph limit theory.

2.1.2 Interpreting density via random mappings

Under the normalization \(t(H,G)=\mathrm{hom}(H,G)/V(G)^{V(H)}\), one may choose a random function \(\psi:V(H)\to V(G)\) uniformly among all functions. Then \(t(H,G)\) equals the probability that \(\psi\) is a homomorphism. This connects homomorphism density to sampling-based reasoning and makes it suitable for taking limits.

2.1.3 Density for induced versus non-induced patterns

The definition above corresponds to homomorphisms that respect edges but ignore non-edges. For induced subgraph density, one modifies the requirement to preserve both adjacency and non-adjacency, so that the image of \(H\) matches the induced pattern. Induced densities are often harder to analyze but capture a finer notion of “copying” a pattern faithfully.

2.2 Homomorphism density in multipartite settings

In multipartite or colored graph settings, one can incorporate restrictions on where vertices of \(H\) may map. For instance, if vertices of \(H\) are assigned to parts, the counting can be done with the condition that a vertex mapped from a given part of \(H\) must land in the corresponding part of \(G\). Densities then measure how frequently patterns respect a prescribed partition structure.

2.3 Weighted graphs and generalized densities

More general formulations allow weights on vertices or edges. In weighted graphs, a mapping’s contribution can be multiplied by products of weights corresponding to image vertices and the pattern’s edges. The resulting “generalized homomorphism densities” extend the probability interpretation: rather than uniform random choice over vertices, one uses a weighted sampling scheme dictated by the graph’s weights.

3 Connections to graph limits

3.1 Convergence via homomorphism densities

3.1.1 Left-convergence and consistency of limits

Consider a sequence of graphs \((G_n)\). A common concept is left-convergence: for every fixed pattern graph \(H\), the sequence \(t(H,G_n)\) converges as \(n\to\infty\). Intuitively, the host graphs become increasingly similar with respect to the frequencies of all finite patterns. Consistency refers to the fact that these limiting values must fit together coherently across different patterns.

1.2 Relation to other graph parameters

Homomorphism densities relate to classical graph parameters such as subgraph counts, edge density, and clustering-type statistics. Because \(t(H,G)\) encodes the frequency of many patterns at once, it often refines coarse parameters. In particular, convergence of densities implies convergence of numerous derived quantities expressible through homomorphism counts.

1.3 Moment-style viewpoint on patterns

One may view the family \(\{t(H,G)\}_{H}\) as a “moment sequence” for the graph. Larger patterns act like higher moments that capture increasingly detailed structure. This analogy helps explain why limits can be described by continuous objects: the entire family of pattern frequencies plays the role of complete information.

3.2 Graphons as continuous limit objects

3.2.1 Defining densities using integrals

A graphon is a symmetric measurable function \(W:[0,1]^2\to[0,1]\). For a finite pattern \(H\) with vertex set \(\{1,\dots,k\}\), its density in a graphon is \[ t(H,W)=\int_{[0,1]^k}\prod_{(i,j)\in E(H)} W(x_i,x_j)\,dx_1\cdots dx_k. \] This mirrors the discrete homomorphism density: each \(x_i\) acts like a continuous “random image” of vertex \(i\), and the product enforces edge constraints via \(W\).

3.2.2 Homomorphism densities as graphon functionals

The quantities \(t(H,W)\) depend continuously on \(W\) in appropriate senses and define the graphon’s pattern frequencies. In graph limit theory, these functionals provide a bridge between combinatorial counting and analytic representation. Two graphons that produce the same \(t(H,W)\) for all \(H\) represent the same limiting structure up to a suitable notion of equivalence.

3.2.3 Measure-preserving transformations and invariance

Graphons are considered equivalent under measure-preserving bijections of \([0,1]\). Such transformations rearrange the parameter space without altering the induced pattern densities. As a result, graphon limits capture intrinsic structure rather than artifacts of the chosen coordinate system.

3.3 Compactness and limiting procedures

Compactness arguments show that sequences of graphs have convergent subsequences in the left-convergence sense when viewed through homomorphism densities. Analytically, this corresponds to the compactness of the space of graphons under suitable metrics. Limiting procedures often proceed by showing tightness of pattern frequencies and then identifying the graphon that realizes the limiting density values.

4 Algebraic and analytic perspectives

4.1 Polynomial representations and counting identities

Homomorphism counts can often be expressed via polynomial identities involving adjacency matrices, especially for regular or small structured patterns. In general, \(t(H,G)\) can be written in terms of products that select edges according to the pattern’s edge set. These algebraic forms enable the derivation of identities and relationships among different densities.

4.2 Semigroup/algebra structure of homomorphism counts

Homomorphism densities interact with algebraic operations on patterns. Combining patterns via disjoint unions yields multiplicative behavior: densities of disjoint pieces factor appropriately because homomorphisms act independently on each component. This produces an algebraic structure that is useful for building and characterizing limits.

4.3 Hölder-type inequalities and bounding techniques

Analytic inequalities can bound densities of larger patterns in terms of densities of smaller ones. Inequalities of Hölder or related types appear in bounding products or integrals, translating into combinatorial bounds. Such techniques are central for proving convergence, establishing continuity, and showing that certain families of pattern densities control others.

4.4 Spectral interpretations in special cases

In special situations—such as when studying densities of walks or regular patterns—spectral methods become relevant. Eigenvalues of adjacency operators can encode averaged counts of certain homomorphisms, linking density questions to operator theory. While general homomorphism density is broader than purely spectral information, these interpretations provide intuition and computational leverage in select classes of graphs.

5 Computation and practical considerations

5.1 Efficient counting for restricted pattern classes

Exact evaluation of \(\mathrm{hom}(H,G)\) can be expensive for large \(H\), since it essentially requires checking edge constraints across many mappings. However, for restricted pattern classes (for example, patterns of bounded treewidth or other structural restrictions), one can compute densities using dynamic programming or specialized counting algorithms.

5.2 Exact versus approximate evaluation

5.2.1 Sampling interpretations

Because homomorphism densities have a probability interpretation, they can be approximated via sampling. One draws random maps \(V(H)\to V(G)\) and estimates the proportion that satisfy the homomorphism constraints. For graphons, similar ideas correspond to Monte Carlo integration, sampling points in \([0,1]\) and evaluating the product of \(W(x_i,x_j)\) terms.

5.2.2 Variance and estimator stability

The quality of sampling-based estimators depends on variance, which in turn depends on how structured the host graph is and how sensitive the pattern constraints are. Patterns with rare satisfaction (for example, a complex pattern in a sparse or poorly aligned graph) can yield high variance unless enough samples are drawn. Analytical bounds on variance or concentration can guide the number of samples needed for a reliable estimate.

5.3 Complexity considerations

From a complexity viewpoint, counting homomorphisms is generally hard in worst-case settings. The difficulty depends on the pattern \(H\) and on the graph model (dense versus sparse, labeled versus unlabeled, presence of additional constraints). Many results classify exact and approximate complexity for various fixed patterns, which helps clarify when homomorphism density is computationally tractable.

6 Typical theorems and use-cases

6.1 Extending densities from small to large patterns

A key theme is that knowing densities for a sufficiently rich family of small patterns can determine densities for larger patterns, at least in limiting regimes. This is related to extension theorems and consistency conditions: limiting objects (like graphons) are specified by their values on all finite patterns, and in practice one may approximate using finite subfamilies.

6.2 Characterizations of limit objects via densities

Graph limit theory provides characterizations: a sequence is left-convergent exactly when there exists a graphon whose pattern densities match the limiting values. Thus, the family \(\{t(H,G_n)\}_H\) acts as an alternative description of the limit, and recovering the graphon becomes an identification problem in functional space.

6.3 Robustness under perturbations

Homomorphism densities are stable under certain perturbations of the host graph, particularly when perturbations affect only a small fraction of edges or vertices. Corresponding continuity properties for graphons imply that small changes in the analytic representation lead to small changes in many \(t(H,\cdot)\) values. This robustness is important for both theoretical approximations and empirical estimation.

6.4 Extremal principles and optimization problems

Densities connect to optimization because many extremal graph problems can be phrased as maximizing or minimizing densities of particular patterns, either in finite graphs or in graphon limits. The limiting viewpoint can turn discrete extremal tasks into continuous ones involving integral functionals of graphons, often making variational methods applicable.

7.1 Subgraph density and induced subgraph density

Subgraph density usually refers to densities based on embeddings or counts of (not necessarily induced) copies of a pattern. Induced subgraph density imposes that both edges and non-edges match the pattern. Homomorphism density is closely related but counts edge-respecting maps that may identify vertices, so it does not coincide with induced copy counts without additional constraints.

7.2 Embedding density versus homomorphism density

Embedding counts typically restrict to injective maps, ensuring that distinct vertices of the pattern remain distinct in the host. Homomorphism density allows non-injective maps, making it algebraically smoother and more convenient for limit theory. The distinction matters when collapsing vertices changes the contribution of a mapping.

7.3 Motifs, small substructures, and test graphs

In practice, researchers often focus on a finite list of motifs (small substructures) known as test graphs. Densities of these motifs can act as signatures for a larger graph. This is the basis of many empirical approaches that estimate graph similarity or identify graph regimes by pattern frequencies.

7.4 Testability and approximation frameworks

Testability refers to the ability to approximate a global property of a large graph by checking only small induced subgraphs sampled uniformly. While testability is typically discussed in relation to properties rather than raw densities, homomorphism densities underpin many arguments: they provide the statistical structure needed to formalize what can be inferred from local samples.

8 Worked examples

8.1 Density in complete graphs and empty graphs

Let \(G=K_n\) be the complete graph. Every edge-respecting map from \(H\) to \(K_n\) is unconstrained by missing edges, so \(\mathrm{hom}(H,K_n)\) is maximal. Under the normalization \(t(H,G)=\mathrm{hom}(H,G)/n^{V(H)}\), the limit density depends on whether \(H\) has any edges: if \(H\) has edges, then all maps that send endpoints of each edge to distinct vertices still satisfy adjacency in a complete graph, and collapsed vertices do not break edge constraints for simple graphs; consequently, many densities become close to 1 as \(n\) grows for typical conventions.

For \(G=\overline{K_n}\) (the empty graph), any pattern \(H\) with at least one edge has \(t(H,\overline{K_n})=0\), since no map can send an edge of \(H\) to an edge of \(G\). Patterns without edges have density 1 because every map is edge-respecting when no constraints exist.

8.2 Densities for bipartite patterns

Consider a bipartite pattern \(H\) with vertex set split into two parts, and host graphs that are complete bipartite or nearly so. Homomorphism density reflects whether edge constraints can be satisfied across the partition. In complete bipartite hosts, mappings that respect which pattern vertices must map across the two sides tend to yield high densities, while in hosts missing edges between parts, densities decrease depending on the “coverage” of connections between corresponding neighborhoods.

8.3 Densities in random graphs (high-level behavior)

For an Erdős–Rényi random graph \(G(n,p)\), densities of fixed patterns typically concentrate around values determined by \(p\). Heuristically, each required adjacency behaves like an independent event of probability \(p\), so \(t(H,G(n,p))\) converges (in probability and often almost surely along subsequences) to a deterministic quantity related to \(p^{E(H)}\), with modifications depending on whether vertex collisions are allowed and on the precise normalization. This behavior underlies why homomorphism density provides a natural notion of convergence for random models.

9 Further reading and references

9.1 Canonical sources in graph limit theory

Standard references in graph limit theory develop homomorphism densities, graphons, convergence, and compactness in a unified framework. These sources usually begin with finite graph definitions, then introduce graphons and show equivalence between convergent density sequences and graphon limits. They also cover regularity-type theorems, variational principles, and connections to statistical estimation.

9.2 Background prerequisites in combinatorics and measure theory

A reader typically benefits from familiarity with extremal and probabilistic combinatorics, basic graph theory, and elementary measure/integration concepts. Because graphons are measurable functions on \([0,1]^2\), understanding integrals, measurability, and measure-preserving maps helps make density definitions and invariance statements precise.

9.3 Suggested pathways for deeper study

A productive learning path is to first master the discrete probability interpretation of \(t(H,G)\), then study how integrals define \(t(H,W)\). From there, one can explore convergence theorems (left-convergence), uniqueness up to measure-preserving transformations, and analytic tools such as continuity and concentration. Finally, studying computational and algorithmic aspects of counting motivates why densities are both theoretically central and practically useful.