Ricci curvature, graphs and Coxeter groups

In the last decades there has been a research trend in combinatorics to translate notions of Riemannian geometry in graph theory (see for example [12], [7], [34],[23],[13],[5],[4],[3],[32],[11],[31],[29],[8],[9],[33],[19] ). In [41] a definition of Ricci curvature of graphs was formulated by Schmuckenschläger as an attempt to define a concept of curvature in the context of discrete Markov chains similar to the one that Bakry and Emery [2] defined for probability spaces. This notion of Ricci curvature at first was mainly used in applications related with finite Markov chains (see [20],[38]) or dealing with analytical aspects in the setting of graphs (e.g. [12],[8],[27], [39]) such as the study of heat kernels, isoperimetric inequalities and Harnack inequalities. The analysis of curvature of graphs associated to algebraic structures was only recently initiated by Klartag, Kozma, Ralli and Tetali in [30].The main result of their paper - as the authors themselves state - is to provide a variety of examples of graphs with non-negative curvature. Among these examples there is the computation of the Ricci curvature of the Cayley graph of Sn, the group of permutations, taking all transpositions as the set of generators. They obtain that the Ricci curvature of such a graph doesn’t depend on n and in particular is always 2. This Cayley graph has an important role in Coxeter Theory as it corresponds to the Bruhat graph of type An−1. The starting point of this thesis has been to study the Ricci curvature of Bruhat graphs associated to other Coxeter groups. The main motivation being to fill the lack of examples and to develop an intuition on how the Ricci curvature works for graphs. The (surprising) result is that the curvature is 2 for any Bruhat graph associated to any finite Coxeter group. From this study arose the interest for the Ricci curvature for other families of graphs having a relevant role in Coxeter theory. In particular it turns out that for a linear Coxeter system (so, also for the symmetric group, see Section 1.1 for the definition of linear Coxeter system) the Ricci curvature of the weak Bruhat order is −2 cos(π/n) where n is the rank. This leads also to some new results about the Ricci curvature of any graph, for example in Theorem 2.3 we show that the curvature of a graph at a given point can be computed as an eigenvalue of a symmetric matrix which depends on the combinatorics of the graph near that point. As corollaries of these results we obtain an isoperimetric inequality for Bruhat graphs and weak order graphs of finite Coxeter groups. We then turn our attention to the (Hasse diagram of the) Bruhat order. This is a more subtle case since this graph is not a Cayley graph. It turns out that to bound the Ricci curvature of these graphs it is useful to know the maximum degree among their vertices. The computation of the maximal degree has appeared in the literature only in type A (i.e., for the symmetric group) in [1]. In this thesis we study this problem for type B and type D. These results are of interest in their own right, and lead to non-trivial bounds on the Ricci curvature of the graphs. Here is in detail the structure of the thesis. Chapter 1 is the chapter of preliminaries. It is divided in three sections where the reader can find basic notions, definitions and results of Coxeter Theory and discrete Ricci curvature, including some applications of the latter. Moreover some results about numerical linear algebra are presented, which are later used in Chapters 2 and 4. The second Chapter is devoted to some results about the Ricci curvature in general graphs. In particular, the theorem that links the computation of the Ricci curvature to the computation of the minimum eigenvalue of a matrix (Theorem 2.3). The results that follow are bounds for the curvature of some families of graphs, for example trees. In this chapter we also show that any negative integer is the Ricci curvature of some graph. In Chapter 3 we study Bruhat graphs. As mentioned above, we show that the Bruhat graph of any finite Coxeter group has Ricci curvature equal to 2. The proof is case free, and relies on a result of Dyer [16] and on the definition of an equivalence relation on the set of reflections of a finite Coxeter group. In Chapter 4 we study the Ricci curvature of (the Hasse diagram of) the weak order of Coxeter systems. More precisely, we compute the Ricci curvature for both finite irreducible Coxeter groups and affine irreducible Weyl groups. The proofs use some classical techniques of linear algebra together some results described in Chapter 2. In Chapter 5 we study the Ricci curvature of the Hasse graph associated to the Bruhat order of finite Coxeter systems. Here we constrain the range of values that the Ricci curvature can take for type A, B and D. This is done by establishing inequalities that depend on the maximal degree of these graphs. In particular the maximal degree of the Hasse diagram of the Buhat order of type Bn is b n 2 2 c + n − 1 for n ≥ 5 and in type Dn is b n 2 2 c + n − 1. This is an extension of a result in [1] where it is stated that the maximal degree for the Bruhat order of An is b n 2 4 c + n − 2.