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

[Allan Wechsler]

Oh, John, that is devilish. It certainly defeats my attempted algorithm.
But it's obviously not a counterexample -- you can still build it using
your extension operation, but my algorithm fails to find a correct
construction procedure.

Intuitively it is still absolutely clear that your construction conjecture
is true, but I am flailing for a satisfactory proof. But here is a start:

The polygon has straight sides of integer length. Let's imagine that we are
circumnavigating it counterclockwise. A side that is between two left
turns, we shall call a *candidate*. To the left of each candidate is a
contiguous rectangle of cells, n units long and m units wide, with m chosen
as large as possible. Call m the *depth* of the candidate. The big lemma is
that there always exists a candidate of depth greater than 1. My intuition
is if there is no candidate with depth greater than 1, then we can prove
that the polygon is not simply-connected, violating the premise. But I
can't make it go through.

On Mon, Feb 22, 2021 at 3:56 AM John Mason <masonmilan33 at gmail.com> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>