TOPICS
Search

Subgraph Count


The subgraph count N(G,H) is the number of distinct subgraphs of a finite simple graph G that are isomorphic to a fixed graph H (Alon 1986). Copies need not be induced, and different labelings of the same copy are counted only once. The definition extends to hypergraphs by counting their subhypergraphs. For an integer r>=2 and a fixed nonempty finite simple r-uniform hypergraph H without isolated vertices, let N_r(m,H) be the maximum count over finite simple r-uniform hosts with exactly m hyperedges. The exclusion of isolated vertices is necessary, since arbitrarily many isolated host vertices can be added without changing m.

Kuang et al. (2026, Theorem 1.2) proved that there is a constant lambda_r(H)>0 such that

 N_r(m,H)=(lambda_r(H)+o(1))m^(rho^*(H)),
(1)

where rho^*(H) is the fractional edge cover number and m->infty, with H and r fixed. This strengthens the earlier order-of-magnitude result of Friedgut and Kahn (1998) to convergence of the normalized count. For graphs, it proves the conjecture of Alon (1986). The count of labeled embeddings is |Aut(H)|N_r(m,H), where Aut(H) is the automorphism group of H. Its leading constant is at most (r!)^(rho^*(H)), and equals this value whenever rho^*(H)=|V(H)|/r.

The leading constant has a variational description over finite hypergraphs and weights. For every 0<epsilon<1, any host can be replaced by a complete blow-up of a hypergraph with at most O_H(epsilon^(-3)) vertices, without increasing its number of hyperedges and while retaining at least a proportion 1-epsilon of the embeddings. Here a blow-up replaces each vertex by a class of vertices and every template hyperedge by all choices of one vertex from each of its classes. For graphs, complete finite cores suffice in the variational formula; the weights attain a maximum for each fixed core, but whether some finite core always attains the overall supremum remains open (Kuang et al. 2026, Corollary 1.3 and Problem 5.2).

For the path graph P_l on l vertices, Kuang et al. (2026, Proposition 5.1) also obtained

 N_2(m,P_(2k))=2^(k-1)m^k+O_k(m^(k-1/2)),
(2)
 N_2(m,P_(2k+1))=(c_k/2+o(1))m^(k+1),
(3)

for each fixed positive integer k, where c_k=max_(a in Z, a>=k)(a)_k/a^(k+1) and (a)_k is the falling factorial. The maximum defining c_k is attained. Kuang et al. (2026) credit GPT-6 Astra with extending their graph argument to globally rainbow embeddings and obtaining the hypergraph proof, which the authors verified and rewrote.


See also

Fractional Edge Cover Number, Graph Homomorphism Density, Hypergraph, Subgraph

Explore with Wolfram|Alpha

References

Alon, N. "On the Number of Certain Subgraphs Contained in Graphs with a Given Number of Edges." Israel J. Math. 53, 97-120, 1986. https://doi.org/10.1007/BF02772673.Friedgut, E. and Kahn, J. "On the Number of Copies of One Hypergraph in Another." Israel J. Math. 105, 251-256, 1998. https://doi.org/10.1007/BF02780332.Kuang, P.; Sun, S.; Wang, Y.; and Zeng, J. "Subhypergraph Counts and Proofs of Two Conjectures of Alon." 17 Nov 2026. https://arxiv.org/abs/2606.18321v2.

Cite this as:

Weisstein, Eric W. "Subgraph Count." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SubgraphCount.html

Subject classifications