Curvatures, graph products and Ricci flatness

(1)

J Graph Theory. 2020;1–32. wileyonlinelibrary.com/journal/jgt

|

¹

A R T I C L E

Curvatures, graph products and Ricci flatness

David Cushing

¹

| Supanat Kamtue

¹

| Riikka Kangaslampi

²

| Shiping Liu

³

| Norbert Peyerimhoff

¹

1Department of Mathematical Sciences, Durham University, Durham, United Kingdom

2Unit of Computing Sciences, Tampere University, Tempere, Finland

3School of Mathematical Sciences, University of Science and Technology of China, Hefei, China

Correspondence

Supanat Kamtue, Department of Mathematical Sciences, Durham University, Durham DH1 3LE, United Kingdom.

Email:supanat.kamtue@durham.ac.ukand skamtue@gmail.com

Funding information

National Natural Science Foundation of China, Grant/Award Number: 11721101

Abstract

In this paper, we compare Ollivier–Ricci curvature and Bakry–Émery curvature notions on combinatorial graphs and discuss connections to various types of Ricci flatness.

We show that nonnegativity of Ollivier–Ricci curvature implies the nonnegativity of Bakry–Émery curvature under triangle‐freeness and an additional in‐degree condition. We also provide examples that both conditions of this result are necessary. We investigate relations to graph products and show that Ricci flatness is preserved under all natural products. While nonnegativity of both curvatures is preserved under Cartesian products, we show that in the case of strong products, nonnegativity of Ollivier–Ricci curvature is only preserved for horizontal and vertical edges. We also prove that all distance‐regular graphs of girth 4 attain their maximal possible curvature values.

K E Y W O R D S

curvature comparison, graph curvature, Ricci flat

1 | I N T R O D U C T I O N 1.1 | Motivation of the paper

Curvature is a fundamental notion in the setting of smooth Riemannian manifolds. There is no unique choice of an analogue of curvature in the setting of combinatorial graphs.

- - - -- This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

(2)

Two possibilities areOllivier–Ricci curvatureandBakry–Émery curvaturewhich are both motivated by specific curvature properties of Riemannian manifolds. Ollivier–Ricci curvature, introduced in [16], is based on the observation that, in the case of positive/negative Ricci curvature, average distances between corresponding points in two nearby small balls in Riemannian manifolds are smaller/larger than the distance between their centres. This fact is reinterpreted using the theory of Optimal Transportation of probability measures representing these balls. Bakry–Émery curvature, introduced in [1], is based on the so‐called curvature–dimension inequality which reads for n‐dimensional Riemannian manifolds( , )M g as follows:

∥ f∥ x ≥ 〈∇f x ∇ f x 〉 ∇ ∇

n f x f f x

1

2Δ grad ( ) ( ), Δ ( ) + 1

(Δ ( )) + Ric( , )( )

2 2 (1)

for all f∈ C^∞( )M andx∈ M. Here,Ric( , )v w for tangent vectorsv w, atxstands for the Ricci curvature of the manifold. This formula is a straightforward implication of Bochner's identity, a fundamental fact in Riemannian Geometry with many important consequences. Both curvature notions have been further discussed in the setting of graphs in several literatures (see, e.g., [14]

for Ollivier–Ricci curvature and [12,15,18] for Bakry–Émery curvature). For the precise defi- nitions of both notions in this paper, we refer to Section2.

While there are many special cases in which these two discrete curvature notions are related, it is a challenging problem to develop a satisfactory general understanding of the agreements and differences of these two curvature notions.

One special family of graphs which have both nonnegative Ollivier–Ricci curvature and nonnegative Bakry–Émery curvature was introduced by Chung and Yau [6], namely,Ricci flat graphs. The notion of Ricci flatness was motivated by the structure of thed_‐dimensional grid^d (with vanishing Ollivier–Ricci and Bakry–Émery curvature) and the class of Ricci flat graphs contains all abelian Cayley graphs as a subset.

The motivation of this paper is to investigate various relations between these two curvature notions and the property of Ricci flatness with special focus on triangle‐free graphs. We also present explicit examples of graphs related to our results. The curvatures of these examples were calculated numerically via the interactive web‐application athttps://www.mas.ncl.ac.uk/

graph-curvature/. For more details about this very useful tool we refer the readers to [9].

1.2 | Statement of results

Let G= ( , )V E be a regular graph. Ollivier–Ricci curvature κp( , )x y is defined on edges

∈ x y E

{ , } and there is an idleness parameterp∈[0, 1]involved. Lin, Lu and Yau introduced in [14] a modified notion of Ollivier–Ricci curvature, denoted by κLLY( , )x y. Both notions are introduced in Definition 2.3. While it is known that κ0≤κLLY, our first result shows in Section2.1 that positiveκLLY‐curvature implies the nonnegativity ofκ0‐curvature:

Theorem 1.1. LetG= ( , )V E be a regular graph.Then we have the following implication for all edges{ , }x y ∈ E:

⇒ ≥

κLLY( , ) > 0x y κ0( , )x y 0.

The Bakry–Émery curvature is defined on vertices and the inequality (1) involves a dimension parametern. Since graphs do not have a well‐defined dimension, a natural choice

(3)

simplifying this inequality isn=∞. The induced Bakry–Émery curvature value at a vertexxis then denoted by∞( )x (see Definition2.8).

Let us now turn to the above‐mentioned notion of Ricci flatness. Ricci flatness is defined locally for individual vertices. In this paper we also introduce stronger types of Ricci flatness, namely, (R)‐, (S)‐and (RS)‐Ricci flatness (see Definition3.1). A fundamental consequence of Ricci flatness is that it implies both nonnegativity of Ollivier–Ricci and Bakry–Émery curvatures; the stronger property of (R)‐Ricci flatness implies even strict positivity of these two curvatures (see Theorems3.4and3.5).

Another basic property of Ricci flatness is that it is preserved under natural graph products (see Theorem 5.2). The graph products under consideration, namely, Cartesian product (involving horizontal and vertical edges), tensorial product (involving only diagonal edges), and the strong product (involving all three types of edges), are introduced in Definition5.1. While Cartesian products preserve the nonnegativity of both Ollivier–Ricci curvature and Bakry–Émery curvature, in the case of strong products, nonnegative Ollivier–Ricci curvature is only preserved for horizontal and vertical edges (see Corollary5.4).

We also consider the case of graphs which contain no triangles. In Section4, we present our main result of this paper relating the two curvature notions. Ralli [17] gave an interesting criterion for curvature sign agreement of both curvature notions for triangle‐free graphs which do not contain the complete bipartite graphK2,3as a subgraph. He mentions that the situation is much more unclear if one restricts to general triangle‐free graphs. Our result requires triangle‐freeness at a vertex x and the additional assumption that the in‐degrees of vertices in the 2‐sphereS x2( ) are smaller or equal to 2. Forz ∈S x2( ), the in‐degree, denoted byd z_x⁻( ), is the number of common neighbours ofx andz. This assumption is weaker than nonexistence ofK2,3as a subgraph.

Theorem 1.2. Given a regular graphG= ( , ),V E letx∈V be a vertex not contained in a triangle and satisfyingd z_x⁻( )≤ 2for all z∈ S x2( ).Then we have the following:

(a) κ0( , ) = 0x y for all y∈ S x1( ) implies∞( )x ≥0. (b) κLLY( , ) =x y _d2

for all y∈S x1( )implies∞( ) = 2x .

It is an important remark here that κ0( , ) = 0,x y κLLY( , ) =x y _d

2 and ∞( ) = 2x are the maximum possible values of curvature for a vertexxnot contained in a triangle. This curvature comparison result is proved by employing Ricci flatness, see Section4. At the end of the section, we also provide examples to show that all conditions of the theorem are necessary.

In Section6, we show that the curvatures of alldistance‐regular graphs of girth4 and vertex degreedsatisfyκ0= 0,κLLY= _d2

and∞= 2(see Theorem6.2). In other words, all curvatures attain their maximal possible values for this interesting family of triangle‐free graphs.

2 | C U R V A T U R E N O T I O N S

All graphsG= ( , )V E with vertex setV and edge setE in this paper are simple (i.e., without loops and multiple edges), undirected and connected, and we assume that the vertex degreesdx

of all verticesx∈ V are finite. Moreover, all our graphs are regular (i.e.,dx=d for allx∈V) unless stated otherwise. Balls and spheres are denoted by

≔ ∈ ≤

≔ ∈

B x z V d x z k S x z V d x z k

( ) { : ( , ) },

( ) { : ( , ) = },

k k

(4)

whered V: ×V→∪{0}is the combinatorial distance function.

2.1 | Ollivier–Ricci curvature

We define the following probability distributions μ_x^p for anyx∈V p, ∈ [0, 1]:

μ z

p z x

p

d z x

( ) =

if = , 1−

if ~ , 0 otherwise.

x p

x

⎧

⎨⎪⎪

⎩⎪⎪

Definition 2.1 (Transport plan and Wasserstein distance). GivenG= ( , ), letV E μ μ₁, ₂ be two probability measures onV. Atransport planπ transportingμ₁toμ₂is a function

→ ∞

π: V×V [0, ) satisfying the following marginal constraints:

∑ ∑

∈ ∈

μ ( ) =x π( , ),x y μ ( ) =y π( , ).x y

y V x V

1 2 (2)

Thecostof a transport planπ is given by

∑ ∑

∈ ∈

π d x y π x y cost( ) = ( , ) ( , ).

y V x V

The set of all transport plans satisfying (2) is denoted byΠ( ,μ μ₁ ₂).

TheWasserstein distanceW1( ,μ μ1 2)between μ₁andμ₂ is then defined as

∑ ∑

≔

∈ ∈

W( ,μ μ ) infcost( ) = infπ d x y( , ) ( , ),π x y

π π

y V x V

1 1 2 (3)

where the infimum runs over all transport plansπ∈Π( ,μ μ₁ ₂).

Remark2.2. Note that every π∈Π( ,μ μ₁ ₂) satisfies π( , ) = 0x y if x∉ supp(μ₁) or

∉

y supp(μ₂). Therefore (3) can be rewritten as

∑ ∑

∈ ∈

W( ,μ μ ) = inf d x y( , ) ( , ).π x y

π y μ x μ

1 1 2

supp( ₂) supp( ₁)

In other words, a transport plan π moves a mass distribution given by μ₁ into a mass distribution given byμ₂, andW1( ,μ μ1 2)is a measure for the minimal effort which is required for such a transition.

Ifμ₁andμ₂have finite supports, then there existsπ which attains the infimum in (3). We call suchπ anoptimal transport plantransporting μ₁to μ₂.

Definition 2.3 (Ollivier–Ricci curvature). The p_‐Ollivier–Ricci curvature[16] on an edge

∈ x y E { , } is

(5)

( )

κp( , ) = 1x y −W μx,μ ,

p y 1 p

where p∈ [0, 1]is called theidlenessparameter.

The Ollivier–Ricci curvature introduced by Lin, Lu and Yau [14] is defined as

→

κ x y κ x y

( , ) = lim ( , )p 1− .

p p

LLY 1

It was shown in [14, Lemma 2.1] that the function p↦κp( , )x y is concave, which implies

≤ ∈

