Abstract
Hepworth, Willerton, Leinster and Shulman introduced magnitude homology groups for enriched categories, and in particular for graphs. Although the construction of the boundary map suggests magnitude homology groups are strongly influenced by graph substructures it is not straightforward to detect such subgraphs. In this talk, we introduce eulerian magnitude homology and highlight its relation with magnitude homology. We then show how eulerian magnitude homology enables a more accurate analysis of graph substructures and apply these results to Erdos-Renyi random graphs and random geometric graphs, obtaining an asymptotic estimate for the Betti numbers of the eulerian magnitude homology groups on the first diagonal.
Motivation
What kind of information about a graph is contained in the magnitude homology?
Magnitude
Definition der Magnitudenhomologie (Graphtheorie)
Is there a generalization of a geodesic called a -Geodesic, which is a geodesic in a distance around ?
Eulerian Magnitude
Definition Eulerian Mangnitude Chain. (EMC) We now calculate the EMH of easy graphs.
The EMH counts detects information about cliques in subgraphs. This is captured by a bound (Giusti, Menara) In this talk we study the diagonal . How can this be used to compare graphs? Connectivity of Graphs? What about Expander Graphs?
Random ER Graphs (Erdös-Relyi-Graph)
Giusti, Menara 23: Let be a raondom graph. Eulerian homology groups on the first diagonal vanish for .
Expected Betti numbers: Kahle, Meckes, 2013 showed something about random clique graphs. Giusti and Menara then gave an analogous formula for the Betti numbers of the EMH about so called ER-Graphs.
Random Geometric Graphs (RGG)
Giusti, Menara 2023: Lat be a RGG graph. EMH on the first diagonal vanish for .
References
- Hepwort, Willerton 2017
- Leinster 2019
- Kahle, Meckes 2013/16
- Yu 2009