A 5-regular counterexample to the curvature-dimension self-improvement conjecture

Conjecture 2 of Blachar, Pajot and Salez, Edge-regular graphs with non-negative curvature have polynomial growth asserts that a $d$-regular graph satisfying $\operatorname{CD}(0,\infty)$ must satisfy $\operatorname{CD}(0,d)$. The following connected graph on twelve vertices is a counterexample with $d=5$.

The verification has two parts. At every vertex, completing squares reduces nonnegative curvature to positivity of a small matrix. The exact determinants below establish that positivity, while one integer-valued function violates the stronger dimension-five inequality.

1. The graph and curvature convention

Let $V=\{0,1,\ldots,11\}$. Define a simple undirected graph by the following neighborhoods:

$v$	$N(v)$
$0$	$\{1,2,3,4,5\}$
$1$	$\{0,2,3,6,7\}$
$2$	$\{0,1,6,7,9\}$
$3$	$\{0,1,7,10,11\}$
$4$	$\{0,8,9,10,11\}$
$5$	$\{0,8,9,10,11\}$
$6$	$\{1,2,7,8,10\}$
$7$	$\{1,2,3,6,11\}$
$8$	$\{4,5,6,9,11\}$
$9$	$\{2,4,5,8,10\}$
$10$	$\{3,4,5,6,9\}$
$11$	$\{3,4,5,7,8\}$

The table is symmetric and each row contains five distinct vertices other than its row label. Thus the graph is simple, undirected and 5-regular. Every vertex is at distance at most two from $0$, so it is connected.

We use the unnormalized Laplacian and the curvature conventions of the conjecture:

$$\Delta f(x)=\sum_{y\sim x}\bigl(f(y)-f(x)\bigr),$$ $$\begin{gathered} \Gamma_1(f,g)(x)\\ =\frac12\sum_{y\sim x} \bigl(f(y)-f(x)\bigr)\bigl(g(y)-g(x)\bigr), \end{gathered}$$ $$\begin{aligned} \Gamma_2(f,f) ={}&\frac12\Delta\Gamma_1(f,f)\\ &-\Gamma_1(f,\Delta f). \end{aligned}$$

For $N\in(0,\infty]$, the condition $\operatorname{CD}(0,N)$ means that, for every function $f:V\to\mathbb R$ and every vertex $x\in V$,

$$\Gamma_2(f,f)(x)\ge\frac{(\Delta f(x))^2}{N}.$$

Here $1/\infty=0$, so $\operatorname{CD}(0,\infty)$ is the nonnegativity of every local quadratic form $\Gamma_2(f,f)(x)$.

2. A local certificate for nonnegative curvature

Curvature-matrix reductions through Schur complements are standard; see Cushing, Kamtue, Liu and Peyerimhoff, Theorem 1.2. We include the needed identity directly.

Fix a vertex $x$, and list its neighbors increasingly as $y_1,\ldots,y_5$. Let $A_x$ be the adjacency matrix induced on these five neighbors, and put

$$t_i=\sum_{j=1}^5(A_x)_{ij}.$$

Write $t=(t_1,\ldots,t_5)$. Let $S_2(x)$ be the set of vertices at distance exactly two from $x$. For each $z\in S_2(x)$, define

$$\begin{aligned} (b_z)_i&=\mathbf 1_{\{y_i\sim z\}},\\ m_z&=\sum_{i=1}^5(b_z)_i. \end{aligned}$$

In particular, $m_z>0$. With $I$ the $5\times5$ identity matrix and $J$ the $5\times5$ all-ones matrix, set

$$\begin{aligned} R_x={}&\frac52 I+\frac14\operatorname{diag}(t)\\ &+\frac12J-A_x\\ &-\sum_{z\in S_2(x)}\frac{b_zb_z^{T}}{m_z}. \end{aligned}$$

Subtracting a constant from $f$ does not change either $\Gamma_2(f,f)$ or $\Delta f$, so assume $f(x)=0$, and write $u_i=f(y_i)$. Expanding the definitions and completing the square separately in each $f(z)$ gives

$$\begin{aligned} &\Gamma_2(f,f)(x)=u^{T}R_xu\\ &\quad+\frac14\sum_{z\in S_2(x)} m_z\left(f(z)-\frac{2b_z^{T}u}{m_z}\right)^2. \end{aligned}$$