κp( , )x y κLLY( , )x y for all p [0, 1]. (4) Moreover, we have the following relation for edges{ , }x y withdx=dy=d (see [3]):

κ x y d

d κ x y ( , ) = + 1

( , ).

LLY d1

+1

(5)

From the definition of the Wasserstein metric we can get an upper bound forW1by choosing a suitable transport plan. Using Kantorovich duality (see, e.g., [20, Ch. 5]), a fundamental concept in the optimal transport theory, we can approximate the opposite direction:

Theorem 2.4(Kantorovich duality). Given G= ( , ),V E let μ μ₁, ₂ be two probability measures onV.Then

→

∑

∈ ∈

W( ,μ μ ) = sup ϕ( )(x μ ( )x −μ ( )),x

ϕV

ϕ x V

1 1 2

: 1‐Lip

1 2



where 1‐Lip denotes the set of all 1‐Lipschitz functions. Ifϕ∈ 1‐Lipattains the supremum we call it anoptimal Kantorovich potentialtransportingμ₁ toμ₂.

Note that both curvaturesκ0( , )x y andκLLY( , )x y of an edge{ , }x y are already determined by the combinatorial structure of the induced subgraphB x2( ). (In fact, by symmetry reasons, the combinatorial structure of the induced subgraphB x2( )∩B y2( )is sufficient.)

As the relationκ0≤ κLLYis known from (4), now we will prove the surprising fact that strict positivity ofκLLY implies the nonnegativity ofκ0(as stated in Theorem1.1 from Section 1).

Proof of Theorem1.1. LetG= ( , )V E bed‐regular. Using the relation (5), it suffices to prove

⇒ ≥

κ ( , ) > 0x y κ0( , )x y 0.

d1 +1

Let{ , }x y ∈E be an edge withκ ( , ) > 0x y

d1

+1 . We define the following sets:

≔ ∩

≔

T S x S y

V S x B y V S y B x

( ) ( ), ( ) \ ( ), ( ) \ ( ).

xy x y

1 1

(6)

In other words,Txyis the set of common neighbours ofxandy V, xis the set of neighbours ofxwhich have distance 2 toyand, similarly,Vyis the set of neighbours ofywhich have distance 2 to x.

We can choose an optimal transport plan^π^opt∈^Π

(

^μ^x^d⁺¹¹ ^,^μ^y^d¹⁺¹

)

^with

(i) ifu∈ Txy ∪{ }x ∪{ }y, thenπopt( , ) =u u _d1 + 1, (ii) ifu∈Vx, thenπopt( , ) =u v _d1

+ 1 for exactly onev ∈Vy and 0 for others, (iii) ifu∉ B x1( ), thenπopt( , ) = 0u v forv ∈V.

The existence of an optimal transport plan satisfying (ii) (i.e., without splitting mass) follows from [4, Theorem 1.1] (see also [19, p. 5]). Moreover, this transport plan can be chosen to satisfy (i) by [3, Lemma 4.1]. Note that (iii) holds for any transport plan in^Π

(

^μ^x^d¹⁺¹^,^μ^y^d⁺¹¹

)

^.

In other words, the optimal transport plan does not move the mass distributions atx y, orTxy, and for the vertices inVxit moves the mass distribution from one vertex completely to one vertex in Vy. Thus the optimal transport plan pairs the vertices at Vx and Vy. Letu∈Vx and denote byu˜ the unique vertex inVyfor whichπopt( , ˜) =u u _d

1 + 1.

Let us then consider the Wasserstein distance. Using the optimal transport plan we can write

∑

∈

( )

κ x y W μ μ

d d u u

1 > 1− ( , ) = , = 1

+ 1 ( , ˜).

x y

u V

d 1

d d

x 1

+1

1

+1 1

+1 (6)

Note that1≤d u u( , ˜ )j j ≤ 3for alluj∈Vx. Let

≔ ∣ ∈ ∣ ∈

Ni {u Vx:d u u( , ˜) = }i for i {1, 2, 3}.

It follows from (6) thatd+ 1 >∑_{u V}_∈ d u u( , ˜) =N1+ 2N2+ 3N3

x , which implies

≥

d N1+ 2N2+ 3N3. (7)

Now we distinguish three cases.

Assume that N3> 0. Then there exists at least one vertex w ∈Vx satisfying d w w( , ˜ ) = 3. Let π be a transport plan from μ_x⁰ to μ_y⁰ such that π( , ) =w x _d¹, π( , ˜ ) =y w _d¹ and π( , ˜) =u u _d¹ for all other pairs ( , ˜)u u on the support of πopt except

w w

( , ˜ ). Using this transport plan and (7), we have

≤

( )

W μ μ

d N N N

d d

, 1

(2 + + 2 + 3( −1))

−1

< 1.

x y

1 0 0

1 2 3

Thusκ0( , ) > 0x y .

Next, we assume N3= 0 and N2> 0. Then there exists at least one vertex w∈Vx

satisfyingd w w( , ˜ ) = 2, and we obtain, similarly as above,

(7)

≤

≤ ≤

( )

W μ μ

d N N

d N N N

, 1

(2 + + 2( −1)) 1( + 2 + 3 ) 1,

x y

1 0 0

1 2

1 2 3

and thereforeκ0( , )x y ≥ 0.

Finally, if N2=N3= 0, the optimal transport plan πopt defines a perfect matching between the setsVxandVy, and therefore

≤ ≤

( )

W μ μ N

d

N , 2 + ( −1) d

= + 1

x y 1,

1 0 0 1 1

sinceN1=∣Vx∣ ≤d−1, and again,κ0( , )x y ≥0, with equality if and only ifN1=d−1,

which meansTxy=∅. □

Remark2.5.

(a) The proof shows thatκLLY( , ) > 0x y impliesκ0( , ) > 0x y in the following cases:

(i) N3> 0 or

(ii) N3=N2= 0 and{ , }x y is contained in a triangle.

(b) The hypercubesQ^dsatisfyκLLY( , ) =x y _d2 > 0

andκ0( , ) = 0x y for all edges{ , }x y ∈ E. (c) The triplex (see Figure 1a) satisfies κLLY( , ) = 0x y and κ0( , ) =x y −1 < 0

3 for all edges{ , }x y ∈ E.

(d) The icosidodecahedral graph (see Figure1b) satisfiesκLLY( , ) = 0x y andκ0( , ) = 0x y for all edges{ , }x y ∈E. This implies thatκp( , ) = 0x y for all p∈[0, 1]. Graphs with this property in all edges are calledbone‐idle (this notion was introduced in [3]).

(e) It was shown in [3] that κ ≤κ +

LLY 0 d2

and that κLLY,κ0∈ ∕ d. The result in the theorem further rules out the possibility that κLLY= _d1

and κ0=−_d1

occur simultaneously.

The examples (b) and (c) show that the result in the theorem is sharp.

We finish this subsection with the following upper curvature bounds forκ0 andκLLY: Theorem 2.6(see [13, Theorem 4] and [8, Proposition 2.7]).LetG= ( , )V E bed‐regular and{ , }x y ∈E.Then

≤ κ x y x y

( , ) # ( , )d

0 Δ

and

≤

κ x y x y

( , ) 2 + # ( , )d ,

LLY Δ

where# ( , )Δ x y is the number of triangles containing{ , }x y.

(8)

2.2 | Bakry – Émery curvature

This curvature notion was first introduced by Bakry and Émery in [1] and was applied on graphs in [12,15,18]. The definition of this curvature is based on the curvature–dimension inequality (1), which is equivalently rewritten as (8) with the help of the followingΓ‐calculus.

For any function f V: → and any vertex x∈V, the (nonnormalized) Laplacian Δ is defined via

∑

≔

f x f y f x

Δ ( ) ( ( )− ( )).

y y x: ~

Definition 2.7 (Γ and Γ2 operators). Given G= ( , ),V E we define for two functions f g, : V→

≔

f g fg f g g f

f g f g f g f g

2Γ( , ) Δ( )− Δ − Δ ;

2Γ2( , ) ΔΓ( , )− Γ( ,Δ )− Γ(Δ , ).

We writeΓ( )f ≔Γ( , )f f andΓ2( , )f f ≔Γ2( )f , for short.

Definition 2.8 (Bakry–Émery curvature). GivenG = ( , ),V E ∈ and∈ (0,∞]. We say that a vertex x∈ V satisfies thecurvature–dimension inequalityCD( , ), if for any

→

f : V , we have

≥ ∈

f x f x f x x V

Γ( )( ) 1

(Δ ( )) + Γ( )( ) for all .

2 2

  (8)

We calla lower Ricci curvature bound ofx, and a dimension parameter. The graph G = ( , )V E satisfiesCD( , )(globally), if all its vertices satisfyCD( , ). At a vertex

∈

x V, let( ,x )be the largestsuch that (8) holds for all functionsf atxfor a given

. We call( , )x ⋅ the Bakry–Émery curvature functionof x and we define

∞ ≔

x →∞ x

( ) lim ( , ).

  



In this paper, we will restrict our considerations to the curvature at ∞‐dimension

∞:V→

 . Note that for the definition of∞( )x , the formula (8) simplifies to

≥ ∈

f x f x x V

Γ2( )( ) Γ( )( ) for all .

The quadratic formsΓ( , )( )⋅ ⋅ x andΓ2( , )( )⋅ ⋅ x can be represented by matricesΓ( )x andΓ2( )x as follows:

⊤

f g x f x g f g x f x g Γ( , )( ) = Γ( ) , Γ2( , )( ) = Γ2( ) ,

where f g, are the vector representations of f and g. The matricesΓ( ),x Γ2( )x are symmetric with nonzero entries only in B x1( ) and B x2( ), respectively. So we can view them as local matrices by disregarding the vertices outsideB x2( ). For the explicit matrix entries ofΓ( )x and

(9)

x

Γ2( )see [10, Subsections 2.2 and 2.3]. Note that these entries are already fully determined by the combinatorial structure of theincomplete2‐ball aroundx, denoted byB₂^inc( )x , which is the induced subgraph ofB x2( )with all edges withinS x2( ) removed.

We have the following general upper curvature bound similar to Theorem2.6:

Theorem 2.9(see [10, Corollary 3.3]).LetG= ( , )V E bed‐regular and x∈ V.Then

∞ x ≤ x

( ) 2 + # ( )d

Δ ,



where# ( )Δ x is the number of triangles containingx.

Let us finally return to the examples from Section 2.1.

Remark2.10. The examples in Remark 2.5 have the following Bakry–Émery and Ollivier–Ricci curvatures:

κ0( , )x y κLLY( , )x y ∞( )x

HypercubeQ^d 0

d

2 2

Triplex −¹₃ 0 −1

Icosidodecahedral graph 0 0 −³₂

None of the regular graphs in the above table has curvature with opposite signs. We are not aware of any such examples and it would be interesting to find such graphs.

3 | R I C C I F L A T G R A P H S

The notion of Ricci flat graphs was introduced in 1996 by Chung and Yau [6] in connection to a logarithmic Harnack inequality and is motivated by the structure of thed‐dimensional grid^d. Abelian Cayley graphs are prominent examples of Ricci flat graphs.

Definition 3.1. LetG= ( , )V E be ad_‐regular graph. We say that x∈V isRicci flatif there exist mapsη_i: B x1( )→V for1≤ ≤i d with the following properties:

(i) η_i( )~u u for allu∈B x1( ), (ii) η_i( )u ≠η_j( )u ifi≠j,

(iii) ⋃jη ηj( ix)) =⋃jη ηi( jx) for alli.

We also consider the following additional properties of the mapsη_i: (R) Reflexivity:η_i²( ) =x x for alli.

(S) Symmetry:η η_j( _ix) =η η_i( _jx)for alli j, .

(10)

If there exists a family of mapsη_ifor a given vertexx∈ Vsatisfying property (R) or property (S) in addition to (i)–(iii), we say thatxis (R)‐Ricci flat or (S)‐Ricci flat, respectively. If there exists a family of mapsη_isatisfying (i)–(iii) and (R) and (S) simultaneously, we say thatxis (RS)‐Ricci flat.

Thed‐dimensional grid^dis Ricci flat with the choicesη_i( ) =x x+ei. The following lemma is a useful observation for the study of Ricci flatness of concrete examples.

Lemma 3.2. Assume a family of maps η_i:B x1( )→V satisfies (i)–(iii) of the above definition.Then each of these mapsη_i is a bijective map betweenB x1( ) and B1(η_ix). Proof. Assume that the familyη_isatisfies (i)–(iii). It follows immediately from (i) and (ii) and regularity that

⋃_{j j}η( ) =u S u1( ) for all u∈ B x1( ).

This implies that (iii) is equivalent to

S1(η_ix) =η_i( ( ))S x1 for all ,i which, in turn, implies

∪ ∪

B1(η_ix) =S1(η_ix) {η_ix} = η_i( ( ))S x1 η_i({ }) =x η_i(B x1( )). (9) Therefore, each mapη_i must be injective, since

∣η_i(B x1( )) =∣ ∣B1(η_ix) =∣ ∣B x1( ) .∣

Bijectivity fromB x1( ) toB1(ηx) follows immediately from (9). □

(A) (B)

F I G U R E 1 Examples of graphs withκLLY= 0. (A) The triplex and (B) the icosidodecahedral graph

(11)

Note that all Ricci flatness properties at a vertexxcan be determined from the combinatorial structure of the incomplete 2‐ball B₂^inc( )x aroundx, which was introduced in Section2.2.

Example 3.3. To help readers familiarize with the notion of Ricci flatness, we provide three examples of graphs and check whether each of them is Ricci flat.

(a) The incomplete 2‐ball in Figure 2 with S x1( ) = { ,v v v1 2, 3},v v1~ 2 and S x2( ) = { , ,v v v4 5 6},v4~ ,v v1 5~v v2, 3 andv6~v3 is not Ricci flat:

We show this by contradiction. Assumeη_i: B x1( ) →V with properties (i)–(iii) exist.

Without loss of generality, we can assume η_i( ) =x vi. Note that we must have

∈ ∩

η_i( )vj S v1( )i S v1( )j for1≤ i j, ≤d. This implies that we have the following choices for our mapsη_j:

x v1 v2 v3

η₁ v1 x v v, 2, 4 x x η₂ v2 x x v v, 1, 5 x v, 5

η₃ v₃ x x v, 5 x v v, ,5 6

Such a table can be presented concisely with the help of a d×d matrix A, namely, A= (Aij) defined as follows: Let S x1( ) = { , …, }v1 vd where vj≔ηj( )x , and S x2( ) = : {vd+1, …, }vt and, furthermore,v0≔x. Then the entriesAij ∈{0, 1, …, }t of Aare given via the relation

vA_ij=ηi( ).vj

Then the table translates into the following possibilities for the entries of A:

0, 2, 4 0 0

0 0, 1, 5 0, 5 0 0, 5 0, 5, 6

.

⎛

⎝

⎜⎜

⎞

⎠

⎟⎟

The conditions (i)–(iii) require that all columns and rows ofAhave nonrepeating entries.

Obviously, this is not possible in this case. Henceforth, we will use this matrix notation to simplify matters.

F I G U R E 2 Graph that is not Ricci flat

(12)

(a) The graph K3,3: Let S x1( ) = { ,v v v1 2, 3} and S x2( ) = { , }v v4 5 with v v v v v4, 5~ ,1 2, 3. We have the following possibilities for the entries of the associated matrix A:

0, 4, 5 0, 4, 5 0, 4, 5 0, 4, 5 0, 4, 5 0, 4, 5 0, 4, 5 0, 4, 5 0, 4, 5 .

⎛

⎝

⎜⎜

⎞

⎠

⎟⎟

Note that (R)‐Ricci flatness requires the existence of an associated matrix A with vanishing diagonal and (S)‐Ricci flatness requires the existence of a symmetric matrix A. Therefore, x is (R)‐and (S)‐Ricci flat by the following matrix choices:

A = A

0 4 5 5 0 4 4 5 0

, =

0 4 5 4 5 0 5 0 4

R S .

⎛

⎝⎜⎜ ⎞

⎠⎟⎟ ⎛

⎝⎜⎜ ⎞

⎠⎟⎟

Note that x is not (RS)‐Ricci flat since both properties (vanishing diagonal and symmetry) cannot be satisfied at the same time. In fact, the complete bipartite graphs Kd d, are both (R)‐and (S)‐Ricci flats for alld, and (RS)‐Ricci flat if and only ifdis even (see details in the appendix of the arXiv version [7]).

(b) Shrikhande graph: Cayley graph 4×4 with the generator set {±(0, 1), ±(1, 0), ±(1, 1)}. It is a strongly regular graph (see [5, p. 125]). The structure of the incomplete 2‐ballB2inc( )x around any vertexxis given in Figure3. We have the following possibilities for the entries of the associated matrix A:

0, 2, 6, 7, 12, 15 0, 7 0, 2 0, 12 0, 6 0, 15

0, 7 0, 1, 3, 7, 8, 13 0, 8 0, 3 0, 13 0, 1

0, 2 0, 8 0, 2, 4, 8, 9, 14 0, 9 0, 4 0, 14

0, 12 0, 3 0, 9 0, 3, 5, 9, 10, 12 0, 10 0, 5

0, 6 0, 13 0, 4 0, 10 0, 4, 6, 10, 11, 13 0, 11

0, 15 0, 1 0, 14 0, 5 0, 11 0, 1, 5, 11, 14, 15

.

⎛

⎝

⎜⎜

⎞

⎠

⎟⎟

F I G U R E 3 The incomplete 2‐ballB₂^inc( )x of the Shrikhande graph

(13)

Choosing 0 for diagonal entries fixes all other entries of the matrix. Moreover, this choice leads to a symmetric matrix, which shows that x is (RS)‐Ricci flat.

3.1 | Ricci flatness and Ollivier – Ricci curvature

With regard to Ollivier–Ricci curvature we have the following general implications:

Theorem 3.4. LetG = ( , )V E bed‐regular.

(a) If x∈V is Ricci flat,thenκ0( , )x y ≥ 0for all edges{ , }x y ∈ E. (b) If x∈V is(R)‐Ricci flat,thenκLLY( , )x y ≥ _d2

for all edges{ , }x y ∈E.

Proof. For the proof of (a) we assume Ricci flatness at x with corresponding maps

→

η_i: B x1( ) V. Let y∈ S x1( ). Recall that

S x1( ) = { ( ), …,η1 x η_d( )}.x

Therefore, we have y=η_i( )x for some i∈{1, …, }. We choose the following trans-d port plan:

∈ π u η u

d u S x

( , ( )) = 1

for all ( ),

i 1

andπ( , ) = 0u v for all other combinations. This implies

∑

^∈

∈

π u v π u η u

d μ u u S x

( , ) = ( , ( )) = 1

= ( ) for all ( )

v V

i x

0 1

and (using Lemma3.2)

∑

^∈

∈ ^π^{( , ) =}^{u v} ^{π η}

(

^{( ),}^{v v}

)

⁼ _d¹ ⁼^μ ^{( )}^v ^{for all} ^v ^{S y}^{( ),}

u V

i y

−1 0

1

which shows that^π∈ ^Π

(

^μ^x⁰^,^μ^y⁰

)

. This leads to

∑

≤

∈

( )

W μ_x,μ_y cost( ) =π π( ,u η( )) = 1,u

u S x 1 0 0 i

1( )

which implies κ0( , )x y ≥0. We prove (b) similarly. Assume x is (R)‐Ricci flat with corresponding mapsη_iand y=η_i( )x . Note that we haveη_i( ) =y xfrom reflexivity. This time, we choose the following transport plan^π∈^Π

(

^μ^x^{1 ( +1)}^∕^d ^,^μ^y^{1 ( +1)}^∕^d

)

^:

∈ π u η u

d u S x y

( , ( )) = 1

+ 1 for all ( ) \ { },

i 1

π( , ) =x x π( , ) =y y _d_{+ 1}¹ , andπ( , ) = 0u v for all other combinations. This leads to

(14)

∑

∕ ∕ ≤

∈

( )

W μ μ π π u η u d

, cost( ) = ( , ( )) = d−1

+ 1,

x d

y d

u S x y 1 1 ( +1) 1 ( +1) i

( ) \ { }

1

which impliesκ1 ( +1)∕d ( , )x y ≥ d 2 + 1 and

∕ ≥

κ x y d

d κ x y

( , ) = + 1 d

( , ) 2

d .

LLY 1 ( +1)

□

3.2 | Ricci flatness and Bakry–Émery curvature

With regard to Bakry–Émery curvature we have the following general implications:

Theorem 3.5. LetG = ( , )V E bed_‐regular.

(a) If x∈V is Ricci flat,then∞( )x ≥ 0. (b) If x∈V is(R)‐Ricci flat,then∞( )x ≥2.

Proof. The proof of statement (a) was already explained in [6,15]. This proof strategy can also be applied to prove statement (b). We present these proofs for the reader's convenience.

Recall from the definition that

f f x f f x f f x

2Γ2( , )( ) =ΔΓ( , )( )−2Γ( ,Δ )( ) (10) and

f g x fg x f x g x g x f x 2Γ( , )( ) =Δ( )( )− ( )Δ ( )− ( )Δ ( ).

A useful identity to computeΓ( , )f g is

∑

f g x f y f x g y g x 2Γ( , )( ) = ( ( )− ( ))( ( )− ( )).

y y x: ~

Let us now consider the first term on the right‐hand side (RHS) of (10) and use the identity A² −B²= (A−B) + 2 (² B A−B):

∑

∑ ∑ ∑

∑∑

f f x f f ηx f f x

f η ηx f ηx f ηx f x

f ηx f x f η ηx f ηx f ηx f x ΔΓ( , )( ) = (Γ( , )( )− Γ( , )( ))

=1

2 ( ( )− ( )) − ( ( )− ( ))

=1

2 ( ( )− ( )− ( ) + ( ))

+ ( ( ) − ( ))( ( )− ( )− ( ) + ( )).

i d

i

i d

j d

j i i

j d

j

i d

j d

j i i j

i d

j d

j j i i j

=1

=1 =1

2

=1

2

=1 =1

2

=1 =1

⎡

⎣

⎢⎢

⎤

⎦

