[seqfan] Re: Fwd: Re: Self avoiding polygons

[John Mason]

I reply to both Allan and Elijah.

I posted the problem because the approach of choosing one “side” of the polygon has difficulty in the following case. BTW, please make sure it arrives as Courier New, so that the spacing works.

OOOOOOO
O     O
O     O
O     O
O O O O
O O O O
OOO OOO

The only way to reduce is to find an endpoint. But how to describe that in a proof?

john 



Sent from Mail for Windows 10

From: Elijah Beregovsky
Sent: 22 February 2021 06:06
To: Sequence Fanatics Discussion list
Subject: [seqfan] Fwd: Re: Self avoiding polygons

Hi, John!
It's a pretty puzzle, thank you! Correct me, if there's a flaw in my logic.
1) Proving that every self-avoiding polygon can be constructed from a
smaller one is equivalent to proving that you can make every s.-a. polygon
smaller, using the inverse of your move.
2) Let's pretend that an irreducible self-avoiding polygon exists and look
at its segments. The segment cannot be, khm... UNshifted, iff doing it
either makes a polygon's perimeter smaller by more than 2, less than 2, or
dismembers the polygon into disjoint parts.
3) Let's look at the first case. In a "good" situation unshifting a segment
removes its endpoints from the perimeter, for example:
OOOO
OOOO
OOO
becomes
OOO
OOO
OOO
and loses two horizontal edges, but no vertical edges.
Thus, the only situation, when unshifting can reduce the perimeter by more
than 2, not leaving the polygon disjoint, is, when this destroys not only
endpoints, but also some of the other edges. But for that to be the case,
there should be no adjacent cells in the direction of an unshift, like here:
OOOOO
OO
you cannot make this by unshifting vertically:
OO
OO
But this doesn't dismember a polygon only if the neighbouring cells stop
exactly once during the segment, so one of endpoints looks like this:
...OO
But here you can shift the lonely endpoint cell horizontally and validly
reduce your polygon, so the first "bad" case is unrealizable in an
irreducible polygon!
4) The second case is easy to prohibit, by unshifting only segments, both
endpoints of which are free, so they'll be lost during unshifting. For
example:
OOO
OOO
You are disallowed to unshift half a segment, so you cannot make this:
OOO
OO
or this
OOO
O
5) Following pretty much the same logic as in the first case I come to a
conclusion that neighbors in the third case stop and start again at least
once. But let's look at the graph, constructed by making a vertex for each
segment and an edge for each pair of neighbouring segments. If every
segment has at least two disjoint sets of neighbors, then this graph has
cycles. But that means, that our polygon also has cycles, e.g.:
OOO
O   O
OOO
That means it is not self-avoiding. So the third "bad" case is also not
possible. Theorem proved!

Best wishes,
Elijah

--
Seqfan Mailing list - http://list.seqfan.eu/



-- 
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus