Opened 3 years ago

Closed 3 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) 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 3 years ago by chapoton

  • Branch set to u/chapoton/21308
  • Commit set to 290fea92c090dab6de9dda881524613ddcb2814b

branch not yet ready for review


New commits:

290fea9implement the magnitude function of a graph

comment:2 Changed 3 years ago by git

  • Commit changed from 290fea92c090dab6de9dda881524613ddcb2814b to 3430f54fe5e2399872602bef8d887775c02c199f

Branch pushed to git repo; I updated commit sha1. New commits:

3430f54trac 21308 better doc

comment:3 Changed 3 years ago by git

  • Commit changed from 3430f54fe5e2399872602bef8d887775c02c199f to 8138e208df862d148f83e2d5784b72b5f75111b1

Branch pushed to git repo; I updated commit sha1. New commits:

8138e20trac 21308 add one reference + more doc

comment:4 Changed 3 years ago by git

  • Commit changed from 8138e208df862d148f83e2d5784b72b5f75111b1 to 87f18ad6d6016375a45a2782aefd99aa4a28502f

Branch pushed to git repo; I updated commit sha1. New commits:

87f18adtrac 21308 better doc

comment:5 Changed 3 years ago by chapoton

  • Cc tscrim jmantysalo darij added
  • Status changed from new to needs_review

comment:6 Changed 3 years ago by jmantysalo

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 3 years ago by chapoton

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 3 years ago by jmantysalo

  • 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 3 years ago by vbraun

  • Branch changed from u/chapoton/21308 to 87f18ad6d6016375a45a2782aefd99aa4a28502f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.