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

[Brendan McKay]

Hi Will,

I can confirm 111 graphs fitting your description for r=4.

The values for r=5,6,7 are 1076, 13870, 220520.
I'm running r=8 but I don't plan to go further.

My program is cobbled together from pieces I already had and
is too stupid to reach r=10 in a reasonable amount of time.
Contacting the authors for verification of the definition
and the missing numbers would be the next step.

Brendan.

On 24/2/2023 3:37 am, William Orrick wrote:
> 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.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/