Lin-Lu-Yau curvature and diameter of amply regular graphs

LI Xintian, LIU Shiping

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

Abstract: By Hall’s marriage theorem, we study lower bounds of the Lin-Lu-Yau curvature of amply regular graphs with girth 3 or 4 under different parameter restrictions. As a consequence,we show that each conference graph has positive Lin-Lu-Yau curvature.Our approach also provides a geometric proof of a known diameter estimates of amply regular graphs in the case of girth 4 and some special cases of girth 3.

Keywords: amply regular graph; perfect matching; Wasserstein distance; Lin-Lu-Yau curvature

1 Introduction and statements of result

Ricci curvature is a fundamental concept in Riemannian geometry. Its extension to general metric measure spaces, particularly, to locally finite graphs, has attracted lots of attention[1-8]. In 2009, Ollivier[2,3]introduced the notion of coarse Ricci curvature of Markov chains on metric spaces including graphs. On graphs, Ollivier’s Ricci curvatureκpof an edge is defined via the Wasserstein distance between two probability measure around the two vertices of the edge, depending on an idleness parameterp∈[0,1]. In 2011, Lin et al.[7]modified Ollivier’s notion by taking the minus of the derivative ofκpatp=1. We will study this modified Ricci curvature, which will be referred to as the Lin-Lu-Yau curvature, on amply regular graphs in this paper.

Definition 1.1LetG=(V,E) be a locally finite graph,μ1andμ2be two probability measures onG. The Wasserstein distanceW1(μ1,μ2) betweenμ1andμ2is defined as

where the infimum is taken over all mapsπ:V×V→[0,1] satisfying

Such a map is called a transport plan.

We consider the following particular measure around a vertexx∈V:

Definition 1.2[2,7]LetG=(V,E) be a locally finite graph. For any verticex,y∈V, thep-Ollivier-Ricci curvatureκp(x,y),p∈[0,1], is defined as

The Lin-Lu-Yau curvatureκ(x,y) is defined as

Notice thatκ1(x,y) is always 0. Hence, the Lin-Lu-Yau curvatureκ(x,y) is minus the derivative ofκp(x,y) atp=1.

Bourne et al.[9]studied the relation betweenp-Ollivier-Ricci curvature and Lin-Lu-Yau curvature. In particular, they proved that for an edgexy∈Ewith deg(x)=deg(y)=d

(1)

The Lin-Lu-Yau curvature has been computed or estimated on graphs with further regularity assumptions. For regular graphs (i.e., every vertex has the same degree), the following upper bound estimate is known.

Theorem 1.1[10]LetG=(V,E) be ad-regular graph. For any edgexy∈E, we have

whereΔxy:=Γ(x)∩Γ(y),Γ(x):={z∈V|xz∈E}, andΓ(y):={z∈V|yz∈E}.

We study the Lin-Lu-Yau curvature of amply regular graphs with girth 3 or 4 in this paper.

Definition 1.3(Amply regular graph[15]) We call ad-regular graph withnvertices an amply regular graph with parameter (n,d,α,β) if the following holds true:

(i) Any two adjacent vertices haveαcommon neighbors.

(ii) Any two vertices with distance 2 haveβcommon neighbors.

We remark that if the above property (ii) holds for any two non-adjacent vertices, the amply regular graph is strongly regular. Therefore, amply regularity is a relaxation of the strongly regularity.

For amply regular graphs with girth 4 we have the following Lin-Lu-Yau curvature formula.

Theorem 1.2LetG=(V,E) be an amply regular graph with parameter (n,d,α,β) with girth 4. For anyxy∈E, we have

This formula has been established for the particular cases of strongly regular graphs with girth 4 and distance regular graphs with girth 4 in Refs.[11] and [13], respectively. Observe that the Lin-Lu-Yau curvature of a given edge only involves number of common neighbors of vertices with distance at most 2. Therefore, the proofs of [11] and [13] can be adopted directly to amply regular graphs with girth 4.

Our main result is the following Lin-Lu-Yau curvature formula or estimates for amply regular graphs with girth 3 (i.e.,α≥1).

Theorem 1.3LetG=(V,E) be an amply regular graph with parameter (n,d,α,β).

(i) Ifα=1 andα<β, then we have for anyxy∈Ethat

(ii) Ifα≥1 andα=β-1, then we have for anyxy∈Ethat

(iii) Ifα=β>1, then we have for anyxy∈Ethat

③ Bonini et al.[11,Conjecture 1.7]conjectured that the Lin-Lu-Yau curvature of any strongly regular conference graphs with parameter (4γ+1,2γ,γ-1,γ) withγ≥2 satisfies

Theorem 1.3(ii) implies that for such conference graphs

④ In general, it is still open whether the Lin-Lu-Yau curvature of an amply regular graph of parameter (n,d,α,β) with girth 3 (i.e.,α≥1) andβ≥2 is always nonnegative or not.

For Ollivier’s Ricci curvature, a Bonnet-Myers type diameter estimate holds true[2]: Uniformly positive curvature lower bound implies the finiteness of the diameter. This has been extended to the Lin-Lu-Yau curvature.

Theorem 1.4(discrete Bonnet-Myers theorem[7]) LetG=(V,E) be a locally finite connected graph. Supposeκ(x,y)≥k>0 holds true for anyxy∈E. Then the diameter

Discrete Bonnet-Myers theorem has recently found important applications in coding theory: It provides a completely elementary way to derive bounds on locally correctable and some locally testable binary linear codes[14].

Applying Theorem 1.4, we have the following consequences.

Corollary 1.1LetG=(V,E) be an amply regular graph with parameter (n,d,α,β).

(i) IfGhas girth 4, then

diam(G)≤d.

(ii) Ifα=1 andα<β, then

(iii) Ifα≥1 andα=β-1, then

diam(G)≤d.

(iv) Ifα=β>1, then

diam(G)≤d.

The following diameter estimate for amply regular graphs is known via classical combinatorial methods, see, e.g., Ref.[15, Theorem 1.13.2].

Theorem 1.5[15]LetG=(V,E) be an amply regular graph with parameter (n,d,α,β). Ifα≤β≠1, then

diam(G)≤d,

where the equality holds if and only ifGis ad-hypercube graph.

Remark 1.2Corollary 1.1 provides a geometric proof via Lin-Lu-Yau curvature for Theorem 1.5 in the case of girth 4 and some special cases of girth 3. Moreover, we improve the estimate in Theorem 1.5 under the condition of Corollary 1.1(ii).

2 Preliminaries

We first recall the important concept of matching from graph theory.

Definition 2.1[16, Section 16.1]LetG=(V,E) be a locally finite simple connected graph. A setMof pairwise nonadjacent edges is called a matching. The two vertices of each edge ofMare said to be matched underM, and each vertex adjacent to an edge ofMis said to be covered byM. A matchingMis called a perfect matching if it covers every vertex of the graph.

The following Hall’s marriage theorem will be an important tool for our purpose.

|ΓT(W)|≥|W| for allW?S

holds, whereΓT(W):={v∈T| there existsw∈Wsuch thatvw∈E}.

For anyxy∈E, the Lin-Lu-Yau curvatureκ(x,y) only depends on the subgraph induced by vertices with the distance less than or equal to 2 toxandy[6, Lemma 2.3]. For convenience, we introduce the following notation of the core neighborhood ofxy∈E:

Cxy={x}∪{y}∪Δxy∪Nx∪Ny∪Pxy,

where

Nx=Γ(x)({y}∪Γ(y)),

Ny=Γ(y)({x}∪Γ(x)),

Pxy={z∈V|d(x,z)=2,d(y,z)=2}.

3 Proof of Theorem 1.3

In this section, we prove Theorem 1.3.

Proof of Theorem 1.3(i)We consider the core neighborhood decomposition of an edgexy∈E, that is,

Γ(x)={y}∪Δxy∪Nx,Γ(y)={x}∪Δxy∪Ny.

Sinceα=1, we can denoteΔxy={x0}, and there are no edges connectingx0and any vertex inNxorNy. We are going to show the existence of a perfect matching betweenNxandNyvia applying Lemma 2.1.

E(A,B):={xy∈E|x∈A,y∈B}.

We then have

Sinceβ>1, we derive from above that

|A|≤|B|=|ΓNy(A)|.

Applying Lemma 2.1, there is a perfect matchingMbetweenNxandNy. We construct the following transport plan building upon such a perfect matching:

Noticing that |Nx|=|Ny|=d-α-1, we calculate the Wasserstein distance

Applying Eq.(1), we have the Lin-Lu-Yau curvature

Combining with Theorem 1.1, we obtain

Proof of Theorem 1.3(ii)We construct a bipartite graphHfrom the core neighborhood ofxy∈Eas follows. Denote

