Opened 4 years ago
Closed 4 years ago
#21308 closed enhancement (fixed)
implement the magnitude function of a graph
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  graph theory  Keywords:  
Cc:  tscrim, jmantysalo, darij  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  87f18ad (Commits)  Commit:  87f18ad6d6016375a45a2782aefd99aa4a28502f 
Dependencies:  Stopgaps: 
Description
the magnitude function is some kind of generalized Euler characteristic defined for metric spaces
in particular, graphs can be seen as metric spaces with edges of length one.
Let us implement the magnitude function for graphs.
Change History (9)
comment:1 Changed 4 years ago by
 Branch set to u/chapoton/21308
 Commit set to 290fea92c090dab6de9dda881524613ddcb2814b
comment:2 Changed 4 years ago by
 Commit changed from 290fea92c090dab6de9dda881524613ddcb2814b to 3430f54fe5e2399872602bef8d887775c02c199f
Branch pushed to git repo; I updated commit sha1. New commits:
3430f54  trac 21308 better doc

comment:3 Changed 4 years ago by
 Commit changed from 3430f54fe5e2399872602bef8d887775c02c199f to 8138e208df862d148f83e2d5784b72b5f75111b1
Branch pushed to git repo; I updated commit sha1. New commits:
8138e20  trac 21308 add one reference + more doc

comment:4 Changed 4 years ago by
 Commit changed from 8138e208df862d148f83e2d5784b72b5f75111b1 to 87f18ad6d6016375a45a2782aefd99aa4a28502f
Branch pushed to git repo; I updated commit sha1. New commits:
87f18ad  trac 21308 better doc

comment:5 Changed 4 years ago by
 Cc tscrim jmantysalo darij added
 Status changed from new to needs_review
comment:6 Changed 4 years ago by
Never heard about this before... Anyways, at https://www.math.unibielefeld.de/documenta/vol18/27.pdf p. 875 there is an example of magnitude function for 2+3 complete bipartite graph. It seems to go to value 5
when t
grows. However
sage: g = graphs.CompleteBipartiteGraph(3, 2) sage: m = g.magnitude_function() sage: m(4).n(20) 0.14839 sage: m(10).n(20) 0.029694
I suppose that I understood something wrong.
comment:7 Changed 4 years ago by
What is pictured page 875 is the function "magnitude in the variable t" defined by replacing q by exp(t)
Saying that the limit of that when t tends to +infinity is the cardinality, is the same as saying that the value of the fraction at q=0 is the cardinality.
comment:8 Changed 4 years ago by
 Reviewers set to Jori Mäntysalo
 Status changed from needs_review to positive_review
OK then. I would write "substitution q = e^{t}
to obtain" instead of "substitution q = exp(t)
to obtain", but not that big thing.
If I understand this correctly, it is much faster to compute by first substituting t
and then inverting the resulting numerical matrix  assuming the user wants only few values. However, this implementation is propably what the user wants.
Tests passed, documentation builds etc, so I mark this as positive review.
comment:9 Changed 4 years ago by
 Branch changed from u/chapoton/21308 to 87f18ad6d6016375a45a2782aefd99aa4a28502f
 Resolution set to fixed
 Status changed from positive_review to closed
branch not yet ready for review
New commits:
implement the magnitude function of a graph