Sharp lower bounds for the minimal growth rate of a graph with connected complement: McMullen's questions $\lambda(G) \geq |V(G)|$ and $\lambda(G) \geq 2^n$

For a finite graph $G$ with positive vertex weights $w$, McMullen's clique polynomial $Q(t) = \sum_K (-1)^{|K|} t^{w(K)}$, summed over the cliques $K$ of $G$, packages the weighted growth of the positive semigroup of the right-angled Artin group $W(G)$: the smallest positive zero of $Q$ equals $1/\lambda(G,w)$, where $\lambda(G,w)$ is the exponential growth rate of the number of semigroup elements of weight at most $T$. Minimizing $\lambda(G,w)$ over admissible weights (those with $w(K) \leq 1$ on every clique) defines an invariant $\lambda(G)$ that governs which exponential growth rates the group can realize and enters the theory of entropy of graph actions and of Perron-Frobenius integer matrices. At the end of Section 6 of 'Entropy and the clique polynomial' (2015), McMullen asks two open questions under the hypotheses that the complement graph $G'$ is connected and $|V(G)| > 1$: (a) is $\lambda(G) \geq |V(G)|$? and (b) if $G$ contains a clique of order $n$, is $\lambda(G) \geq 2^n$? Both bounds are sharp: $\lambda(nA_1) = n$ for $n$ isolated vertices, and $\lambda(K_n + A_1) = 2^n$ for a complete graph with one added isolated vertex, so neither constant can be improved. Both questions remain open, with no published resolution known to date; the best general lower bound under this hypothesis remains the paper's own Ramsey-type estimate $\lambda(G) \geq \lambda_n$, where the Ramsey parameter $n$ satisfies $|V(G)| \geq \binom{2n-2}{n-1}$ (so $n$ is of order $\log_2 |V(G)|$) and $\lambda_n$ is of order $n/\log n$, i.e., a bound of order $\log|V(G)|/\log\log|V(G)|$ in the number of vertices. A companion open problem stated in the same paper - that $\liminf \eta_g^g > 0$ for the minimal spectral radius $\eta_g$ of symplectic integer matrices, which the paper notes is equivalent to the Schinzel-Zassenhaus conjecture - has since been resolved affirmatively by Dimitrov's proof of that conjecture.

Background

Let $G$ be a finite, undirected, simple graph. The right-angled Artin group $W(G)$ is presented by one generator per vertex, with two generators commuting exactly when the corresponding vertices are joined by an edge. Its positive semigroup $W(G)^+$ consists of the elements expressible as products of the vertex-generators; since commuting generators may be reordered, for any assignment $w : V(G) \to \mathbb{R}^+$ of positive vertex weights the weight $w(g) = \sum_i w(a_i)$ of such a product is independent of the word chosen to express $g$. The weighted growth rate is $\lambda(G,w) = \lim_{T \to \infty} N(T)^{1/T}$, where $N(T)$ counts semigroup elements $g$ with $0 < w(g) \leq T$. McMullen's clique polynomial $Q(t) = \sum_K (-1)^{|K|} t^{w(K)}$ - the sum runs over all cliques $K$ of $G$ (complete subgraphs, including the empty one), with $w(K) = \sum_{v \in K} w(v)$ - encodes this growth exactly: by Theorem 1.3 of the source paper, the smallest positive zero of $Q$ equals $1/\lambda(G,w)$, and $h(w) = \log \lambda(G,w)$ is convex; when the complement graph $G'$ (same vertex set, two distinct vertices adjacent exactly where $G$ has no edge) is connected and $|V(G)| > 1$, $h$ is strictly convex, real-analytic, and tends to infinity at the boundary of the cone of positive weights. A weight is admissible if $w(K) \leq 1$ for every clique $K$; this normalization fixes the scale of the weights. The minimal growth rate of $G$ is $\lambda(G) = \inf\{\lambda(G,w) : w \text{ admissible}\}$. The same paper develops the parallel theory of metrized directed graphs (directed graphs whose edges carry positive real lengths), where the Perron polynomial - the determinant of $I$ minus the length-weighted adjacency matrix - plays the role of $Q$ and the growth rate counts closed paths; with integral edge-lengths this connects $\lambda$ to spectral radii (the largest modulus of an eigenvalue) of adjacency matrices of nonnegative integer matrices, and hence to questions about small eigenvalues of integer matrices and the entropies of surface dynamical systems. The complement-connectivity hypothesis structures the problem. The join $G \ast H$ of two graphs is their disjoint union with all cross edges added; $W(G \ast H) \cong W(G) \times W(H)$ (a direct product), and growth rates multiply: $\lambda(G \ast H) = \lambda(G)\lambda(H)$ (equation (6.2) of the paper). Every graph factors canonically as a join $G = G_1 \ast \cdots \ast G_k$ where the $G_i'$ are the connected components of $G'$; graphs with $G'$ connected are called prime, and only the prime case is essential. The hypothesis is also necessary for any bound in terms of vertex or clique counts: the complete graph $K_n$ has $W(K_n) \cong \mathbb{Z}^n$, polynomial growth, and $\lambda(K_n) = 1$, while the complement of $K_n$ is totally disconnected. Two cone subtleties matter for extremal arguments: if $G = A_1 \ast H$ (one vertex joined to all of $H$) with $\lambda(H) > 1$, then $\lambda(G) = \lambda(H)$ but the infimum is not attained - the optimal weight degenerates, vanishing on the cone vertex. The known sharp values calibrate the questions (throughout, $A_m$ denotes the path graph with $m$ vertices, and $nG$ denotes the disjoint union of $n$ copies of $G$). For $nA_1$ ($n$ isolated vertices, so $W$ is the free product of $n$ copies of the integers, realized as the free group on $n$ generators at the semigroup level): $Q(t) = 1 - nt$ and $\lambda(nA_1) = n$, with connected complement $K_n$. For $K_n + A_1$ ($K_n$ plus one isolated vertex, complement the star $K_{1,n}$, hence connected, containing an $n$-clique): with clique weights $1/n$ on the $K_n$ factor and weight $1$ on the isolated vertex, $Q(t) = (1 - t^{1/n})^n - t$, whose smallest positive zero is $t = 2^{-n}$, so $\lambda(K_n + A_1) = 2^n$ exactly. Further values: $\lambda(A_2) = 1$ (a single edge, $W \cong \mathbb{Z}^2$), $\lambda(A_3) = 2$, $\lambda(A_2 + nA_1) = (1 + \sqrt{n})^2$, and $\lambda(2A_2) = 6 + 4\sqrt{2}$ (two disjoint edges). What is known in general under the connected-complement hypothesis comes from the source paper: by Theorem 6.1, for fixed $M$ only finitely many graphs with connected complement have $\lambda(G) \leq M$, proved via a Ramsey-theoretic argument: by Ramsey theory, if $|V(G)| \geq \binom{2n-2}{n-1}$, then either $G$ or its complement $G'$ contains a clique of order $n$. In the branch where $G'$ contains the clique (so $G$ contains $nA_1$ as an induced subgraph), monotonicity gives $\lambda(G) \geq \lambda(nA_1) = n$; in the branch where $G$ itself contains the clique $K$ of order $n$, the optimal weight satisfies $w(a) \leq 1/n$ for some $a \in K$, and a two-vertex induced subgraph then gives $\lambda(G) \geq \lambda_n$, where $1/\lambda_n$ is the smallest positive root of $1 - t^{1/n} - t$ and $\lambda_n$ grows like $n/\log n$. Since the Ramsey parameter $n$ satisfying $|V(G)| \geq \binom{2n-2}{n-1}$ is of order $\log_2 |V(G)|$, the resulting general lower bound is of order $\log|V(G)|/\log\log|V(G)|$. By Theorem 1.5, only finitely many graphs with connected complement satisfy $1 < \lambda(G) \leq M$; and by Theorem 1.6, the graphs with connected complement and $1 < \lambda(G) < 8$ are exactly $nA_1$ for $2 \leq n \leq 7$, $A_2 + A_1$, $A_2 + 2A_1$, $A_2 + 3A_1$, $A_3 + A_1$, and $K_{1,3} + A_1$. The two open questions ask whether the true general lower bounds are the sharp linear and exponential ones rather than this Ramsey-type bound of order $\log|V(G)|/\log\log|V(G)|$. For context on the arithmetic side of the same paper: Theorem 1.1 determines the minimum spectral radius over reciprocal Perron-Frobenius matrices $A \in M_{2g}(\mathbb{Z})$ (nonnegative integer matrices, with strongly connected directed graph, whose eigenvalues are invariant under $\mu \mapsto \mu^{-1}$) as the largest root of $t^{2g} - t^g(1 + t + t^{-1}) + 1$, whence $\rho(A)^g \geq (3 + \sqrt{5})/2$ - a result motivated by lower bounds for the entropies of pseudo-Anosov mapping classes of surfaces (the irreducible, exponentially stretching homeomorphisms in the Nielsen-Thurston classification of surface maps).

Problem Statement