For clarity, the terms before completing the squares are

$$\begin{aligned} &\Gamma_2(f,f)(x)\\ &\quad=u^{T}\!\left( \frac52I+\frac14\operatorname{diag}(t)+\frac12J-A_x \right)u\\ &\qquad+\sum_{z\in S_2(x)} \left(\frac{m_z}{4}f(z)^2-f(z)b_z^{T}u\right). \end{aligned}$$

Thus positive semidefiniteness of $R_x$ implies nonnegative curvature at $x$.

For $1\le k\le5$, let $D_{x,k}$ be the determinant of the leading $k\times k$ principal submatrix of $R_x$, using the increasing neighbor order above. Substitution of the adjacency table into the definition of $R_x$ gives the following exact values. The equal rows for vertices $4$ and $5$ are combined.

$x$	$D_{x,1}$	$D_{x,2}$	$D_{x,3}$
$0$	$8/3$	$34/9$	$3175/432$
$1$	$3/2$	$31/8$	$71/8$
$2$	$23/12$	$281/48$	$439/32$
$3$	$9/4$	$409/72$	$239/18$
$4,5$	$29/30$	$157/60$	$273/40$
$6$	$8/3$	$55/9$	$233/18$
$7$	$41/12$	$161/24$	$793/48$
$8$	$11/4$	$15/2$	$21/4$
$9$	$1/3$	$11/12$	$5/2$
$10$	$4/3$	$37/12$	$55/8$
$11$	$25/12$	$671/144$	$5687/576$

$x$	$D_{x,4}$	$D_{x,5}$
$0$	$16277/1728$	$335/288$
$1$	$503/32$	$5107/128$
$2$	$791/32$	$3041/192$
$3$	$1379/108$	$1969/108$
$4,5$	$1301/96$	$39869/1920$
$6$	$457/36$	$163/36$
$7$	$1175/32$	$5599/384$
$8$	$12$	$339/16$
$9$	$187/36$	$82/9$
$10$	$451/64$	$5555/384$
$11$	$12859/2304$	$4807/768$

Every entry is positive. By Sylvester's criterion, each $R_x$ is positive definite. The square decomposition therefore proves that, for every function $f:V\to\mathbb R$ and every vertex $x\in V$,

$$\Gamma_2(f,f)(x)\ge0.$$

Consequently, this graph satisfies $\operatorname{CD}(0,\infty)$.

3. Failure of the dimension-five bound

Define the integer-valued function $f$ by the following values:

$v$	$f(v)$	$v$	$f(v)$
$0$	$0$	$6$	$-2$
$1$	$-1$	$7$	$0$
$2$	$-1$	$8$	$10$
$3$	$2$	$9$	$6$
$4$	$5$	$10$	$8$
$5$	$5$	$11$	$8$

At vertex $0$, the neighborhood table gives

$$\begin{aligned} \Delta f(0)&=-1-1+2+5+5\\ &=10. \end{aligned}$$

The remaining quantities needed in the definition of $\Gamma_2$ are

$$\begin{aligned} \Gamma_1(f,f)(0)&=28,\\ \sum_{y\sim0}\Gamma_1(f,f)(y)&=\frac{291}{2},\\ \Delta\Gamma_1(f,f)(0)&=\frac{11}{2}. \end{aligned}$$

Moreover,

$$\begin{gathered} \bigl(\Delta f(1),\ldots,\Delta f(5)\bigr)\\ =(4,8,5,7,7), \end{gathered}$$

and hence

$$\begin{aligned} &2\Gamma_1(f,\Delta f)(0)\\ &=(-1)(4-10)+(-1)(8-10)\\ &\quad+2(5-10)+5(7-10)\\ &\quad+5(7-10)\\ &=-32. \end{aligned}$$

It follows that

$$\begin{aligned} \Gamma_2(f,f)(0)&=\frac12\cdot\frac{11}{2}-(-16)\\ &=\frac{75}{4}. \end{aligned}$$

But $\operatorname{CD}(0,5)$ would require

$$\Gamma_2(f,f)(0)\ge\frac{(\Delta f(0))^2}{5}=20,$$

whereas $75/4<20$. The graph therefore satisfies $\operatorname{CD}(0,\infty)$ but not $\operatorname{CD}(0,5)$, disproving Conjecture 2.