Opened 6 years ago
Closed 6 years ago
#21308 closed enhancement (fixed)
implement the magnitude function of a graph
Reported by: | chapoton | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.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, GitHub, GitLab) | 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 6 years ago by
Branch: | → u/chapoton/21308 |
---|---|
Commit: | → 290fea92c090dab6de9dda881524613ddcb2814b |
comment:2 Changed 6 years ago by
Commit: | 290fea92c090dab6de9dda881524613ddcb2814b → 3430f54fe5e2399872602bef8d887775c02c199f |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
3430f54 | trac 21308 better doc
|
comment:3 Changed 6 years ago by
Commit: | 3430f54fe5e2399872602bef8d887775c02c199f → 8138e208df862d148f83e2d5784b72b5f75111b1 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
8138e20 | trac 21308 add one reference + more doc
|
comment:4 Changed 6 years ago by
Commit: | 8138e208df862d148f83e2d5784b72b5f75111b1 → 87f18ad6d6016375a45a2782aefd99aa4a28502f |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
87f18ad | trac 21308 better doc
|
comment:5 Changed 6 years ago by
Cc: | tscrim jmantysalo darij added |
---|---|
Status: | new → needs_review |
comment:6 Changed 6 years ago by
Never heard about this before... Anyways, at https://www.math.uni-bielefeld.de/documenta/vol-18/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 6 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 6 years ago by
Reviewers: | → Jori Mäntysalo |
---|---|
Status: | needs_review → 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 6 years ago by
Branch: | u/chapoton/21308 → 87f18ad6d6016375a45a2782aefd99aa4a28502f |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
branch not yet ready for review
New commits:
implement the magnitude function of a graph