Markov and lattice bases for Forman-Ricci curvature of graphs

Abstract

Discrete Forman-Ricci curvature is a quantity associated to each edge of a graph that describes its local geometry. It has proven to be a useful tool in network analysis in a variety of applications. Recent work by Roost et al.\ (2024) proposed the use of Markov bases to sample from the space of graphs with prescribed vertex degrees and curvatures. In the present work, we further develop the algebraic and combinatorial theory of these Markov bases. We show that the degree of an indispensable Markov move grows at least quadratically in the maximum degree of the graph. In light of this result, a compact description of all Markov basis elements seems unattainable at present. Instead, we find a lattice basis for this problem using only degree three Markov moves, which allows us to employ recently-developed reinforcement learning methods for finding Markov moves that can be applied to a specific graph.

19 pages, comments very welcome!