Okay, the proof as I see it has these components: 1. There's an optimal configuration without the connectedness requirement that consists of k nested squares; each square is a closed edge path. 2. There's an existing construction (due to Allan) that makes slight perturbations to this (k-1 changes to link the k edge rings on a 2k x 2k board). This construction also makes the edges connected, with even degree on each point, so there's a Hamiltonian path with strictly clockwise (or counterclockwise) directions. This construction simply decreases the PSWN on k-1 cells from which the edge changes can be derived. 3. In order to link an edge path to another, where the first lies entirely inside the second, we need to change at least one cell that is inside the first edge path and outside the other. If there is one edge path not connected to but entirely inside the another edge path, then there's a set of cells with the same PSWN that separate the two edge paths. 4. Since there are k unconnected nested rectangles to link, we need to make at least k-1 cell changes to link them. By (2) we know how to do this. On Thu, Mar 24, 2016 at 6:12 AM, James Propp <jamespropp@gmail.com> wrote:
It's also interesting to look at my example going in the reverse direction, from
101 010 101
to
101 000 101.
The central square starts out with winding-number x=1, unlike its four neighbors, which start out with winding-number x-1. When we reduce the winding-number at the middle from x to x-1, we turn a 1-component picture into a 4-component picture. Right? (Actually, maybe Tom and Gareth would call the initial picture a 2-component picture, but either way, the number of components goes UP, and by more than 1.)
This makes it hard for me to understand the passage "Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing."
Jim
On Thu, Mar 24, 2016 at 9:03 AM, James Propp <jamespropp@gmail.com> wrote:
Actually, I goofed last night: what I had in mind was a comparison of
101 000 101
("before") and
101 010 101
("after"). The intuition behind my example will be clearer if I explain these arrays as (grid-)multipaths. Label the nine vertices as
ABCD EFGH JKLM NOPQ
(I left out "I" because it's so narrow, since so many of us use non-fixed-width mail-readers).
Start with a 4-component multipath consisting of the closed paths AEFBA, JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. We get the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding number around the center square has changed. (I hope I got it right this time!) Anyway, the multipath changes from having four components to having just one component. (Unless Tom and Gareth are using a different definition of components.)
Anyway, in addition to wanting to understand better why there must be at least k-1 grid-squares at which single-component pattern doesn't achieve maximal winding number, I'd like to know the constraints on the locations of those grid-squares. In Allan's example, the grid-squares were all on the same diagonal. Is that forced by Tom and Gareth's analysis (which I'm still trying to understand)?
Jim
On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp@gmail.com> wrote:
I expect that Gareth and Tom will find my remarks about
010 111 010
obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --