[seqfan] Re: Stan Wagon's Powers of Two Problem: News!

[Max Alekseyev]

Neil et al.,

In case anyone is interested, I have computed minimal forbidden subgraphs
(MFS) of order up to 10 for graphs appearing in https://oeis.org/A352178
An MFS is a graph that is not admissible/soluble (in the sense of A352178)
but every its smaller subgraph is.

The smallest MFS is the cycle C_4 as proved by M. S. Smith. One more MFS on
7 nodes is given in M. Bolan's memo (the "saw" formed by 3 triangles).
The other graph on 10 nodes with 16 edges ("graph A") that Bolan proves
insoluble happens to contain an MFS with 14 edges. In other words, it is
possible to remove 2 edges from graph A so that it will still be insoluble.

I've established that there exists one more MFS on 7 nodes with 9 edges
(also formed by 3 triangles), none on 8 or 9 nodes, and 15 MFSes on 10
nodes (1 with 13 edges, 11 with 14 edges, and 3 with 15 edges).

Drawing of these MFSes can be seen at Sagecell:
https://sagecell.sagemath.org/?q=onssar
Graphs' layout may slightly vary from time to time, and so it may be worth
it to click the [Evaluate] button a few times to get them placed nicely.

Regards,
Max

On Sat, Sep 24, 2022 at 5:15 PM Max Alekseyev <maxale at gmail.com> wrote:

> Hi Neil,
>
> I have written a piece of software that verified A352178(12) and
> A352178(13) being equal to their lower bounds - 19 and 21, respectively.
> I'll try to push this further.
>
> Regards,
> Max
>
> On Thu, Sep 22, 2022 at 4:43 PM Neil Sloane <njasloane at gmail.com> wrote:
>
>> Dear Sequence Fans,
>>
>> Remember Stan Wagon's Powers of Two Problem? Brady Haran and I made a
>> video
>> a year ago that Brady released yesterday together with a postscript:
>>
>> Brady Haran and N. J. A. Sloane, <a
>> href="https://youtu.be/IPoh5C9CcI8">Problems
>> with Powers of Two</a>, Youtube Numberphile Video, Sep 21 2022
>>
>> Brady Haran and N. J. A. Sloane, <a href="
>> https://www.numberphile.com/stop-press">STOP PRESS: Postscript to
>> Problems
>> with Powers of Two</a>, Sep 21 2022
>>
>> It has had 100K views already and there have been a lot of new results
>> even
>> today which you can see in https://oeis.org/A352178
>>
>> It's a lovely problem.
>> Best regards
>> Neil
>>
>> Neil J. A. Sloane, Chairman, OEIS Foundation.
>> Also Visiting Scientist, Math. Dept., Rutgers University,
>> Email: njasloane at gmail.com
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>