The universal golden-ratio threshold for decorated unicyclic graphs

Two adjacent pendant stars violate the golden-ratio balance threshold

Conjecture 5.10 of Bai, Discrete Einstein metrics on unicyclic graphs asserts that a fixed decoration of a long cycle is eventually balanced whenever its limiting largest Ricci-matrix eigenvalue is less than $(\sqrt5-2)/2$. The following fixed decoration is a counterexample: attach 198 pendant leaves to each of two adjacent cycle vertices.

Bai's Proposition 5.8 establishes the threshold for decorations at a single cycle vertex. Here the decoration occupies two adjacent vertices.

The large stars make the coupling across their common cycle edge weak. That edge nevertheless carries a large fraction of the cycle perimeter. The calculation below constructs the positive eigenvector directly and proves both failure of balance and convergence of the eigenvalue. It does not concern whether a different, unbalanced Einstein metric exists.

1. The graph and the balance condition

For every integer $g\ge9$, start with the simple cycle $C_g$ and choose an edge $e_0=\{v_0,v_1\}$. Attach 198 new leaves to $v_0$ and another 198 new leaves to $v_1$. Call the resulting graph $G_g$.

Thus $v_0$ and $v_1$ have degree 200, the other cycle vertices have degree two, and all new vertices have degree one. The graph is finite, simple, connected and unicyclic. Its decoration is independent of $g$.

Write $d_v$ for the degree of vertex $v$, and let $\mathrm{Id}$ denote the identity matrix on the edge-coordinate space. We use the source's symmetric matrix $R_G$, indexed by edges. For $e=\{x,y\}$,

$$(R_G)_{e,e}=-\left(\frac1{d_x}+\frac1{d_y}\right).$$

For distinct edges $e,e'$ meeting at $z$, its entry is $1/d_z$; for disjoint edges it is zero. The matrix $R_G+2\mathrm{Id}$ is nonnegative and irreducible. Therefore a strictly positive eigenvector of $R_G$ must be its Perron eigenvector.

If the cycle-edge weights have total $L$, balance requires the sum of every three consecutive cycle-edge weights to be at most $L/2$. We will violate this at $e_0$ for every $g\ge9$.

2. An explicit positive eigenvector

Put $n=g-1$. List the edges of the other arc from $v_1$ to $v_0$ as $e_1,\ldots,e_n$. For a parameter $\mu>1$, define

$$r=\mu^{-1},\qquad \lambda=\frac{(\mu-1)^2}{2\mu}.$$

Give the arc edges the positive weights

$$\begin{gathered} z_j=\frac{r^{j-1}+r^{n-j}}{1+r^{n-1}},\\ 1\le j\le n. \end{gathered}$$

In particular $z_1=z_n=1$. At every edge whose endpoints both have degree two, the eigenvector equation is

$$\lambda z_j=-z_j+\frac{z_{j-1}+z_{j+1}}2.$$

Our weights satisfy it because $r+r^{-1}=2(1+\lambda)$.

Let $b$ be the weight of $e_0$, and give every pendant edge the weight

$$y=\frac{b+1}{200\lambda+4}.$$

This is exactly its eigenvector equation: at a pendant edge the other edges incident to its degree-200 endpoint have weights $b$, $1$, and 197 copies of $y$. Consequently that row reduces to

$$(200\lambda+4)y=b+1.$$

Introduce

$$\begin{aligned} P&=\frac{200\lambda+202}{200(200\lambda+4)},\\ T&=\frac{200\lambda-194}{200(200\lambda+4)},\\ D&=\lambda+2T. \end{aligned}$$

Substituting the pendant weights into the remaining three cycle-edge equations gives

$$\begin{aligned} Db&=2P,\\ Pb&=\lambda+\frac12+T-\frac{z_2}{2}. \end{aligned}$$

The second equation serves for both $e_1$ and $e_n$, by reflection. Define

$$\begin{aligned} H_n(\mu) &=\lambda+\frac12+T\\ &\quad-\frac{r+r^{n-2}}{2(1+r^{n-1})},\\ F_n(\mu)&=H_n(\mu)D-2P^2. \end{aligned}$$

Whenever $D>0$ and $F_n(\mu)=0$, taking $b=2P/D$ makes every row of the original matrix equation hold. All weights are then strictly positive, so this is the Perron eigenvector and its eigenvalue is $\lambda$.

3. A root in a fixed rational interval

Set

$$\alpha=\frac{77}{50},\qquad \beta=\frac{31}{20},\qquad I=[\alpha,\beta].$$

Let

$$\begin{aligned} H(\mu)&=\frac{\mu-1}{2}+T,\\ F(\mu)&=H(\mu)D-2P^2. \end{aligned}$$

The relation between the finite-arc and limiting equations is

$$\begin{aligned} F_n(\mu)&=F(\mu)\\ &\quad-\frac{D}{2}\, \frac{r^{n-2}(1-r^2)}{1+r^{n-1}}. \end{aligned}$$

All these functions are continuous on $I$. Direct rational substitution gives

$$\begin{aligned} D(\alpha)&=\frac{124727}{6799100}>0,\\ H(\alpha)&=\frac{20471}{88300}>0,\\ F(\alpha)&=-\frac{23913}{61810000}<0,\\ F(\beta)&=\frac{9427}{8370000}>0. \end{aligned}$$

