Opened 5 years ago
Closed 5 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 5 years ago by
- Branch set to u/chapoton/21308
- Commit set to 290fea92c090dab6de9dda881524613ddcb2814b
comment:2 Changed 5 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 5 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 5 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 5 years ago by
- Cc tscrim jmantysalo darij added
- Status changed from new to needs_review
comment:6 Changed 5 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 5 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 5 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 5 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