Supporting Software for Mathematics Publication
In discrete mathematics, graphs are networks of connected nodes. These graphs can be used to model a large variety of real world systems by applying attributes to the nodes and edges. These attributes could be in the form of labels, directions and weights.
A challenge in network theory is to apply the notion of curvature from surfaces to discrete structures such as graphs and networks. There are different variants of this curvature property depending on whether it is defined for the edges or nodes. Bakry-Émery curvature describes curvatures on the set of nodes, which are loosely related to the local connectivity of the network. This allows for the classification of networks by properties of their curvatures, for example non-negative and/or infinity curvature sharp.
The aim of this project was to classify all curvature sharp quartic (four-regular) networks. Quartic networks have four edges connected to each node. This research builds upon the research conducted by D. Cushing et. al. in which all cubic (three-regular) graphs with non-negative curvatures were classified. [1]
My role was to help develop software in Python to generate the full classification of local configurations with curvature sharp centres. [2] This was achieved in four stages:
- All possible radius two configurations of a quartic graph were generated recursively;
- The curvature of each graph was calculated using The Graph Curvature Calculator by G. Stagg and D. Cushing to remove graphs with negative curvature; [3]
- All isomorphisms (structurally equivalent graphs) were found and removed;
- The curvature sharpness condition was checked for the centres of each of the remaining graphs to provide the final result.
This result was crucial to derive a complete classification of the eight infinity curvature sharp graphs (pictured below). This formed the main theorem of the paper entitled Quartic Graphs that are Bakry-Émery Curvature Sharp which was published in Discrete Mathematics 343(3). [4]
The eight infinity curvature sharp graphs:
References
[1] Cushing, D., Kangaslampi, R., Lipiäinen, V., Liu, S. and Stagg, G., 2019. The Graph Curvature Calculator and the Curvatures of Cubic Graphs. Experimental Mathematics, [online] Available at: <https://doi.org/10.1080/10586458.2019.1660740>
[2] Gurr, F. and Watson May, L., 2019. Bakry-Émery Curvature Calculations Of Quartic 2-Balls And Graphs Of Diameter 2. [online] Available at: <https://arxiv.org/src/1902.10665v1/anc>.
[3] Cushing, D. and Stagg, G., 2017. The Graph Curvature Calculator. [online] Available at: <http://www.mas.ncl.ac.uk/graph-curvature/>.
[4] Cushing, D., Kamtue, S., Peyerimhoff, N. and Watson May, L., 2020. Quartic graphs which are Bakry-Émery curvature sharp. Discrete Mathematics, [online] 343(3), p.111767. [online] Available at: <https://doi.org/10.1016/j.disc.2019.111767>