Let $G$ be a finite, undirected, simple graph with vertex set $V(G)$, and let $G'$ denote its complement (same vertices; two distinct vertices adjacent in $G'$ exactly when they are not adjacent in $G$). The right-angled Artin group $W(G)$ is the group presented by one generator $a_v$ for each vertex $v \in V(G)$, with the relations $a_u a_v = a_v a_u$ exactly when $u$ and $v$ are joined by an edge of $G$; its positive semigroup $W(G)^+$ consists of the elements expressible as products of the vertex-generators. Since commuting generators may be reordered, for any assignment $w : V(G) \to \mathbb{R}^+$ of positive vertex weights, the weight $w(g) = \sum_i w(a_i)$ of such a product is independent of the word chosen to express $g$. Let $N(T)$ denote the number of semigroup elements $g \in W(G)^+$ with $0 < w(g) \leq T$, and let $\lambda(G,w) = \lim_{T \to \infty} N(T)^{1/T}$ be the resulting exponential growth rate. By Theorem 1.3 of McMullen's paper 'Entropy and the clique polynomial', $\lambda(G,w)$ equals the reciprocal of the smallest positive zero of the clique polynomial $Q(t) = \sum_K (-1)^{|K|} t^{w(K)}$, where the sum runs over all cliques $K$ of $G$ (complete subgraphs, including the empty one, and $w(K) = \sum_{v \in K} w(v)$). A weight $w$ is admissible if $w(K) \leq 1$ for every clique $K$; the minimal growth rate of $G$ is $\lambda(G) = \inf\{\lambda(G,w) : w \text{ admissible}\}$. McMullen's two questions, posed at the end of Section 6 of that paper, are: (a) If $G'$ is connected and $|V(G)| > 1$, is $\lambda(G) \geq |V(G)|$? (b) If $G'$ is connected, $|V(G)| > 1$, and $G$ contains a clique of order $n$, is $\lambda(G) \geq 2^n$? Both bounds are sharp and therefore optimal up to equality: for $G = nA_1$ ($n$ isolated vertices) the complement is the complete graph $K_n$, which is connected, and $\lambda(G) = n = |V(G)|$; for $G = K_n + A_1$ ($K_n$ with one added isolated vertex) the complement is the star $K_{1,n}$ (one center vertex joined to $n$ leaves), which is connected, $G$ contains a clique of order $n$, and $\lambda(G) = 2^n$. The two questions share the same hypothesis and the same objective - sharp lower bounds on $\lambda(G)$ in terms of elementary graph parameters - and are stated together in the source.

References

1. Curtis T. McMullen. Entropy and the clique polynomial. Journal of Topology 8 (2015), no. 1, 184-212. DOI: 10.1112/jtopol/jtu022. URL: https://doi.org/10.1112/jtopol/jtu022
2. Vesselin Dimitrov. A proof of the Schinzel-Zassenhaus conjecture on polynomials. arXiv:1912.12545 (2019). URL: https://arxiv.org/abs/1912.12545
3. Livio Liechti. On the arithmetic and the geometry of skew-reciprocal polynomials. Proceedings of the American Mathematical Society 147 (2019), no. 12, 5131-5139. DOI: 10.1090/proc/14668. URL: https://doi.org/10.1090/proc/14668 (preprint: arXiv:1812.04918, https://arxiv.org/abs/1812.04918)
4. Erwan Lanneau, Livio Liechti, and Chi Cheuk Tsang. Minimal stretch factors of orientation-reversing fully-punctured pseudo-Anosov maps. Transactions of the American Mathematical Society 378 (2025), no. 4, 2943-2968. DOI: 10.1090/tran/9350. URL: https://doi.org/10.1090/tran/9350 (preprint: arXiv:2402.15369, https://arxiv.org/abs/2402.15369)
5. Eriko Hironaka and Chi Cheuk Tsang. Standardly embedded train tracks and pseudo-Anosov maps with minimum expansion factor. Groups, Geometry, and Dynamics 19 (2024), no. 4, 1263-1317. DOI: 10.4171/ggd/805. URL: https://doi.org/10.4171/ggd/805 (preprint: arXiv:2210.13418, https://arxiv.org/abs/2210.13418)
6. Mehdi Yazdi. Lower bound for dilatations. Journal of Topology 11 (2018), no. 3, 602-614. DOI: 10.1112/topo.12061. URL: https://doi.org/10.1112/topo.12061 (preprint: arXiv:1610.04278, https://arxiv.org/abs/1610.04278)
7. Vsevolod Gubarev. PC-polynomial of graph. arXiv:1808.03932 (2018). URL: https://arxiv.org/abs/1808.03932
8. A. Schinzel and H. Zassenhaus. A refinement of two theorems of Kronecker. Michigan Mathematical Journal 12 (1965), no. 1, 81-85. DOI: 10.1307/mmj/1028999247. URL: https://doi.org/10.1307/mmj/1028999247