Markov and lattice bases for Forman-Ricci curvature of graphs
2026-08-03 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors studied a math concept called Forman-Ricci curvature that helps understand the shape of networks by looking at their edges. They built on recent work that uses special moves, called Markov moves, to explore all graphs with certain properties. The authors found that these moves can get very complicated as the graphs get bigger. Since describing all these moves fully is hard, they instead found a simpler set of moves to work with. This simpler set can be used with computer learning methods to analyze specific graphs more easily.
Forman-Ricci curvaturegraph theoryMarkov basesMarkov movesvertex degreesalgebraic combinatoricslattice basisreinforcement learningnetwork analysisgraph sampling
Authors
Jane Ivy Coons, Giulio Zucal
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.