Bounds on curvature in regular graphs
Peter Ralli

Consistent SPH Simulations of Protostellar Collapse and Fragmentation
    José M. Ramírez-Velasquez1
    December 30, 2023
=====================================================================




We study the curvature-dimension inequality in regular graphs.  We develop techniques for calculating the curvature of such graphs, and we give characterizations of classes of graphs with positive, zero, and negative curvature.  Our main result is to compare the curvature-dimension inequality in these classes to the so-called Ollivier curvature.  A consequence of our results is that in the case that the graph contains no subgraph isomorphic to either K_3 or K_2,3 these curvatures usually have the same sign, and we characterize the exceptions.  




§ INTRODUCTION

Recently there have been several attempts to translate the well-understood concept of curvature from Riemannian geometry to discrete spaces.  In the continuous setting, the Bochner formula characterizes harmonic functions in terms of the curvature.  Based on this, Bakry and Émery <cit.> developed the Curvature-Dimension inequality, which has since been adapted to define curvature in a discrete setting <cit.>.  There have recently been many results on the spectral and isoperimetric properties of graphs under a bound on the CD-curvature <cit.><cit.> with further references therein.

An alternate notion of discrete curvature is the Ollivier curvature, proposed by Y. Ollivier<cit.> and independently by Sammer <cit.> which has been further investigated at length, e.g. <cit.>.  This curvature compares the minimum-transport distance of balls on a curved space to that of balls in Euclidean space.

In this work we investigate the CD-curvature for regular graphs, and compare to the Ollivier curvature.  It is known that these notions are not in general equivalent, indeed, in this work we give examples of graphs for which the curvature is positive in one notion but not the other.  For graphs that are triangle-free and have no subgraph isomorphic to K_2,3, we develop rules for calculating both types of curvature, and observe that the signs of the curvatures are usually equivalent.  We also characterize the classes of graphs for which the signs are not equivalent.  We calculate the curvature for several examples of interest, including the graph of the state space of the random interchange process.

In Section 2, we provide the definitions of both the curvature-dimension inequality and of Ollivier's curvature.  In Sections 3 and 4, we investigate the curvature of regular graphs that have no subgraph isomorphic to either K_3.  In addition we prove a number of short results related to these notions of curvature.



§ PRELIMINARIES
  



 §.§ Curvature-Dimension inequality
 The CD-inequality was introduced in <cit.> and several variations have been studied.  Our definitions follow from <cit.> and we use the non-normalized Laplacian matrix.  For a d-regular graph, the curvature differs from that explored by Chung, Lin, Yau <cit.> by a multiplicative factor of d; those definitions result from choosing a normalized Laplacian.

If G = (V,E) is a locally finite graph and f,g:V→, then


    Γ (f,g)(x) = 1/2∑_y∼ xf(y)-f(x)g(y)-g(x),


    Γ f(x) :=Γ(f,f)(x),


    Δ f(x) = ∑_y∼ x f(y)-f(x),


    and Γ_2 f = 1/2ΔΓ f - Γ(f,Δ f).


Let f:V→ and x∈ V. Because Δ f = Δ (f+c) and Γ f = Γ(f+c), we may (and will) assume that f(x) = 0.  In that case straightforward manipulation (as in <cit.>) reveals a form for Γ_2f(x) that often simplifies computation: 


    2Γ_2f(x) =    1/2∑_u∼ v∼ x
     d(x,u) = 2f(u)-2f(v)^2 + ∑_v∼ xf(v)^2 + ∑_v∼ x4-d(x)-d(v)/2f^2(v)
    
    
     +   ∑_Δ(x,v,u)[2f(v)-f(u)^2 + 1/2f^2(v) + f^2 (u)] ,


where Δ(x,v,u) means that x∼ v∼ u∼ v.

 We say that G satisfies the CD(ρ,∞) condition at x iff for all f:V→, Γ_2f(x)≥ρΓ f(x).

 Whether CD(ρ,∞) is satisfied for G at x is a local property; in particular, it depends only on the structure of edges that are incident to at least one neighbor of x.  It is possible to remove all other edges without affecting the curvature at x.


An obvious concern is to characterize the non-constant function f that minimizes Γ_2f(x)/Γ f(x).  It is understood how to calculate the f(u) if d(x,u) = 2.  A simple optimization reveals that, holding f(v) constant for all v∼ x, the value of f(u) minimizing Γ_2f(x) is 

    f(u) = 2∑_v: x∼ v∼ u f(v)/#{v:x∼ v∼ u}.




 §.§ Ollivier curvature


The second form of discrete curvature that we consider is the so-called Ollivier curvature.

For probability measures μ,ν on V, the L_1 Wasserstein (i.e., minimum-transport) distance is 
    W_1(μ,ν) = min_m ∫_V× V d(x,y) dm(x,y),
 where the minimum is taken over all probability measures m on V× V so that 
    ∫_V m(x,y) dν(y) = μ(x) and ∫_V m(x,y) dμ(x) = ν(y).
  In plain words, we transport μ to ν by shifting a load of size m(x,y) along an (x,y)-geodesic, and W_1 minimizes the average distance transported over all choices of transport function m. 

Let G be a d-regular graph.  For x∈ V, define a probability measure μ_x so that 
    μ_x(v) = 12   if v = x 
    1/2d   if v ∼ x 
    
          0    otherwise.


 If x,y∈ V and x∼ y, the curvature is κ(x,y) = 1-W_1(μ_x,μ_y).




§ K_2,3 AND TRIANGLE-FREE GRAPHS


In this section we compare the CD curvature to Ollivier's curvature for regular graphs that contain no subgraphs isomorphic to either K_3 or K_2,3.

If x∈ V and y,z∼ x, we say that y and z are linked if there is a vertex w≠ x so that y∼ w∼ z.  We write y≈ z if y and z are linked and y≉z if not.

 If x,y∈ V and x∼ y, the non-linking number N_x(y) is the number of other neighbors of x that are not linked to y: |{w∼ x:w≠ y, w≉y}|.

 Let G be d-regular and have no subgraph isomorphic to either K_3 or K_2,3.  Let N = max_y∼ x N_x(y).

(i) If N = 0, then G satisfies CD(ρ,∞) at x iff ρ≤ 2 (G is positively curved at x.)

(ii) If N = 1, then G satisfies CD(ρ,∞) at x iff ρ≤ 0. (G is flat at x.)

(iii) If N ≥ 2, then G does not satisfy CD(0,∞) at x. (G is negatively curved at x.)



Because G has no subgraph isomorphic to K_2,3, if neighbors y,z of x are linked, then they are linked by a unique vertex w, and the link w cannot be adjacent to any neighbor of x other than y and z.


(i) If N=0, then G is locally isomorphic to the hypercube Ω_d. That is, there is a local isomorphism ϕ:V(G)→ V(Ω_d) with the property that Γ_2 f(x) = Γ_2 f∘ϕ(x) and Γ f(x) = Γ f∘ϕ(x) for all f:V→.  It is well-known <cit.> that Ω_d has positive curvature, likewise G has positive curvature.


(ii) To show that CD(ρ,∞) fails at x if ρ > 0, we describe a test-function f for which Γ_2 f (x) = 0:

  Let y,z be a pair of unlinked neighbors of x, set f(x) = 0, f(y) = 1, f(z) = -1.  For any other neighbor of x, set f = 0.  On the second-neighbors of x, set f to be twice the average of f evaluated on all neighbors of x adjacent to that vertex, so as to minimize Γ_2.  Notice that y will be linked to d-2 neighbors of x(all besides z and itself) by d-2 distinct vertices, each with f = 1, and will have one neighbor that is not adjacent to any other neighbor of x, at which f = 2.  Likewise, z will have d-2 neighbors with f = -1 and one neighbor with f = -2.  And, each other neighbor of x will be adjacent to one vertex with f = 1 and one with f = -1: the vertices linking them to y and z respectively.

With this function it is straightforward to see that 2Γ_2 f(x) = 0.


We now show that for any function f, 2Γ_2f(x) ≥ 0, and therefore CD(ρ,∞) holds for any ρ≤ 0:

Because there is a bijection between pairs of linked neighbors of x and the linking vertices,


    1/2∑_u∼ v∼ x
     d(x,u) = 2f(u)-2f(v)^2 ≥1/2∑_y,z∼ x
     y≈ zf(y)-2f(w)^2 + f(z)-2f(w)^2 ≥∑_y,z∼ x
     y≈ zf(y)-f(z)^2,
 where w is the vertex linking y and z, and the sum is taken over all unordered pairs y,z of linked neighbors of x.

