[seqfan] Re: Identifying sequence in Quanta Magazine graph theory article

William Orrick will.orrick at gmail.com
Thu Feb 23 17:37:07 CET 2023

Just a follow-up: The *Quanta* article is mostly about "The Euler
characteristic of the moduli space of graphs" by Michael Borinsky and Karen
Vogtmann (https://arxiv.org/abs/2301.01121). The preprint references a work
in preparation, "FORM as a tool for topological and
combinatorial computations" by Borinsky and Vermaseren. Perhaps that will
say more about these enumerations.

Anyway, I missed some graphs before. I'm now fairly certain that this
sequence is looking at graphs that

1) are unlabeled, undirected and connected,
2) are allowed to have loops and multiple edges,
3) have all vertices of valence 3 or more, and
4) are allowed to have bridges.

There are indeed 3 such graphs with circuit rank 2 and 15 such graphs with
circuit rank 3. The circuit rank is r = e - v + c, where c is the number of
components, which is 1 in our case.

For r = 2 we have one graph with v = 1, which looks like an eight, and two
graphs with v = 2, one of which looks like a theta and the other like a
dumbbell. (The latter has a bridge.)

For r = 3 we have one graph with v = 1, four graphs with v = 2, five graphs
with v = 3, and five graphs with v = 4. If bridges are disallowed, the
numbers change to one for v = 1, three for v = 2, two for v = 3, and two
for v = 4. (I was missing some four-vertex graphs in my previous message.

I have not confirmed the stated numbers for r = 4 and r = 10.

More information about the SeqFan mailing list