⎥⎥

(15)

On the other hand, we have for the second term on the RHS of (10), using Ricci flatness,

∑

∑∑

f f x f ηx f x f ηx f x

f ηx f x f η ηx f ηx f ηx f x

−2Γ( ,Δ )( ) =− ( ( )− ( ))(Δ ( )− Δ ( ))

=− ( ( ) − ( ))( ( )− ( )− ( ) + ( ))

=− ( ( ) − ( ))( ( )− ( )− ( ) + ( )).

j d

j j

j d

i d

j i j j i

j d

i d

j j i i j

=1

=1 =1

Adding both terms, we end up with

∑∑

^≥

f f x f η ηx f ηx f ηx f x 2Γ( , )( ) = 1

2 ( ( )− ( )− ( ) + ( )) 0,

i d

j d

j i i j

2

=1 =1

2

showing∞( )x ≥ 0. Under the stronger condition of (R)‐Ricci flatness, we can estimate f f x

2Γ2( , )( )from below as follows:

∑∑

∑

≥

f f x f η ηx f ηx f ηx f x

f η ηx f ηx f ηx f x

f x f ηx f f x 2Γ( , )( ) =1

2 ( ( )− ( )− ( ) + ( ))

1

2 ( ( )− ( )− ( ) + ( ))

=1

2 (2 ( )−2 ( )) = 4Γ( , )( ).

i d

j d

j i i j

i d

i i i i

i d

i 2

=1 =1

2

=1

2

=1

2

This shows thatΓ2( , )( )f f x ≥2Γ( , )( )f f x , which means that we have∞( )x ≥2. □

4 | T R I A N G L E ‐ F R E E G R A P H S

In this section we focus on curvature comparison results for graphs without triangles. Our main result states that the nonnegativity of Ollivier–Ricci curvature implies the nonnegativity of Bakry–Émery curvature under a certain in‐degree condition (see Corollary1.2). This result is derived via Ricci flatness properties.

We start with particular upper curvature bounds in case of triangle‐freeness:

Proposition 4.1. Let G= ( , )V E be d‐regular. Then we have the following upper curvature bounds:

(i) κ0( , )x y ≤ 0 for all edges{ , }x y ∈E not contained in a triangle, (ii) κLLY( , )x y ≤ _d

2 for all edges{ , }x y ∈E not contained in a triangle, (iii) ∞( )x ≤2 for all x∈ V not contained in a triangle.

(16)

Remark4.2. Combining the proposition with the lower curvature bounds for Ricci flatness (Theorems3.4and3.5), we obtain the following curvature equalities:

• If x is Ricci flat and the edge { , }x y ∈E is not contained in any triangle, thenκ0( , ) = 0x y .

• If x is (R)‐Ricci flat and the edge { , }x y ∈ E is not contained in any triangle, thenκLLY( , ) =x y _d2

.

• If x is (R)‐Ricci flat and not contained in any triangle, then∞( ) = 2x .

Proof of Proposition4.1. Although Statements (i) and (ii) are an implication from Theorem2.6, we provide their proof here which presents a useful idea for the following remark.

Statement (i) follows from

∑ ∑

≥

∈ ∈

( )

W μ μ d u v π u v

π u v

, = ( , ) ( , )

( , ) = 1,

x y

u S x v S y

1 0 0

( ) ( )

opt

( ) ( ) opt

1 1

(11)

sinceS x1( )∩S y1( ) =∅. Hereπopt is an optimal transport plan in^Π

(

^μ^x⁰^,^μ^y⁰

)

^.

For the proof of (ii), we only need to show

≤ κ x y

( , ) d 2 + 1

d1 +1

by (5). This follows from

∑ ∑

≥

∕ ∕

∈ ∈

( )

W μ μ d u v π u v

π u v π x x π y y

d

, = ( , ) ( , )

( , ) − ( , )− ( , ) 1− 2

+ 1,

x d

y d

u B x v B y

u B x v B y 1 1 ( +1) 1 ( +1)

( ) ( )

opt

( ) ( )

opt opt opt

1 1

⎛

⎝

⎜⎜

⎞

⎠

⎟⎟ (12)

since B x1( )∩B y1( ) = { , }x y andπ ( , )u u ≤μ_x^∕^d ( )u ≤

opt 1 ( +1) d1

+ 1. Hereπopt is an optimal transport plan in^Π

(

^μ^x^{1 ( +1)}^∕^d ^,^μ^y^{1 ( +1)}^∕^d

)

^.

Statement (iii) is an implication from Theorem2.9. □

Remark4.3. Note that in Proposition 4.1, (ii) implies (i) by Theorem1.1. Moreover, it follows from the above proof that sharpness of the bounds in (i) and (ii) has the following combinatorial interpretation in the triangle‐free case:

(a) κ0( , ) = 0x y is equivalent that there is a perfect matching betweenS x1( )andS y1( ). (b) κLLY( , ) =x y _d2

is equivalent that there is a perfect matching between S x1( ) \ { }y andS y1( ) \ { }x .

(17)

A natural class of examples where all three upper bounds of Proposition4.1are attained is distance‐regular graphs of girth 4 (see Section6). To motivate our next result, let us focus on one particular example:

Example 4.4. Let S x1( ) = { , …, }v1 vd and S x2( ) = {vij∣ ≤1 i< j≤d} with v v vi, ~j ij. In fact this is the 2‐ball of the d‐dimensional hypercube Q^d and we have the following curvatures (see Remark 2.10):

κ x v κ x v ∞

d x

( , ) = 0, ( , ) = 2

, ( ) = 2.

i i

0 LLY 

We also like to mention that the vertex x in this example is (RS)‐Ricci flat and that we haved zx−( ) = 2