Using this in the expression for Γ_2, we find


    2Γ_2f(x)    ≥∑_y,z∼ x
     y≈ zf(y)-f(z)^2+∑_y∼ xf(v)^2 + (2-d)∑_y∼ x f^2(v) 
       = ∑_y∼ x (3-d + #{z∼ x:y≈ z})f^2(y) + ∑_y,z∼ x
     y≈ z2f(y)f(z) 
       ≥∑_y∼ x f^2(y) + ∑_y,z∼ x
     y≈ z2f(y)f(z) ≥∑_y,z∼ x
     y≈ zf(y)-f(z)^2 ≥ 0,
 because each neighbor y of x is linked to at least d-2 of the d-1 other neighbors of x, and not linked to at most 1 other neighbor of x.


(iii).  Let y be a neighbor of x with N_x(y)>1.  Define a test-function f: f(x) = 0, f(y) = d-1, otherwise if z∼ x, f(z) = -1, and choose the values of f on the second-neighbors of x to minimize Γ_2.

It is straightforward to calculate that 
    2Γ_2f(x)    = (∑_z∼ x
     y≈ zf(y)-f(z)^2) + (2-d)[(d-1)^2 + (d-1)]
       ≤ (d-3)d^2 + (2-d)(d^2 - d) = -2d < 0,
 and therefore CD(0,∞) fails at x.  The bound on the first term is due to the fact that y is unlinked to at least 2 of the d-1 other neighbors of x.



We give a similar characterization of the Ollivier curvature:

 Let G be d-regular and have no subgraph isomorphic to either K_3 or K_2,3.  Let N = max_y∼ x N_x(y).

(i) If N = 0, then κ(x,y) > 0.

(ii) If N = 1, then κ(x,y) ≥ 0.

(iii) If N ≥ 2, then κ(x,y) ≤ 0.



(i) As in our previous result G must be locally isomorphic to Ω_d, it is well-known that κ(x,y) = 1d in this case.


(ii) Let y,z be an unlinked pair of neighbors of x, and let v_1,…, v_d-2 be the other neighbors of x.  For each v_i there is a w_i that links v_i and y, let u be the neighbor of y that is not in {x,w_1,…, w_d-2}.  d(u,z)≤ 3 as u∼ y∼ x∼ z.  To bound W_1(μ_x,μ_y) from above, consider the transfer of mass along paths x→ y, v_i → w_i and z→ u.  This gives a bound of W_1(μ_x,μ_y) ≤ 1, and so κ(x,y)≥ 0.


(iii) Let y be a neighbor of x with N_x(y)>1.  We use a test-function f to bound the dual formulation of W_1,
    W_1(μ,ν) = max_f∈ Lip(1)∫ f dμ-∫ f dν.
  For a test-function, set f(x) = 0, f(y) = 1, f(v) = 0 if v is any other neighbor of x, f(w) = 1 if w links y to a neighbor of x, f(u) = 2 if u is any other neighbor of y, and f = 1 on every other vertex, so that f is 1-lipschitz.


    W_1(μ_x,μ_y)≥∫ f dμ_y -∫ f dμ_x = 1 + N-2/2d≥ 1,
 so κ(x,y) ≤ 0.


 κ > 0 is satisfied under hypothesis (ii) for G = C_5, or graphs with similar structure for which (in the language of the proof) d(u,z) = 2.  κ = 0 is satisfied under hypothesis (iii) e.g. for the dodecahedral graph, again because d(u,z) = 2.  

We combine the previous results to show a relationship between the curvatures.

 Let G be d-regular and have no subgraph isomorphic to either K_3 or K_2,3.  Let x∈ V.

(i) If and only if there exists ρ > 0 so that G satisfies CD(ρ,∞) at x, then κ(x,y)>0 for all y∼ x.

(ii) If G satisfies CD(0,∞) at x, then κ(x,y) ≥ 0 for all y∼ x.

(iii) If G does not satisfy CD(0,∞) at x, then there is a vertex y∼ x for which κ(x,y)≤ 0.  If there is a vertex y∼ x for which κ(x,y) < 0, then G does not satisfy CD(0,∞) at x. 



 §.§ Examples

We give examples of graphs with no subgraph isomorphic to K_3 or K_2,3, categorized by which subhypothesis of Theorems 3.1 and 3.2 they satisfy.  Most of these graphs are vertex-transitive, so the curvature is identical at every vertex.

As before, let v be a neighbor of x that is not linked to the largest number of other neighbors of x, and let N be that number.


Common graphs with N=0, satisfying hypothesis (i) include 

  * The hypercube Ω_d.


Common graphs with N = 1, satisfying hypothesis (ii) include



  * The square lattice ^n where n≥ 1.

  * The cyclic graph C_k if k≥ 5.

  * Any product of the above graphs, or product of these graphs with a graph from the previous list.


Common graphs with N > 1, satisfying hypothesis (iii) include



  * The infinite d-regular tree if d≥ 3.

  * Any d-regular graph with girth ≥ 5 if d≥ 3.

  * The graph of triangulations of an n-gon (n≥ 6), with edges representing the action of flipping one interior arc of the polygon.

  * S_n with edges corresponding to adjacent transpositions.




  §.§.§ Interchange Process

Given an underlying graph H = ([n],F), the interchange process labels the vertices of H and at each step, we are allowed to exchange the labels of a pair of adjacent vertices.  Let G be the graph of possible states with an edge between two states if we can move from one state to the other in a single step.  In other words, G is the Cayley graph of the subgroup of S_n with generating set A = {(i,j):{i,j}∈ F}.

G is always K_3-free, and will be K_2,3-free if and only if H is triangle-free.  If x∈ V(G) and a,b∈ A, ax≈ bx iff a and b are not incident to the same vertex as edges of H.  Because of this, we can easily determine the value of N for the interchange process in terms of H.




  * If H is a matching, G satisfies hypothesis (i). 


  * If H is the disjoint union of paths with length ≤ 2 (at least one of which has length equal to 2), G satisfies hypothesis (ii).


  * If H has any vertex of degree ≥ 3 or any path of length ≥ 3, then G satisfies hypothesis (iii). 























 











   

   




















§ TRIANGLE-FREE REGULAR GRAPHS.


In this section we compare the curvature-dimension inequality to the Ollivier curvature for regular triangle-free graphs.  Unlike Section 3, we allow the graph to have K_2,3 as a subgraph.  In this more general case our results are less complete.  In both notions of discrete curvature we give characterizations of classes of graphs with positive curvature, but it remains open to give a full characterization of graphs with positive curvature.

Let G = (V,E) be a triangle-free d-regular graph.

Let u,w be two neighbors of x.  The linkage of u and w is calculated by summing over all vertices z≠ x for which u∼ z∼ w: 
    l(u,w) = ∑_z 1/|{y: x∼ y∼ z}|



 As discussed in Section 2, if G contains no subgraph isomorphic to K_2,3, then there can be at most one vertex z with z≠ x, u∼ z∼ w, which will have {y:x∼ y∑ z} = {u,w}.  In this case l(u,w) = 1/2 and (as before) we say that u and w are linked.   



Let G be a triangle-free graph, and x∈ V(G).  If for every pair u,w of neighbors of x, l(u,w)≥1/2, then G satisfies CD(ρ,∞) at x iff ρ≤ 2.






It is known that any triangle-free graph G fails CD(ρ,∞) if ρ > 2 <cit.>.

Recall that if f is the minimizer of Γ_2f(x)/Γ f(x) and d(x,z) = 2, 
    f(z) = 2/# y: x∼ y∼ z∑_y:x∼ y∼ z f(y).


With this minimization (and the assumption of a triangle-free graph), straightforward algebraic manipulation reveals a form for Γ_2 f:

    2Γ_2 f(x) = ∑_y∼ x (3-d)f^2(y) + ∑_w,y∼ x2f(y) f(w) + ∑_w,y∼ x 2l(w,y) f(w)-f(y)^2


Because l≥ 1/2 we can bound this equation:


    2Γ_2 f(x)    ≥∑_y∼ x (3-d)f^2(y) + ∑_w,y∼ x2f(y) f(w) + ∑_w,y∼ xf(w)-f(y)^2
       = ∑_y∼ x (3-d)f^2(y) + ∑_w,y∼ x2f(y) f(w) +∑_y∼ x (d-1)f^2(y)- ∑_w,y∼ x2f(y)f(w)
       = 2∑_y∼ xf^2(x) = 4Γ f(x),

and therefore CD(2,∞) is satisfied.


We prove a result regarding the Ollivier curvature of a related class of graphs:


Let G be a triangle-free graph. If every pair of adjacent edges of G are contained within exactly one maximal complete bipartite induced subgraph whose parts have equal size, then κ(x,y) = 1/d for all pairs of neighbors x,y. 



Let x,y be a pair of neighboring vertices in G.  The neighbors w of x with w≠ y are partitioned into S_1,...,S_k according to which maximal complete bipartite subgraph contains {xy} and {xw}.  Similarly neighbors of y (other than x) are partitioned into T_1,...,T_k, so that {x}∪ T_i,{y}∪ S_i are the equally sized parts of a maximal complete bipartite graph.

To minimize W_1(μ(x),μ(y)) requires shifting a mass of size |S_i|/2d from vertices of S_i to those in T_i and a mass of size 1/2-1/2d from x to y at a total cost of 1/2-1/2d+1/2d∑_i|S_i| = 1 - 2/2d, this proves the theorem.


Observe that under the hypothesis of Theorem 4.2, a pair of vertices y,w that are neighbors of x will be contained within a copy of K_m,m for some value m≥ 2.  In this case, l(w,y)≥ (m-1)1/m≥ 1/2, so the hypothesis of Theorem 4.1 is also satisfied, and such a graph will have positive curvature both in terms of the CD inequality and Ollivier curvature.

Examples of common graphs:


  * The hypercube Ω_n, where neighbors w and y of x are linked by a unique vertex z, so that x,z,w,y are the vertices of a copy of K_2,2, and l(x,y) = 1/2.  Ω_n satisfies CD(ρ,∞) iff ρ≤ 2 and has κ = 1/n.


  * G = K_n,n for n≥ 2, which has l(y,w) = n-1/n.  K_n,n satisfies CD(ρ,∞) iff ρ≤ 2 and has κ = 1/n.


  * The Cayley graph of S_n generated by all interchanges (ij):i,j∈ [n]:

If y = (ij)x and w=(ik)x, then x,w,y are contained within the copy of K_3,3 that also includes (jk)x,(ijk)x,(jik)x.  In this case l(w,y) = 2/3.

On the other hand if y = (ij)x and w = (kl)x, those vertices are contained within a square that includes x and (ij)(kl)x, and l(w,y) = 1/2.

G satisfies K_n,n satisfies CD(ρ,∞) iff ρ≤ 2 and has κ = 1/n2


  * If X = ([n],E) is a graph, the interchange process on X will always give an |E|-regular triangle-free graph.  If X is a union of disjoint cliques, it is simple to see that G satisfies the hypotheses of Theorems 4.1 and 4.2.  Indeed many of the previous examples are of this type: Ω_d corresponds to X being a perfect matching on 2d vertices, and S_n corresponds to X = K_n.


  * An (n,d,k)-incidence graph is a d-regular bipartite graph with partite sets A_1,A_2 of n elements each so that each pair of elements in A_i share k common neighbors in A_1-i.  In order that such a graph exists, (n-1)k = d(d-1) must count the number of 2-paths starting (and not ending) at x.

Without loss of generality x∈ A_1 and x has neighbors y,w∈ A_2, then y and w share k-1 other neighbors, each of which is adjacent to k neighbors of x.  l(w,y) = k-1/k.  If k≥ 2, an (n,d,k) incidence graph satisfies CD(ρ,∞) iff ρ≤ 2.





§ OTHER RESULTS




 §.§ zig-zag product

The zig-zag product is defined <cit.> for graphs G_1,G_2, where 


  * G_1 is regular with degree d = |V_2|, and for each a∈ V(G_1) the incident edges are indexed by V_2 - so that we can write a[x] for the unique neighbor of a that shares an edge labelled x with a.

  * G_2 is D-regular.

  * The vertex set of the zig-zag product is G_1× G_2.

  * If x∼ y∼ z is a 2-walk in G_2, then (a,x)∼ (a[y],z).


The zig-zag product is a D^2-regular graph that inherits its expansion properties from G_1, which may have much larger degree.  For this reason the zig-zag product is useful in generating expander graphs of bounded degree.  The question arises whether the zig-zag product inherits the curvature properties from G_1 or G_2.  In general this is not the case, we give an example of such a graph:

If G_1 and G_2 are both abelian Cayley graphs, it is not in general true that the zig-zag product will have non-negative curavture: as a simple example if G_1 = Ω_d and G_2 = Z_d with vertices 1…, d labelled in order around the cycle, and x∈ V_1 with y = x[2], z = x[d], then (x,1) has four neighbors - (y,1), (y,3), (z,1), (z,d-1).
(y,1) has neighbors (x,1),(x,3),(y[d],1),(y[d],d-1).

(y,3) has neighbors (x,1),(x,3),(y[4],3),(y[4],5).

(z,1) has neighbors (x,1),(x,d-1),(z[2],1),(z[2],3).

(z,d-1) has neighbors (x,1), (x,d-1),(z[d-2],d-1),(z[d-2],d-3).

G is K_3 and K_2,3-free, we examine which pairs of neighbors of (x,1) are not linked.  We see that (y,3)≉(z,1), (y,3)≉(z,d-1), (y,1)≉(z,d-1).  As such, N=2, and G satisfies hypothesis (iii) of Theorems 3.1-2.

As such, G fails CD(0,∞), and simple calculation gives κ((x,1),(y,3)) = -14.



 §.§ Diameter bounds

It is well-known that a positive lower bound on Ollivier curvature gives an upper bound on the diameter of the graph, according to the following argument developed from <cit.>.

Assume for every pair of neighboring vertices x,y, κ(x,y)≥κ*>0.  Let x_0,…,x_l be a geodesic path, then 
    W_1(μ_x_0,μ_x_l)≤∑_i=1^l W_1(μ_x_i-1,μ_x_i) ≤ l(1-κ*),
 but, considering the 1-Lipschitz function f(y) = d(x_0,y), 
    W_1(μ_x_0,μ_x_l)≥∫ f dμ_x_l-∫ fdμ_x_0≥ (l-12)-(12) = l-1.


Thus l(1-κ*)≥ l-1, and 1≥ lκ*; as the diameter is achieved on a geodesic path, its length D is bounded above by D≤1/κ*.

If G is a d-regular graph with positive curvature, then the diameter is bounded by D≤ 2d.

For any x,z∈ V, μ_x(z) is an integer multiple of 12d.  There is an optimal solution to the minimum-transport problem between μ_x and μ_y with the property that a multiple of 12d is transported along each path used - as each path has integer length, W_1(μ_x,μ_y) is a multiple of 12d.  If x,y are neighbors and κ(x,y) > 0, then it must be κ(x,y) ≥12d.  If x,y are not neighbors, then for any z∼ x along the shortest x-y path, κ(x,y)≥κ(x,z)≥12d.  Thus κ* ≥12d, and D≤ 1/κ* ≤ 2d.


If d is instead an upper bound on the degree of the vertex, then for any x,y,z,w, μ_x(z) and μ_y(w) are both multiples of 1/2d_xd_y, and the same argument follows with κ(x,y)≥1/2d_xd_y≥1/2d^2-2d and thus D≤ 2d^2-2d.



This argument depends in the specifics on the definition of μ_x which is not universal, but for any of the other common definitions I am aware of a similar argument will follow.


 There is no infinite family of bounded-degree graphs with a lower bound on curvature of κ > 0.


It is known that a planar graph with bounded degree on n vertices has spectral gap λ = O(1/n)<cit.>.  The previous theorem tells us that among planar graphs with bounded degree, there is no infinite family that makes the bound κ = O(1/n) tight, indeed, κ≤ 0 for all but finitely many bounded degree graphs.

In the case of graphs without bounded degree, it is true that κ = 1/n for the star graph with n leaves, which is planar.



§ ACKNOWLEDGEMENTS
 The author thanks Max Fathi and Prasad Tetali for valuable discussions and examples of graphs relevant to this topic.

plainnat