The function $\lambda(\mu)$ is strictly increasing for $\mu>1$. As functions of $\lambda$,

$$\begin{aligned} \frac{dP}{d\lambda} &=-\frac{198}{(200\lambda+4)^2},\\ \frac{dT}{d\lambda} &=\frac{198}{(200\lambda+4)^2}. \end{aligned}$$

Hence $P$ is positive and decreasing on $I$, while $H$ and $D$ are positive and strictly increasing. In particular $F$ is strictly increasing there.

For $n\ge8$, the correction at $\beta$, where $r=20/31$, satisfies

$$\begin{gathered} 0<F(\beta)-F_n(\beta)\\ \le\frac{D(\beta)}2\left(\frac{20}{31}\right)^6. \end{gathered}$$

The remaining margin is positive:

$$\begin{aligned} &F(\beta) -\frac{D(\beta)}2\left(\frac{20}{31}\right)^6\\ &\qquad=\frac{6310691602361}{22285217429910000}>0. \end{aligned}$$

Thus $F_n(\alpha)<0<F_n(\beta)$ for every $n\ge8$. The intermediate value theorem supplies a root $\mu_n\in(\alpha,\beta)$. The construction in Section 2 gives a positive eigenvector, and therefore

$$\lambda_{\max}(R_{G_{n+1}}) =\frac{(\mu_n-1)^2}{2\mu_n}.$$

4. Failure of balance for every $g\ge9$

Since $P$ decreases and $D$ increases while both remain positive, the central-edge weight satisfies

$$\begin{aligned} b&=\frac{2P(\mu_n)}{D(\mu_n)}\\ &\ge\frac{2P(\beta)}{D(\beta)}\\ &=\frac{47306}{11743}>4. \end{aligned}$$

The total weight on the other arc is

$$\begin{aligned} S_n:=\sum_{j=1}^n z_j &=\frac{2(1-r^n)}{(1-r)(1+r^{n-1})}\\ &<\frac2{1-r} \le\frac{154}{27}<8. \end{aligned}$$

Here $r=1/\mu_n\le50/77$. The three consecutive edges $e_n,e_0,e_1$ have weight $b+2$, and the cycle perimeter is $L=b+S_n$. Since $b+4>8>S_n$,

$$2(b+2)>b+S_n=L.$$

The Perron metric is therefore unbalanced for every $g\ge9$.

5. Every edge is geodesic

The source excludes degenerate cycle weightings in which one edge exceeds half the perimeter. The counterexample also satisfies this additional convention: every cycle edge is strictly shorter than its complementary cycle arc.

To see this, let $\gamma=37/24$, so $\alpha<\gamma<\beta$. A further exact evaluation gives

$$F(\gamma)=-\frac{37321961}{272420640000}<0.$$

Thus $F_n(\gamma)<0<F_n(\beta)$ for every $n\ge8$. Applying the intermediate value theorem on $(\gamma,\beta)$ gives a positive eigenvector by Section 2. Its eigenvalue must be the same Perron eigenvalue constructed in Section 3. Since $\lambda(\mu)$ is strictly increasing, its parameter is the same $\mu_n$. Consequently $\mu_n>\gamma$, and monotonicity of $2P/D$ gives

$$\begin{aligned} b&<\frac{2P(\gamma)}{D(\gamma)}\\ &=\frac{21786636}{4356133} <\frac{51}{10}. \end{aligned}$$

On the other hand, $20/31<r<2/3$ and $n\ge8$. The exact arc-sum formula therefore yields

$$\begin{aligned} S_n &>\frac{2\bigl(1-(2/3)^8\bigr)} {(11/31)\bigl(1+(2/3)^7\bigr)}\\ &=\frac{78182}{15279} >\frac{51}{10}. \end{aligned}$$

In particular $b<S_n$, so the central edge has $b<L/2$. Every other cycle-edge weight satisfies $z_j\le1$, since

$$\begin{aligned} &1+r^{n-1}-r^{j-1}-r^{n-j}\\ &\qquad=(1-r^{j-1})(1-r^{n-j})\ge0. \end{aligned}$$

As $L>b>4$, these edges also have $z_j<L/2$. Pendant edges are bridges and therefore automatically geodesic. The entire positive weighting is thus geodesic, despite its failure of the stronger three-edge balance condition.

6. The limiting eigenvalue is below the threshold

On $I$, the finite equations converge uniformly to the limiting equation, because

$$\begin{gathered} 0\le F(\mu)-F_n(\mu)\\ \le\frac{D(\beta)}2 \left(\frac{50}{77}\right)^{n-2}. \end{gathered}$$

The strictly increasing function $F$ has a unique zero $\mu_\infty\in(\alpha,\beta)$. Every convergent subsequence of $\mu_n$ has to converge to that zero, by uniform convergence and $F_n(\mu_n)=0$. Compactness of $I$ then gives $\mu_n\to\mu_\infty$.

Consequently the limit required in the conjecture exists and satisfies

$$\begin{aligned} \lambda_\infty &=\frac{(\mu_\infty-1)^2}{2\mu_\infty}\\ &<\frac{121}{1240} <\frac1{10} <\frac{\sqrt5-2}{2}. \end{aligned}$$

The last inequality follows from $5>(11/5)^2$. Thus a fixed decoration has limiting Perron eigenvalue strictly below the proposed golden-ratio threshold while failing balance for every sufficiently large cycle length. This disproves Conjecture 5.10.