for allz ∈S x2( ).

Theorem 4.5. Given a regular graphG= ( , ),V E letx∈V be a vertex not contained in a triangle and satisfyingd z_x⁻( )≤ 2for all z∈ S x2( ).Then we have the following:

(a) κ0( , ) = 0x y for all y∈ S x1( ) is equivalent to xbeing(S)‐Ricci flat.

(b) κLLY( , ) =x y _d2

for all y∈S x1( )is equivalent to x being(RS)‐Ricci flat.

This result, together with Theorem 3.5, implies our main curvature comparison result in Theorem1.2 from Section 1:

Proof of Theorem1.2. Under the assumptions of Theorem 4.5, we first assume that κ0( , ) = 0x y for all y∈ S x1( ). This implies that x is Ricci flat and, by Theorem 3.5(a), that∞( )x ≥ 0.

Similarly, assumingκ ( , ) =x y

LLY d2

for ally∈ S x1( ), we know that x is (R)‐Ricci flat, and Theorem3.5(b) implies that∞( )x ≥2. Sincex is not contained in a triangle, this

leads to∞( ) = 2x by Proposition4.1(iii). □

Before we start with the proof of Theorem 4.5, let us introduce the following notion and discuss relations to existing results.

Definition 4.6. LetG = ( , )V E be a regular triangle‐free graph andx∈V. We say that

∈

y y₁, ₂ S x1( ) are linked by z ∈S x2( ) if we have y₁~ ~z y₂. We refer to z as a link of y₁and y₂.

Ralli [17] investigated curvature implications for regular graphs withoutK3andK3,2as subgraphs.

It is easy to check that this condition is equivalent to the following properties at all verticesx:

(i) x is not contained in a triangle, (ii) d zx−( )≤2 for allz∈S x2( ),

(iii) Any pair y y₁, ₂ ∈S x1( ) has at most one link.

A consequence of his results is that conditions (i)–(iii) imply∞( )x ≤0 or∞( ) = 2x . Under these conditions, Ralli has the following equivalence:

∈ ⇔ ∞ ≥

κ0( , ) = 0x y for all y S x1( )  ( )x 0.

(18)

Our theorem implies that the implication“⇒”holds already under conditions (i) and (ii) and we have an example that the implication“⇐=”is no longer true if one drops condition (iii). Note also that our theorem is a local result, meaning that the assumption is made for an arbitrary vertexx(in contrast to Ralli's result where the assumption is made for the entire graph). However, if a graph satisfies the assumption of our theorem for all vertices x, then it is equivalent to the graph satisfying Ralli's assumption. In other words, there are no entire graphs where Theorem4.5holds and Ralli's does not.

Proof of Theorem4.5. The implications ⇐= in (a) and (b) follow immediately from Theorem3.4and Proposition4.1.

Let us now prove the forward implication in (a). Letx∈V be given withd=dxand S x1( ) = { , …, }y1 y_d . The propertyκ0( , ) = 0x y for ally∈ S x1( )implies that we have perfect matchingsσi: S x1( )→S y1( )i for all1≤ ≤i d. In particular, we can assume that these perfect matchingsσi satisfy the following property:

Property (P): If there exists a perfect matching between S x1( ) \ { }y_i and S y1( ) \ { }_i x , thenσi( ) =yi x.

Our goal is to show that we can modify these perfect matchings in such a way that σi( ) =yj σj( )yi for all i≠ j. Defining then η_i: B x1( )→B y1( )_i as η_i( ) =x y_i and η_i( ) =y σi( )y for y∈S x1( )provide (S)‐Ricci flatness.

We first prove the following crucial fact:

Fact: Leti≠ j. We haveσi( ) =yj x if and only if y_iand y_j are not linked.

This fact can be shown as follows: We first prove the easier“⇐=”implication. Assume y_iandy_jare not linked. Thenσi( ) ~ ,yj y yi jcannot be inS x2( )and we must have therefore σi( ) =yj x. For the“⇒”implication, we provide an indirect proof: Ify_iandy_jwere linked by z∈ S x2( ), then the σi‐preimage of z ∈S y1( )_i must be in { , }y y_i _j but we know that σi( ) =yj x. Thereforeσi( ) =yi yj. Defining then the mapσ˜ :i S x1( )→S y1( )i via

≠ σ y

σ y k i j

z k j

x k i

˜ ( ) =

( ) if , , if = , if = ,

i k

⎧

⎨⎪

⎩⎪

induces a perfect matching betweenS x1( ) \ { }y_i andS y1( ) \ { }_i x . This would implyσi( ) =yi x contradicting toσi( ) =yj x.

Now we prove our goal.

We first show that σi( ) =yj x implies σj( ) =yi x: Sinceσi( ) = ,yj x yi and y_j are not linked by our Fact which, in turn, impliesσj( ) =yi x by our Fact, again.

We deal with all other pairs( , ),i j i≠ jas follows: Ifσi( ) =yj σj( )yi , we do not change the assignmentsσi( ),yi σi( ),yj σj( ),yi σj( )yj . Now we assume thatσi( ) = :yj z≠ σj( )yi ≔z′. Note that z z, ′ ∈S x2( ) and they both are links of y_i and y_j. Since z∈ S y1( )_j and

≤

d z_x⁻( ) 2, we must have σ⁻¹_j ( )z ∈ { , }y y_i _j . Since σj is injective andσj( ) =yi z′, we must haveσ_j⁻¹( ) =z y_j. So we must have

σj( ) = .yj z (13)

Similarly, we conclude that σi( ) =yi z′. Now we modify σi as follows: σi( ) =yi z and σi( ) =yj z′. This preserves property (P) of the perfect matching σi and establishes