Skip to content

Tuesday, 7 November 2017: Joint ACiD/NODES Seminar

David Cushing (Durham, Maths): Ollivier-Ricci idleness functions of graphs

Time and Location:

13:00 in CM101 (Durham)

see also http://community.dur.ac.uk/algorithms.complexity/seminars.html

Abstract:

Ricci curvature plays a very important role in the study of Riemannian manifolds. In the discrete setting of graphs, there is very active recent research on various types of Ricci curvature notions and their applications. One such notion on graphs is the Ollivier-Ricci curvature. This notion has recently had many applications, ranging from modelling cancer growth to modelling WiFi connections. This stems from this curvature notion being a way to quantify local connectedness.

We study the Ollivier-Ricci curvature of graphs as a function of the chosen idleness. We show that this idleness function is concave and piecewise linear with at most 3 linear parts, with at most 2 linear parts in the case of a regular graph. We then apply our result to show that the idleness function of the Cartesian product of two regular graphs is completely determined by the idleness functions of the factors. I will also present an interactive web applet which has helped in my investigations.