Quartic graphs which are Bakry-Émery curvature sharp
David Cushing Supanat Kamtue Norbert Peyerimhoff Leyna Watson May







Cushing]David Cushing
D. Cushing, Department of Mathematical Sciences, Durham University, Durham DH1 3LE, United Kingdom
davidcushing1024@gmail.com

Kamtue]Supanat Kamtue
S. Kamtue, Department of Mathematical Sciences, Durham University, Durham DH1 3LE, United Kingdom
supanat.kamtue@durham.ac.uk

Peyerimhoff]Norbert Peyerimhoff
N. Peyerimhoff, Department of Mathematical Sciences, Durham University, Durham DH1 3LE, United Kingdom
norbert.peyerimhoff@durham.ac.uk

Watson May]Leyna Watson May
L. Watson May, Department of Mathematical Sciences, Durham University, Durham DH1 3LE, United Kingdom
leyna.may@durham.ac.uk



Quartic graphs which are Bakry-Émery curvature sharp
    [
    
====================================================




  We give a classification of all connected quartic graphs which are
  (infinity) curvature sharp in all vertices with respect to
  Bakry-Émery curvature. The result is based on a computer
  classification by F. Gurr and L. Watson May and a combinatorial case
  by case investigation.




§ INTRODUCTION

Curvature is a fundamental notion in geometry which goes back to Gauss
and Riemann and was originally defined in the smooth setting of
Riemannian manifolds. A challenging problem is to find meaningful
curvature notions in discrete settings like graphs and networks.

In this paper we focus on a specific curvature notion on a graph
G=(V,E) with a vertex set V and an edge set E, called
Bakry-Émery curvature (at dimension n=∞). This curvature
notion is based on Bakry-Émery's Γ-calculus and a curvature
dimension inequality <cit.>, and it was first used by
Schmuckenschläger <cit.> in 1999. The crucial ingredient to
define this curvature is a natural notion of a Laplacian. In this
paper, we choose the non-normalized graph Laplacian Δ, defined
on functions f: V → by

    Δ f(x) = ∑_y: y ∼ x (f(y)-f(x)).

Bakry-Émery curvature is then a real valued function
𝒦_∞(x) of the vertices x∈ V, where the value
𝒦_∞(x) is fully determined by the combinatorial
structure of the (incomplete) 2-ball around x. The precise definition of
𝒦_∞(x) is given in Subsection
<ref>. For readers interested in more details about
this curvature notion, see, e.g. <cit.> and the references
therein. Corollary 3.3 of <cit.> gives the following upper bound
of 𝒦_∞(x) for a D-regular graph:


    𝒦_∞(x) ≤ 2 + #_Δ(x)/D,

where #_Δ(x) is the number of triangles containing x as a
vertex. We call a vertex x (infinity) curvature sharp if this
estimate holds with equality. The main result in the paper is a complete
classification of all 4-regular (quartic) curvature sharp graphs:

 
	Let G=(V,E) be a connected quartic graph which is Bakry-Émery
	curvature sharp in all vertices. Then G is one of the following:
	
		
  (i) The complete graph K_5 with |V|=5, =3.5,
		G = 1;
		
  (ii) The octahedral graph O with |V|=6, =3,
		G = 2;
		
  (iii) The Cartesian product K_3 × K_3 of two copies of
		the complete graph K_3 with |V|=9, =2.5, G =
		2;
		
  (iv) The complete bipartite graph K_4,4 with |V|=8,
		=2, G = 2;
		
  (v) The crown graph C(10) with |V|=10, =2,
		G = 3;
		
  (vi) The Cayley graph Cay(D_12,S) of the dihedral group
		D_12 of order 12 with generators S = { r^3,s,sr^2,sr^4 }
		with |V|=12, =2, G = 3;
		
  (vii) The Cayley graph Cay(D_14,S) of the dihedral group
		D_14 of order 14 with generators S = { s,sr,sr^4,sr^6 }
		with |V|=14, =2, G = 3;
		
  (viii) The 4-dimensional hypercube Q^4 with |V|=16,
		=2, G = 4.
	


The proof of this result is based on a computer classification of all
quartic incomplete 2-balls with non-negative curvature at their
centres. This local classification result was obtained in a 2018
LMS[London Mathematical Society] Undergraduate Research
Bursary by the last author. The revelant local results of this
research can be found in <cit.> and are summarized in Section
<ref> below. They are crucial for the
combinatorial arguments given in Section <ref> to
derive the global classification result. In fact, the proof of Theorem
<ref> is a combinatorial case by case investigation starting
with an incomplete 2-ball with a curvature sharp center and
extending it to derive a contradiction or to end up with one of the graphs in
the above classification.

It is conceivable that the results in <cit.> may
also have other applications, for example with regards to the following
conjecture about expander graph families (Conjecture 9.11 in <cit.>):

 Let D ∈ be fixed. Then there do not exist
  increasing D-regular expander graphs { G_k }_k ∈ which are
  non-negatively curved in all vertices.
  

In the case D=3 (cubic graphs), it was shown in
<cit.> that the only finite connected cubic
graphs of non-negative Bakry-Émery curvature are the prism graphs
and the Möbius ladders and, therefore, the conjecture is true for
D=3. It would be an interesting project to investigate whether the
results in <cit.> can be used to verify the conjecture in the case
D=4. A full classification of all finite connected non-negatively
curved quartic graphs is likely to be out of range due to the large
number of local combinatorial possibilities to construct such
graphs. However, <cit.> might be useful to derive specific
properties contradicting the existence of expander families like,
e.g., polynomial volume growth of metric balls.

Let us finish this introduction with an overview about the structure
of this paper. In Section <ref>, we introduce
Bakry-Émery curvature and all other relevant notions and present
some crucial results needed for the proof of Theorem
<ref>. The proof of Theorem <ref> is given in Section
<ref>.

































§ BAKRY-ÉMERY CURVATURE
 



 §.§ Motivation of Bakry-Émery curvature
 
Readers not familiar with Riemannian
manifolds can skip the following explanation and go directly to Definition
<ref> below.

Bakry-Émery
curvature is a general (Ricci) curvature notion which can be motivated
via the following curvature-dimension inequality on an
n-dimensional Riemannian manifold (M,⟨·,·⟩)
whose Ricci curvature at x satisfies _x(v) ≥ K_x |v|^2 for all
tangent vectors v ∈ T_xM:

    1/2Δ|  f|^2 (x) - ⟨ Δ
    f(x),   f(x) ⟩≥1/n(Δ f(x))^2 + K_x
    ‖  f(x) ‖^2.

This pointwise inequality holds for all smooth functions f and is a
straightforward consequence of Bochner's formula, a fundamental
fact in Riemannian Geometry (for Bochner's formula see, e.g.,
<cit.>). Using Bakry-Émery's Γ-calculus, this
inequality can be reformulated as

    Γ_2(f,f)(x) ≥1/n(Δ f(x))^2 + K_x
    Γ(f,f)(x)   ∀  f,

where the symmetric bilinear forms Γ and Γ_2 of two
smooth function f,g: M → are defined as

    2 Γ(f,g)    =   Δ(fg) - fΔ g - gΔ f = ⟨ 
      f,  g ⟩, 
    
      2 Γ_2(f,g)    =   ΔΓ(g,f) - Γ(f,Δ g) -
      Γ(g,Δ f).

Note that Γ and Γ_2 can be defined for any space
admitting a reasonable Laplace operator Δ. The idea is to use
inequality (<ref>) to define lower Ricci curvature bounds
at all points of general spaces admitting Laplace operators. In the
case of an arbitrary (not necessarily regular) graph G=(V,E) with
vertex set V and edge set E, there is a natural way to introduce a
Laplace operator via its adjacency matrix A_G, namely

    Δ = A_G - D·,

where D is a diagonal matrix containing the respective vertex
degrees. This operator Δ is called the non-normalized
  graph Laplacian and can also be viewed as a linear operator on the
space of functions on the vertices. It is straightforward to see that
the Laplacian of a function f: V → is then given by

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

where y ∼ x means that the vertices x and y are adjacent.

Note that inequality (<ref>) involves a dimension parameter
n, and it is not clear how to choose the dimension for a given graph
G. If we do not fix the dimension parameter n, (<ref>)
induces a lower Ricci curvature notion at a vertex x∈ V as a
  function of the dimension. This viewpoing was taken in <cit.>
and it easy to see that this pointwise curvature function is
monotone increasing in n and assumes a finite limit as n →∞. We refer to the limit as the Bakry-Émery curvature (at infinity)
𝒦_∞(x) at the vertex x. This limit value can also be
directly obtained by dropping the term involving the dimension
parameter in (<ref>).

 
Let G=(V,E) be a graph and Δ be the associated Laplacian defined in (<ref>). Let Γ and Γ_2 be the forms defined in (<ref>) and (<ref>). Then the Bakry-Émery curvature
𝒦_∞(x) at a vertex x is the supremum of all values K∈ satisfying

    Γ_2(f,f)(x) ≥ K Γ(f,f)(x)   ∀  f: V →.
 
Moreover, if we have 𝒦_∞(x) ≥ at all vertices x ∈ V for some value ∈, we say that G satisfies the (global) curvature-dimension inequality CD(,∞).


A natural class of connected regular graphs satisfying CD(0,∞)
are all abelian Cayley graphs (see <cit.> and references therein) and a
prominent example with vanishing Bakry-Émery curvature at all
vertices is the infinite grid ^n with generators ± e_j,
j=1,…,n.



 §.§ Fundamental properties of Bakry-Émery curvature


Before we present some fundamental properties of Bakry-Émery
curvature, we need to introduce some relevant notation. All graphs G =
(V,E) are assumed to be connected, i.e., there is a path between any pair of vertices in V. The degree of a vertex x is denoted by d_x∈ℕ, and a graph G is called D-regular if d_x=D for all x∈ V. The combinatorial distance d(x,y) between
two vertices x,y ∈ V is then the length of the shortest path from
x to y. The diameter of G is defined as 
    (G)=max_x,y∈ V d(x,y).

Spheres and balls around a vertex x ∈
V are defined via

    S_k(x)    =   { y ∈ V | d(x,y) = k }, 
    
      B_k(x)    =   { y ∈ V | d(x,y) ≤ k }.

The 2-ball B_2(x) has the following decomposition into spheres

    B_2(x) = {x}⊔ S_1(x) ⊔ S_2(x).

We call an edge {y,z}∈ E a spherical edge (w.r.t. x)
if d(x,y) = d(x,z), and a radial edge otherwise. Moreover,
the following values associated a reference vertex x ∈ V are
relevant:

    d_x^-(y)    = |{z∼ y : d(x,y) = d(x,z) + 1}|,
    
    d_x^0(y)    = |{z∼ y : d(x,y) = d(x,z) }|,
    
    d_x^+(y)    = |{z∼ y : d(x,y) = d(x,z) - 1}|,

which we call the in-degree, spherical degree, out-degree of
y, respectively. Note that d_y=d_x^-(y)+d_x^0(y)+d_x^+(y).


  We say that G is S_1-out regular at a vertex x, if all
  the vertices y in S_1(x) have the same out-degree
  d^+_x(y).
  

  





The complete 2-ball around x, denoted by B_2^(x), is the induced subgraph of B_2(x). Furthermore, the incomplete 2-ball around x, denoted by B_2^(x), is obtained from B_2^(x) with all spherical edges w.r.t. x within S_2(x) being removed. It is important to note that Bakry-Émery curvature 𝒦_∞(x) at a vertex x ∈ V is a local value, and it is already determined by the structure of incomplete 2-ball B_2^(x). As explained in <cit.>, the explicit calculation of Bakry-Émery curvature at a vertex is a semidefinite programming problem implemented in the interactive curvature calculator which can be found at <http://www.mas.ncl.ac.uk/graph-curvature>.

In <cit.>, the authors give an upper bound for Bakry-Émery curvature at a vertex in a D-regular graph, and then define the notion of a curvature sharp vertex as follows:


Let G=(V,E) be a D-regular graph. Then Bakry-Émery curvature (of dimension n=∞) at any vertex x ∈ V satisfies

    𝒦_∞(x) ≤ 2 + #_Δ(x)/D.


Moreover, a vertex x ∈ V is called
(infinity) curvature sharp if (<ref>) holds with
equality.



From Corollary 5.11 in <cit.>, curvature sharp at x implies S_1-out regularity at x. Moreover, the following proposition says that if S_1-out regularity is assumed everywhere, then the number of triangles involving a vertex (or an edge) is uniform.

 
Let G=(V,E) be a connected D-regular graph which is S_1-out regular in all vertices. Then there is c_1,c_2∈ such that #_Δ({x,y})=c_1 and #_Δ(x)=c_2, for all x∈ V and for all edges {x,y}∈ E.



Let x∼ y ∼ z be any two connected edges in G. Observe that

    d^+_y(x)   =D-1-#_Δ({x,y})
    
    d^+_y(z)   =D-1-#_Δ({y,z}).

Then S_1-out regularity at y means d^+_y(x)=d^+_y(z), which implies that  #_Δ({x,y})=#_Δ({y,z}).

Let x∼ y and x'∼ y' be two arbitrary edges in G. Consider a connected path from the edge x∼ y to the edge x'∼ y', namely 
    x∼ y ∼ v_0 ∼ ... ∼ v_n ∼ x' ∼ y'.
 
Then S_1-out regularity at y, at v_i's, and at x' altogether implies that 
    #_Δ({x,y})= #_Δ({y,v_0})=...=#_Δ({v_n,x'})=#_Δ({x',y'}),
 so #_Δ({x,y})≡ c_1, for some constant c_1. Moreover, counting triangles containing x gives 
    #_Δ(x)=1/2∑_y: y∼ x#_Δ({x,y})=1/2c_1 D,

which is also a constant i.e., c_2:=1/2c_1 D.



  Every connected D-regular graph G = (V,E) which is curvature
  sharp in all vertices x has constant curvature, that is, 𝒦_∞(x) = 𝒦 for all x ∈ V.


	#_Δ(x) is constant for all vertices x∈ V by Proposition <ref>, and the result follows from (<ref>).


Finally, we need the following combinatorial analogue of the classical
Bonnet-Myers Theorem from Riemannian Geometry (see, e.g.,
<cit.>) and its associated rigidity result by Cheng <cit.>.

 Let G=(V,E) be a connected D-regular graph with K:=inf_x∈ V𝒦_∞(x)>0. Then G satisfies Bonnet-Myers' diameter bound

    (G)≤2D/K,
 which holds with equality if and only if G is a D-dimensional hypercube. 





 §.§ Incomplete 2-balls with non-negative curvature at centers



In this subsection, we survey the relevant computational results about
Bakry-Émery curvature from <cit.>. They are based on a computer
program in Python written by the last author during a 2018 LMS
Undergraduate Research Bursary.

Firstly, we explain the representations of 2-balls in quartic graphs that were used for these calculations. We fix a vertex v_0 and S_1(v_0)={v_1,v_2,v_3,v_4} (since in a quartic graph, v_0 has four neighbors). The vertices of the 2-sphere are labeled as follows: S_2(v_0)={v_5,v_6,...,v_m}. Then a 2-ball B_2(v_0) centered at v_0 is represented by a list of 3 lists: B_2(v_0)=[list_1,list_2, list_3]. The first list determines the S_1 structure (i.e., how the vertices in S_1 are connected to each other) by list_1=[a_12,a_13,a_14,a_23,a_24,a_34] where each a_ij∈{0,1} is a Boolean indicator whether vertices v_i and v_j are adjacent or not. The second list list_2=[a_5,a_6,...,a_m] describes the S_1S_2 structure (i.e., which vertices in S_2 are adjacent to vertices in S_1). For instance, a_5=[123] means that the vertex v_5 is adjacent to v_1,v_2,v_3 but not to v_4. Lastly, the list list_3 describes the S_2 structure (i.e., how the vertices in S_2 are connected to each other). For example, list_3=[[57], [58], [68]] means that v_5∼ v_7, v_5∼ v_8, and v_6∼ v_8. However, the computation of Bakry-Émery curvature only requires the information of incomplete 2-balls where no spherical edge of S_2(v_0) is present, in which case list_3=[ ].
We refer to quartic incomplete 2-balls as those which are incomplete 2-balls of some quartic graph, i.e., every quartic B_2^(v_0) has d_v_0=d_v_1=...=d_v_4=4 and d_v_5,...,d_v_m≤ 4.

For example, the incomplete 2-ball B_2^(v_0) in Figure <ref> has the following representation:

    B_2^(v_0)=[[0,1,0,0,1,0]_S_1 structure , [[13],[13],[24],[2],[4]]_S_1-S_2 structure , [ ]]




Concerning the S_1 structures, we will only consider the 11 standard
representations (given in the second column of Table
<ref>) since all other S_1 structures can be
obtained from them via permutations of the vertices v_1,v_2,v_3,v_4.

The computational results are presented in the following two propositions below. The first proposition gives the number of all non-isomorphic quartic incomplete 2-balls as well as the ones with non-negative curvature at their center. The second proposition gives a list of all 22 quartic incomplete 2-balls that are curvature sharp at their center.


There are 365 non-isomorphic quartic incomplete 2-balls B_2^(v_0). Among them, there are 204 quartic incomplete 2-balls that have non-negative curvature 𝒦_∞(v_0). For more details, see Table <ref>.




In fact the above result is not used in our proof in Section <ref>. The following result, however, is crucial for the proof:


  There are 22 non-isomorphic quartic incomplete 2-balls B_2^(v_0) which are curvature sharp in v_0. They are listed in Table <ref>.



















































§ PROOF OF THE CLASSIFICATION THEOREM
 




  Let us start with a reference vertex v_0 and
  S_1(v_0) = {v_1,v_2,v_3,v_4}. We will perform a case-by-case
  analysis of all 22 possible (non-isomorphic)
  B_2^ inc(v_0)-structures which are curvature sharp at v_0,
  provided in Table <ref>.

  Since we assume all vertices v to be curvature sharp, any
  incomplete 2-ball B_2^ inc(v) must be one of the 22
  possible types, but their types can differ from vertex to
  vertex. However, we will see a posteriori that each globally
  curvature sharp graph generated by these cases is vertex transitive
  and, therefore, the incomplete 2-ball types of all its vertices
  coincide.

Moreover, Proposition <ref> asserts that for every edge e∈ E the number of triangles containing e, #_Δ(e), is uniform. We will therefore use the number #_Δ(e)∈{0,1,2,3} for our case separation.
Table <ref> provides an overview about all incomplete 2-ball structures that lead to globally curvature sharp graphs.






 §.§ Case #_Δ(e)=3 or #_Δ(e)=2


In the case #_Δ(e)=3, the S_1-structure immediately implies that G is the complete graph K_5.

Next we deal with the case #_Δ(e)=2. If B_2^ inc(v_0) is of type 2.1, then G is immediately the Octahedral graph O. Otherwise, if B_2^ inc(v_0) is of type 2.2, 2.3, 2.4, 2.5, 2.6 or 2.7, the S_1-S_2 structure infers that v_2 and v_4 have no common neighbor in S_2(v_0). Thus we have #_Δ({v_2,v_4})=1, namely the triangle {v_0v_2v_4}; contradiction to #_Δ(e)=2.




 §.§ Case #_Δ(e)=1


In the case #_Δ(e)=1, we will show that the incomplete 2-ball B_2^ inc(v_0) has only one possible structure, which is of type 3.3. Moreover, it leads to a unique graph G, namely the Cartesian product K_3× K_3.



  §.§.§ Case B_2^ inc(v_0) is of type 3.1
 Denote v_5,v_6,v_7∈ S_2(v_0) with the patterns 
    v_5≡ [1234]      v_6≡ [13]      v_7≡ [24].
 Then {v_0v_1v_2} and {v_1v_2v_5} are triangles, so #_Δ({v_1,v_2})≥ 2; contradiction.

We purposedly use “≡” to describe the pattern of a vertex in a 2-sphere to allow the possibility that two vertices may have the same pattern e.g., v_5≡ v_6≡ [13] even though v_5≠v_6.



  §.§.§ Case B_2^ inc(v_0) is of type 3.2
 Denote v_5,v_6,v_7,v_8∈ S_2(v_0) with the patterns 
    v_5≡ v_6≡ [13]      v_7≡ v_8≡ [24].
 Note that v_1 has four neighbors v_0, v_2, v_5, v_6. Since v_5 is not a neighbor of v_0 and v_2, the fact that #_Δ({v_1,v_5})=1 implies that v_5 is a neighbor of v_6. Now {v_1v_5v_6} and {v_3v_5v_6} are triangles, so #_Δ({v_5,v_6})≥ 2; contradiction.



  §.§.§ Case B_2^ inc(v_0) is of type 3.4
 Denote v_5,v_6∈ S_2(v_0) with the patterns v_5≡ v_6≡ [1234]. Then {v_0v_1v_2}, {v_1v_2v_5}, and {v_1v_2v_6} are triangles, so #_Δ({v_1,v_2})=3; contradiction.



  §.§.§ Case B_2^ inc(v_0) is of type 3.3 
 Denote v_5,v_6,v_7,v_8∈ S_2(v_0) with the patterns 
    v_5≡ [13]    v_6≡ [14]    v_7≡ [23]    v_8≡ [24].
 Consider v_1 as a center with four neighbors v_0, v_2, v_5, v_6. Since v_5≁v_0 and v_5≁v_2, the fact that #_Δ({v_1,v_5})=1 implies v_5∼ v_6. Similarly,

by centering at v_2, #_Δ({v_2,v_7})=1 implies v_7∼ v_8.
 By centering at v_3, #_Δ({v_3,v_5})=1 implies v_5∼ v_7.
 By centering at v_4, #_Δ({v_4,v_6})=1 implies v_6∼ v_8.

Now B_2^ inc(v_0) with additional edges v_5∼ v_6 ∼ v_8 ∼ v_7 ∼ v_5 results in a quartic graph, which is in fact the Cartesian product K_3× K_3 (see Figure <ref>).





 §.§ Case #_Δ(e)=0

Lastly, we deal with the most difficult case where #_Δ(e)=0 (i.e. G is triangle-free) and we expect to derive 5 possibilities of G, depending on its incomplete 2-ball structure. Henceforth, we restrict ourselves to the “bottom half" of Table <ref>, that is the ones indexed by 4.1-4.10.

From now on, we introduce a new notation for S_1-S_2 structure of the 2-ball B_2^ inc(v_i), which is centered around the vertex v_i (for i∈{1,2,3,4}). To do so, we add a subscript i to the pattern of each vertex on the two-sphere S_2(v_i).

For example, assuming v_1 has the neighbors v_0,v_5,v_6,v_7, the subscripts 1 in the following patterns

    v_2≡ [0567]_1      v_3≡ [0567]_1      v_4≡ [056]_1

signifies that they describe vertices in the S_1-S_2 structure of B_2^ inc(v_1).

Moreover, as in previous arguments, patterns are written without subscripts when we describe the S_1-S_2 structure of B_2^ inc(v_0).




  §.§.§ Case B_2^ inc(v_0) is of type 4.10

It is straightforward to deduce that G is the complete bipartite graph K_4,4.



  §.§.§ Case B_2^ inc(v_0) is of type 4.1, 4.2, 4.3, or 4.7


Note that all these cases have precisely two vertices in S_2(v_0) with the patterns [1234]. Let us denote them by v_5 and v_6.

Consider v_1 as a center with three known neighbors v_0,v_5,v_6, and the other unknown neighbor, which we denote by v_7. Now v_2,v_3,v_4 are in S_2(v_1) and all of them are neighbors of v_0,v_5,v_6, so they will have the following patterns:

    v_2≡ [056*_2]_1      v_3≡ [056*_3]_1      v_4≡ [056*_4]_1

where (for i∈{2,3,4}) each *_i takes value 7 or “empty", depending on whether v_i is a neighbor of v_7 or not.

When comparing the patterns in (<ref>) to the S_1-S_2 structures in Table <ref>, we can see that the possible structures of B_2^ inc(v_1) are of type either 4.3 or 4.10. However, an incomplete 2-ball of type 4.10 previously led to the resulting graph G=K_4,4. In case B_2^ inc(v_1) is of type 4.3, two vertices have their patterns [0567]_1 and one vertex has its pattern [056]_1. Without loss of generality, let the patterns in (<ref>) take values 

    v_2≡ [0567]_1      v_3≡ [0567]_1      v_4≡ [056]_1

which means v_4≁v_7. Now consider v_4 as a center, with neighbors v_0,v_5,v_6, and another neighbor denoted by v_8 (≠v_7). Note that due to the S_1 structure of v_0 being [0,0,0,0,0,0], it means that v_4 is not a neighbor of v_1,v_2,v_3. Thus v_1,v_2,v_3 are in S_2(v_4), and all of them are neighbors of v_0,v_5,v_6,v_7 (but not of v_8). Hence, v_1,v_2,v_3 have all the same pattern [056]_4, which does not belong to any S_1-S_2 structure in Table <ref>.



  §.§.§ Case B_2^ inc(v_0) is of type 4.4

Denote the vertices on S_2(v_0) by patterns

    v_5≡ [1234]      v_6≡ [12]      v_7≡ [13]      v_8≡ [24]      v_9≡ [34].

Consider v_1 as a center with four neighbors v_0,v_5,v_6,v_7. Now v_2,v_3,v_4 are in S_2(v_1) with the patterns

    v_2≡ [056]_1      v_3≡ [057]_1      v_4≡ [05]_1,

which does not belong to any S_1-S_2 structure in Table <ref>.



  §.§.§ Case B_2^ inc(v_0) is of type 4.8

Denote the vertices on S_2(v_0) by patterns

    v_5≡ [1234]      v_6≡ [123]      v_7≡ [124]      v_8≡ [34].

Consider v_3 as a center with four neighbors v_0,v_5,v_6,v_8. Now v_1,v_2,v_4 are in S_2(v_3) with the structure

    v_1≡ [056]_3      v_2≡ [056]_3      v_4≡ [058]_3,

which does not belong to any S_1-S_2 structure in Table <ref>.



  §.§.§ Case B_2^ inc(v_0) is of type 4.6
 
From now on, instead of calling the vertices on S_2(v_0) as v_5,v_6 and so on, we call them differently by names reflecting their patterns.  

In this particular case, we will denote the vertices on S_2(v_0) by patterns

    v_123≡ v'_123≡ [123]      v_14≡ [14]      v_24≡ [24]      v_34≡ [34].


Consider v_1 as a center with four neighbors v_0,v_14,v_123,v'_123. Henceforth, we also describe patterns no longer just by the indices of the involved vertices but by the vertices themselves. In this case, the vertices v_2,v_3,v_4 are in S_2(v_1) with patterns

    v_2≡ v_3≡ [v_0v_123v'_123]_1      v_4≡ [v_0v_14]_1,

and according to Table <ref>, the B_2^ inc(v_1) must be of type 4.6. That is, the other two vertices in S_2(v_1), namely A and B, will have patterns

    A≡ [v_123v_14]_1      B≡ [v'_123v_14]_1

In principle, it is possible that A or B could coincide with v_24 or v_34. However, this can be excluded by the following arguments. If A=v_24, we would have a triangle {v_4v_14v_24}, and if A=v_34, we would have a triangle {v_4v_14v_34}. The same reasoning applies to B=v_24 or B=v_34.

Next, consider v_4 as a center with four neighbors v_0,v_14,v_24,v_34. Now v_1,v_2,v_3,A,B are in S_2(v_4) with the patterns

    v_1≡ [v_0v_14]_4      v_2≡ [v_0v_24]_4      v_3≡ [v_0v_34]_4      A≡ [v_14*]_4      B≡ [v_14*]_4,

where each * represents some unknown vertex/vertices. According to Table <ref>, the only possible type of B_2^ inc(v_4) is 4.6. That is, A and B are in S_2(v_4) with patterns

    A≡ B≡ [v_14v_24v_34]_4.


The information (<ref>) and (<ref>)
tells us that we have a quartic graph as in Figure
<ref>, which is indeed a Cayley graph of D_12 (see
Figure <ref> in Remark <ref>
below).






  §.§.§ Case B_2^ inc(v_0) is of type 4.5
 
Denote the vertices on S_2(v_0) by patterns

    v_12≡ [12]    v_13≡ [13]    v_14≡ [14]    v_23≡ [23]    v_24≡ [24]    v_34≡ [34].


For each i∈{1,2,3,4}, consider v_i as a center with four neighbors v_0,v_ij,v_ik,v_il where {i,j,k,l}={1,2,3,4} (and from now on, v_ij=v_ji by convention). The vertices v_j,v_k,v_l are then in S_2(v_i) with patterns


    v_j≡ [v_0v_ij]_i      v_k≡ [v_0v_ik]_i       v_l≡ [v_0v_il]_i.


According to Table <ref>, the type of B_2^ inc(v_i) must be either 4.5 or 4.6 (and we can safely assume the type 4.5, since we previously dealt with the case where an incomplete 2-ball is of type 4.6). 

Since B_2^ inc(v_i) is of type 4.5, we suppose S_2(v_i)={v_j,v_k,v_l,A_jk^i,A_jl^i,A_kl^i} with patterns

    v_j≡[v_0v_ij]_i      v_k   ≡[v_0v_ik]_i      v_l≡[v_0v_il]_i 
    
    A_jk^i≡ [v_ijv_ik]_i      A_jl^i   ≡ [v_ijv_il]_i      A_kl^i≡ [v_ikv_il]_i.

Here, A_jk^i and A_kj^i represent the same vertex. 

Note that none of the vertices A_jk^i,A_jl^i,A_kl^i can coincide with the vertices v_jk,v_jl,v_kl, since this would always lead to the existence of some triangle, namely, v_sv_isv_st for some distinct s,t∈{j,k,l}. In conclusion, 
    A_jk^i,A_jl^i,A_kl^i ∈ S_3(v_0).


For every vertex w∈ S_3(v_0), we know that

    w ∼ v_ij  for some distinct i,j∈{1,2,3,4},

and therefore w∈ S_2(v_i)∩ S_2(v_j). Since w∈ S_2(v_i), (<ref>) implies that w coincides with one of
A_jk^i,A_jl^i,A_kl^i, so it is adjacent to v_ij by (<ref>) and
v_is for some s≠j.

Similarly, since w∈ S_2(v_j), w is
also adjacent to v_ij and v_jt for some t≠i. Therefore,
w has at least 3 different neighbors in S_2(v_0), namely
v_ij, v_is, v_jt, so its in-degree (w.r.t. v_0)
is 
    d^-_v_0(w)≥ 3      w∈ S_3(v_0).
 On
the other hand, for every vertex z∈ S_2(v_0), its in-degree is
d^-_v_0(z)= 2, so its out-degree is d^+_v_0(z)≤
2. Counting edges between S_2(v_0) and S_3(v_0) then gives

    12 ≥∑_z∈ S_2(v_0) d^+_v_0(z) = ∑_w∈ S_3(v_0) d^-_v_0(w) ≥ 3|S_3(v_0)|,

so we have |S_3(v_0)|≤ 4. Moreover, since A_jk^i,A_jl^i,A_kl^i ∈ S_3(v_0), we must have 3≤ |S_3(v_0)|≤ 4.























  * Case |S_3(v_0)|=3: then we know that
S_3(v_0)={A_jk^i,A_jl^i,A_kl^i}. Observe also that v_ij has four neighbors, namely S_1(v_ij)={v_i,v_j, A_jk^i,A_jl^i}.

Since these arguments hold for all indices i,j, we are allowed to interchange them, that is 

    S_3(v_0)   ={A_jk^i,A_jl^i,A_kl^i}={A_ik^j,A_il^j,A_kl^j}
    
    S_1(v_ij)   ={v_i,v_j, A_jk^i,A_jl^i}={v_i,v_j, A_ik^j,A_il^j}.

which implies that A_kl^i and A_kl^j coincide. By definition, it means that this vertex A_kl^i∈ S_3(v_0) is connected to v_ik,v_il,v_jk,v_jl,  that is 
    S_1(A_kl^i)={v_ik,v_il,v_jk,v_jl}.
 Since this argument holds for all combinations of i,j,k,l, we derive the information about all three vertices A_23^1,A_24^1,A_34^1∈ S_3(v_0): 

    S_1(A_23^1)   ={v_12,v_13,v_24,v_34},
    
    S_1(A_24^1)   ={v_12,v_14,v_23,v_34},
    
    S_1(A_34^1)   ={v_13,v_14,v_23,v_24},

which results in a quartic graph as in Figure <ref>,
which is indeed a Cayley graph of D_14 (see Figure
<ref> in Remark <ref>).




  * Case |S_3(v_0)|=4: We claim that in this case our graph G has diameter (G)≥ 4. Assume for the sake of contradiction that (G)=3 and the 4-sphere S_4(v_0) is empty.

Since |S_3(v_0)|=4, the inequality (<ref>) holds with equality, which implies that for all w∈ S_3(v_0), the in-degree d^-_v_0(w)=3. Thus the spherical degree d^0_v_0(w)=1. In particular, each of the vertices A_23^1,A_24^1,A_34^1 must be adjacent to another vertex in S_3(v_0). However, note that no pair of vertices A_23^1,A_24^1,A_34^1 are adjacent (otherwise, if A_jk^1 and A_jl^1 were connected, then they would form a triangle Δ v_1jA_jk^1A_jl^1). Thus A_23^1,A_24^1,A_34^1 must be adjacent to the the fourth vertex in S_3(v_0), which we may denote by P. Then the spherical degree d^0_v_0(P)=3, contradiction.



Therefore we have shown that (G) ≥ 4. On the other hand, Theorem <ref> gives the following diameter bound for Bakry-Émery curvature: 
    (G)≤2D/K=2·4/2=4,
 as we are working with quartic graphs (D=4) and K=inf_x(K)_∞(x)=2 (see Table <ref>). Since the graph G has diameter (G)=4, it must be the 4-dimensional hypercube Q^4 (as illustrated in Figure <ref>) by the rigidity statement in Theorem <ref>.





  §.§.§ Case B_2^ inc(v_0) is of type 4.9
 
Denote the vertices on S_2(v_0) by patterns

    v_123≡[123]      v_124≡[124]      v_134≡[134]      v_234≡[234].


For any {i,j,k,l}={1,2,3,4}, each vertex v_ijk∈ S_2(v_0)
has in-degree d^-_v_0(v_ijk)=3 and spherical-degree
d^0_v_0(v_ijk)=0 (as G is triangle-free), so v_ijk must
be connected to exactly one vertex on S_3(v_0) (depending on the choice of i,j,k) which we denote by
A_ijk∈ S_3(v_0). Note that these vertices
A_ijk might coincide (in fact, we will see that they are all the
same vertex).

Consider v_i as a center with four neighbors v_0,v_ijk,v_ijl,v_ikl. The vertices v_j,v_k,v_l∈ S_2(v_i) will have patterns

    v_j≡[v_0v_ijkv_ijl]_i      v_k≡[v_0v_ijkv_ikl]_i      v_l≡[v_0v_ijlv_ikl]_i.




According to Table <ref>, B_2^ inc(v_i) must be of
type 4.9 and, therefore, |S_2(v_i)|=4. We denote the so far
unlabeled vertex of S_2(v_i) by A_i and we have S_2(v_i) = {v_j,v_k,v_l,A_i} and A_i will have a pattern

    A_i≡[v_ijkv_ijlv_ikl]_i.

Since d(A_i,v_i)=2 and A_j ≠ v_j,v_k,v_l, we have

    A_i ∉{ v_0,v_i,v_j,v_k,v_ijk,v_ijl,v_ikl}.

We can also rule out A_i = v_jkl (for, otherwise,
2=d(A_i,v_i)=d(v_jkl,v_i) would imply that A_i=v_jkl is
adjacent to one of the neighbors v_ijk,v_ijl,v_ikl of v_i;
but any edge between two vertices of v_ijk,v_ijl,v_ikl,v_jkl
would create a triangle and, therefore, a contradiction). These considerations
show that A_i ∈ S_3(v_0) and A_i ∼ v_ijk by (<ref>). By definition of the vertices A_ijk, we conclude that

    A_i=A_ijk    {i,j,k,l}={1,2,3,4}.

In particular,

    A_1   =A_123=A_124=A_134
    
    A_2   =A_123=A_124         = A_234,

which means A_123,...,A_234 all coincide, and S_3(v_0) has only one vertex. As a result, G is the crown graph C(10), as shown in Figure <ref>.



After consideration of all possible cases we have now completed our classification result of quartic curvature sharp graphs (8 of them in total).


 
Figures <ref> and <ref> illustrate that the graphs in (vi) and (vii) of Theorem <ref> have indeed the stated Cayley graph structure.







Acknowledgement: Leyna Watson May's research was funded by the
London Mathematical Society (LMS) in a 2018 Undergraduate
Research Bursary. We thank Francis Gurr (Watson May's co-author
in <cit.>) for his support in creating the relevant Python code
and
 Riikka Kangaslampi for helpful mathematical discussions.




9

[BE85]BE85 D. Bakry and M. Émery, Diffusions hypercontractives (French), in Séminaire de probabilités, XIX, 1983/84, 
  Lecture Notes in Math. 1123, Springer, Berlin, 1985, pp. 177–206.

[Ch75]Ch75 S. Y. Cheng, Eigenvalue comparison theorems and its geometric applications, Math. Z. 143(3) (1975), pp. 289–297.
  

  
[CKLLS17]CKLLS17 D. Cushing, R. Kangaslampi, V. Lipiäinen, Sh. Liu,
  G. W. Stagg, The Graph Curvature Calculator and the curvatures
    of cubic graphs, arXiv:1712.03033.

[CLP17]CLP17 D. Cushing, Sh. Liu, N. Peyerimhoff, Bakry-Émery curvature functions of graphs, 
Canad. J. Math., pp. 1–55. doi:10.4153/CJM-2018-015-4. 

[GHL04]GHL04 S. Gallot, D. Hulin, J. Lafontaine, Riemannian geometry, Universitext, Third Edition, Springer-Verlag, Berlin, 2004.

[GW18]GW18 F. Gurr, L. Watson May, Bakry-Émery curvature
  calculations of quartic 2-balls and graphs of diameter 2, Python code
  results used for our article are filed as ancillary file.

[KKRT16]KKRT16 B. Klartag, G. Kozma, P. Ralli, and P. Tetali, Discrete curvature and abelian groups, Canad. J. Math. 68 (2016), pp. 655–674.




  
[LMP16]LMP16 Sh. Liu, F. Münch, N. Peyerimhoff, Bakry-Emery curvature and diameter bounds on graphs,  Calc. Var. Partial Differential Equations 57 (2018), no. 2, Art. 67, 9 pp.

[LMP17]rigidity Sh. Liu, F. Münch, N. Peyerimhoff, Rigidity properties of the hypercube via Bakry-Emery curvature, arXiv:1705.06789.

[Schm99]Schm99 M. Schmuckenschläger, Curvature of
    nonlocal Markov generators, in Convex geometric analysis
  (Berkeley, CA, 1996), Math. Sci. Res. Inst. Publ. 34, Cambridge
  Univ. Press, Cambridge, 1999, pp. 189–197.
  
  

