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

[Brendan McKay]

For r=8, the count is 4185406.  As far as combinatorial
explosions go, this is a slow rate of increase.

Brendan.

On 24/2/2023 2:15 pm, Brendan McKay wrote:
> 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/
>