Δxy={z1,…,zα}.

We add a new set of verticesΔ′xy:={z′1,…,z′α} which is considered as a copy ofΔxy. LetHbe the bipartite graph with vertex set

VH=Nx∪Δxy∪Δ′xy∪Ny

and edge set

EH=E1∪E2∪E3∪E4∪E5,

where

E1={vw|v∈Nx,w∈Ny,vw∈E},

E2={vz′i|v∈Nx,z′i∈Δ′xy,vzi∈E},

E3={ziw|zi∈Δxy,w∈Ny,ziw∈E},

E4={ziz′i|i=1,…,α},

E5={ziz′j|zizj∈E,i≠j, 1≤i,j≤α}.

Notice that in the above construction, edges only exist betweenNx∪ΔxyandNy∪Δ′xy. We will show thatHhas a perfect matching by Lemma 2.1.

Take a subsetA?Nx∪Δxy. LetB=ΓNy∪ Δ′xy(A) be the neighbors ofAinNy∪Δ′xy.

① The caseA?Nx. Similarly as in the proof of Theorem 1.3 (i), there areβ-1≥1 neighbors of anyv∈AinNy∪Δ′xy, andβ-1≥1 neighbors of anyw∈B∩NyinNx∪Δxy. Consider any vertexz′i∈B∩Δ′xy. The corresponding vertexzi∈Δxyandxhaveαcommon neighbors inGincluding the vertexy. Since there is a new additional edge betweenziandz′iinH, the vertexz′ihas exactlyαneighbors inNx∪ΔxyinH. Therefore, we derive

By assumption, we haveα=β-1. Hence the above estimate yields

|A|≤|B|=|ΓNy∪Δ′xy(A)|.

② The caseA?Δxy. Consider any vertexzi∈A. The verticesziandyhasαcommon neighbors inGincluding the vertexx. Since there is a new additional edge betweenziandz′i∈Δ′xyinH, the vertexzihas exactlyαneighbors inNy∪Δ′xyinH. Therefore, we derive

Usingα=β-1, we obtain

|A|≤|B|=|ΓNy∪Δ′xy(A)|.

③ The caseA?Nx∪Δxy. We have

Byα=β-1, we obtain

|A|≤|B|=|ΓNy∪Δ′xy(A)|.

Applying Eq.(1), we have the Lin-Lu-Yau curvature

Proof of Theorem 1.3 (iii)We modify the construction of the bipartite graphHin the proof of Theorem 1.3 (ii) by dropping the edge setE4. That is,His the graph with vertex setVH=Nx∪Δxy∪Δ′xy∪Nyand edge setEH=E1∪E2∪E3∪E5.

Take a subsetA?Nx∪Δxy. LetB=ΓNy∪ Δ′xy(A) be the neighbors ofAinNy∪Δ′xy. Similarly as the analysis in the proof of Theorem 1.3 (ii), we have

By assumption, we haveα=β>1. Then we derive from above that

|A|≤|B|=|ΓNy∪Δ′xy(A)|.

Therefore, there is a perfect matching ofHby Lemma 2.1. Similarly as in the proof of Theorem 1.3 (ii), we derive

Acknowledgments

We are very grateful to BAI Shuliang for pointing out that amply regular graphs of parameter (n,d,α,β) withβ=1 can have girth 3 and negative Lin-Lu-Yau curvature. We would like to thank the anonymous referees for suggestions that helped to greatly improved the quality of this paper. This work is supported by the National Natural Science Foundation of China (No. 12031017).

Conflictofinterest

The authors declare no conflict of interest.

Authorinformation

LIXitianis a master student under the supervision of Professor Liu Shiping at University of Science and Technology of China. She received her BS degree from Nanjing University of Science and Technology in 2018. Her research mainly focuses on the discrete Ricci curvature theory.

LIUShiping(corresponding author) is a Professor at School of Mathematical Sciences, University of Science and Technology of China. He received his BS degree from Shandong University in 2006, and PhD (Dr. rer. nat.) degree from Max Planck Institute for Mathematics in the Sciences, Leipzig and University of Leipzig, Germany, in 2012. From 2013 to 2016, he worked as a Research Associate in the Department of Mathematical Sciences, Durham University, UK. His research interests include spectral graph theory, discrete Ricci curvature theory, spectral geometry and other related topics in discrete and continuous geometric analysis.