[seqfan] Possible method for determining bound of A288554

[Gary Thompson]

I have discovered what I believe to be an algorithm resulting in a
superset of A288554 that could be used to at the very least bound it,
and possibly with development start to converge on it. With minor
modifications, it should also work for the other related intersecting
circle arrangements, resulting in a reasonable bound for A250001, and
especially for the version that contains all topologically-conceivable
arrangements.

Please allow me some grace as I am not a mathematician but someone who
just enjoys puzzles. I’m going to try and get terms correct, but most
of this will be pretty naive, and I will throw conjectures out that
seem correct to me but will at least try and mention when I am
guessing. Mostly I just want to put forward the approach, as I haven't
seen it mentioned anywhere. And believe me I understand that may be
for very good reason. I honestly don’t want to waste any more
brainpower on it if it ends up being infeasible, so please tell me now
if I’ve gone astray.

First, we will define a new shape, the squiggle. Squiggles can be any
closed, simple curve with the property that any two k-squiggles can
only intersect at k points. For this initial algorithm, we will limit
ourselves to 2-squiggles.

All squiggles in the same figure will require different colors, the
first drawn squiggle will be red, subsequent squiggles will follow in
ROYGBIV order.

Now consider a tree, T. The root of the tree will contain 1 red squiggle.

To create a child node of depth n:

Begin in any face bounded by the squiggle drawn in the parent node.
Draw a closed path by passing through any adjacent edge, and
continuing through edges until each color in the figure has been
intersected exactly twice

Now here is the first place I stumble. I don’t have a good way to
label all the attributes of the resultant graph. It seems that there
might be ways to remove some of the symmetrical positions that this
algorithm is going to spit out by keeping track of how and when faces
were created, for example, and whether the path passes through the
unbounded plane. But for now I am just renumbering the faces by hand.

A simple search method for nodes of T could thus be:

1)Begin in the lowest numbered face in the most recently drawn squiggle
2)Go through the edge of the most recently drawn color that:
     -Has been visited <2 times in this path
     -Passes into a face that has not been thoroughly searched on previous nodes
     -If two unsearched faces are available, choose the face with the
lowest number
3) Repeat step 2 2(n-1) times. This will always return you to the
origin. I absolutely love this.
4) Repeat for all edges of all faces within the most recently drawn squiggle


Figure 1
https://docs.google.com/drawings/d/1TbtQPXKoBe94fL9txnflKL1CSjCg-xdhs0ImWSxNX5U/edit?usp=sharing

contains a demonstration for n=3. The paths searched in order are:

Face path: 1,0,1,2 Edge path: OORR
Face path: 1,0,3,2 Edge path: OROR
Face path: 1,0,3,0 Edge path: ORRO
Face path: 1,2,3,2 Edge path: ROOR

Thus, with just the above algorithm, we get T(n)=4

I *think* the search space should stay reasonably calculable for a
while, even without optimization. I can’t work out the math, but for
any given node of depth T(n) being drawn, the first choice will be
from at most n-1 edges. Path length is only 2(n-1), and options are
quickly pared down due to the edge color restriction and being
algorithmically forced back to the origin. Additionally, the list of
faces visited is rotatable, paring down the search.

The one issue that I see to be resolved before this can safely serve
as a bound is illustrated in figure 2:
https://docs.google.com/drawings/d/1iweaw2ai4qOGZ0kjvBi_JzjJGRp-6WcRXotys5BwrP8/edit?usp=sharing


Jon Wild mentioned:
“There *is* an operation that turns one into the other, and that is to turn
one inside-out, or to evert it around the central bound region that lies
outside all the circles, swapping its boundary with the outer boundary.“

which I think is the same as projecting it onto a sphere, which is how
I visualize it. I think this has the possibility of occurring any time
the path crosses the unbounded plane 2 or more times. My gut is this
can be handled just with a separate node on the tree any time this
occurs, but please correct this if it is wrong.

If we include this transform, we then have T(3)=5.

Interestingly, two of these (a and d in figure 1) can also be shown to
be able to transform into one another via that projection. After both
these transforms, we actually get back down to A288554(3) = 4. I do
not think this is entirely coincidence, but I would appreciate input
from someone who actually knows what they are doing.

Now, given that fully intersecting circles are a special case of
2-squiggles, A288554(n) <= T(n).
As n increases, there will obviously be symmetrical positions such as
in figure 3 ( https://docs.google.com/drawings/d/1cEZtXtVVp8CR8vGSiPhom8h-md2GL-hrDlG6RW_efDc/edit?usp=sharing
). Thus, assuming those transforms above are handled properly,
T(n)>A288554(n). I'm sure there exist methods to identify these to
bound it more closely though.

Any attempt at the other related series such as A275924 will
necessitate using {0,2} squiggles and modifying the algorithm
slightly.

The search space for these will be larger, so any means of removing
symmetrical positions from the search would expedite things. It should
still be manageable, I think.

Generalizing to k-squiggles is left as an exercise.