Oops, my claim that "a torus spanning configuration is necessarily a spanning configuration" is false. Some torus spanning configurations that loop more than once may not be spanning configurations. Tom Tom Karzes writes:

Variants of possible interest:

1. "Double-spanning" configurations which have both horzontal and vertical paths

2. Torus spanning configurations, which have a "north-south" loop on a torus. Note that a torus spanning configuration is necessarily a spanning configuration, but the reverse is not always true. Note that some paths may loop multiple times before connecting back.

3. Torus double-spanning configurations, which contain loops along both axes.

Tom

Cris Moore via math-fun writes:

...

My friend Stephan Mertens and I just proved something you might enjoy. Consider filling a subset of the cells of an n-by-m rectangular lattice. Call the resulting configuration “spanning" if there is a path of occupied cells from the top row to the bottom row (stepping orthogonally).

Let N_even (N_odd) be the number of spanning configurations with an even (resp. odd) number of occupied cells. Show that N_even-N_odd = +1 or -1, and determine the sign as a function of n and m. As a corollary, the total number of spanning configurations is odd.

For instance, for n=m=2 there are 7 spanning configurations, with N_even=3 and N_odd=4.

Cris

Cris Moore moore@santafe.edu

true. but indeed my claims also hold for spanning configurations on the vertical cylinder, i.e. where there is a path from the top row to the bottom row, and each “row” is a cycle. Cris

On Sep 2, 2019, at 6:48 PM, Tom Karzes <karzes@sonic.net> wrote:

Oops, my claim that "a torus spanning configuration is necessarily a spanning configuration" is false. Some torus spanning configurations that loop more than once may not be spanning configurations.

Tom

Tom Karzes writes:

...

Variants of possible interest:

1. "Double-spanning" configurations which have both horzontal and vertical paths

2. Torus spanning configurations, which have a "north-south" loop on a torus. Note that a torus spanning configuration is necessarily a spanning configuration, but the reverse is not always true. Note that some paths may loop multiple times before connecting back.

3. Torus double-spanning configurations, which contain loops along both axes.

Tom

Cris Moore via math-fun writes:

...

My friend Stephan Mertens and I just proved something you might enjoy. Consider filling a subset of the cells of an n-by-m rectangular lattice. Call the resulting configuration “spanning" if there is a path of occupied cells from the top row to the bottom row (stepping orthogonally).

Let N_even (N_odd) be the number of spanning configurations with an even (resp. odd) number of occupied cells. Show that N_even-N_odd = +1 or -1, and determine the sign as a function of n and m. As a corollary, the total number of spanning configurations is odd.

For instance, for n=m=2 there are 7 spanning configurations, with N_even=3 and N_odd=4.

Cris

Cris Moore moore@santafe.edu

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Wow, Tom, that is impressive. I haven’t checked all the details but I think the strategy is right. Our proof is here: https://arxiv.org/pdf/1909.01484.pdf <https://arxiv.org/pdf/1909.01484.pdf> It’s maybe a bit simpler, and you might enjoy the following strategy: define a partial pairing on spanning configurations that gives most of them a partner with opposite parity (namely by flipping a single site). These pairs cancel each other, and the remaining un-paired configurations are easy to count. Best! - Cris

On Sep 3, 2019, at 9:54 AM, Tom Karzes <karzes@sonic.net> wrote:

Here's my solution:

The (even - odd) count depends on both the width (w) and height (h).

If w is even, the sequence is: -1, -1, 1, 1, -1, -1, ... If w is odd, the sequence is: -1, 1, -1, 1, -1, 1, ...

In closed form:

When w is even, the (even - odd) difference is:

-1 (if h mod 4 = 1 or 2) 1 (if h mod 4 = 0 or 3)

When w is odd, the (even - odd) difference is:

-1 (if h mod 2 = 1) 1 (if h mod 2 = 0)

Here's my somewhat verbose, but simple, proof:

Let f(w, h) be the number of spanning configurations for a grid of width w and height h, where w, h >= 1. Let fe(w, h) and fo(w, h) be the number of spanning configurations with an even (fe) or odd (fo) cell count, so f(w, h) = fe(w, h) + fo(w, h).

If h = 1, all configurations are spanning except for the empty configuration, so:

f(w, 1) = 2**w - 1

fe(w, 1) = 2**(w-1) - 1 fo(w, 1) = 2**(w-1)

and:

fe(w, 1) - fo(w, 1) = -1

If h >= 2, consider a spanning configuration for a w x h grid. Then the w x (h-1) grid composed of the bottom h-1 rows must be a spanning configuration for the w x (h-1) grid. Classify the cells of the top row of that grid as either live or dead. They are live if they are filled and are part of a path within the w x (h-1) grid from the top to bottom row. Otherwise they are dead, either empty or filled but not part of a spanning path in the w x (h-1) grid.

For a given w x (h-1) spanning configuration, we can enumerate all w x h spanning configurations that contain that w x (h-1) configuration as the lower h-1 rows. The top row must contain at least one filled cell above one of the live cells of the w x (h-1) grid. The rest of the cells can each be empty or filled without affecting the solution.

Suppose there are v live cells in the top row of the w x (h-1) grid, and d dead cells (so v + d = w). There are 2**v - 1 possible cell configurations above the live cells that produce a spanning configuration for the w x h grid (only the empty configuration is disallowed), and 2**d possible configurations above the dead cells, for a total of (2**d) * (2**v - 1) configurations.

If d >= 1, then half of these row configurations contain an even number of filled cells and half contain an odd number, so the total contribution contains an equal number of even vs. odd configurations. This is due to half of the 2**d configurations for the cells above the dead cells containing an even number of filled cells and half containing an odd number.

So for each of the cases with d >= 1, the even and odd filled cell counts match. These cases therefore do not affect the difference between the even and odd spanning configurations.

This leaves the case where d = 0. In this case, the top row of the w x (h-1) spanning configuration consists entirely of live, filled cells.

Take all of these cases together, i.e. all of the spanning configurations of the lower w x (h-1) grid that contain all filled cells in the top row. For each of these, there are 2**w - 1 row configurations for the top row of the w x h grid that result in a spanning configuration of the w x h grid (only the empty row is disallowed).

Of these 2**w - 1 configurations of the top row, 2**(w-1) - 1 contain an even number of filled cells and 2**(w-1) contain an even number of filled cells.

Now consider the top two rows of the w x h grid (the second of which consists of all filled cells). There are two cases:

(1) If w is even, then there are 2**(w-1) - 1 configurations that contain an even number of cells in the top two rows, and 2**(w-1) that contain an odd number.

(2) If w is odd, then there are 2**(w-1) configurations that contain an even number of cells in the top two rows, and 2**(w-1) - 1 that contain an odd number.

In other words, the second row inverts the parity of the top row if w is odd.

If h = 2, then this accounts for the entire w x h grid. So:

fe(w, 2) - fo(w, 2) = -1 (if w is even) fe(w, 2) - fo(w, 2) = 1 (if w is odd)

If h >= 3, consider the fact that the spanning configurations for the w x (h-1) grid whose top row consists entirely of filled cells correspond one-to-one to the spanning configurations of the w x (h-2) grid consisting of the lower h-2 rows.

Let:

p = fe(w, h-2) - fo(w, h-2)

So:

fe(w, h-2) = fo(w, h-2) + p

Let de(w, h) and do(w, h) be the number of even (de) and odd (do) configurations of the w x h grid that are derived from the w x (h-2) grid in this manner. So:

fe(w, h) - fo(w, h) = de(w, h) - do(w, h)

If w is even, we have:

de(w, h) = fe(w, h-2) * (2**(w-1) - 1) + fo(w, h-2) * 2**(w-1) = fe(w, h-2) * 2**(w-1) + fo(w, h-2) * 2**(w-1) - fe(w, h-2) = 2**(w-1) * (fe(w, h-2) + fo(w, h-2)) - fe(w, h-2)

do(w, h) = fe(w, h-2) * 2**(w-1) + fo(w, h-2) * (2**(w-1) - 1) = fe(w, h-2) * 2**(w-1) + fo(w, h-2) * 2**(w-1) - fo(w, h-2) = 2**(w-1) * (fe(w, h-2) + fo(w, h-2)) - fo(w, h-2)

de(w, h) - do(w, h) = -(fe(w, h-2) - fo(w, h-2)) = -p

fe(w, h) - fo(w, h) = -p

If w is odd, we have:

de(w, h) = fe(w, h-2) * 2**(w-1) + fo(w, h-2) * (2**(w-1) - 1) = fe(w, h-2) * 2**(w-1) + fo(w, h-2) * 2**(w-1) - fo(w, h-2) = 2**(w-1) * (fe(w, h-2) + fo(w, h-2)) - fo(w, h-2)

do(w, h) = fe(w, h-2) * (2**(w-1) - 1) + fo(w, h-2) * 2**(w-1) = fe(w, h-2) * 2**(w-1) + fo(w, h-2) * 2**(w-1) - fe(w, h-2) = 2**(w-1) * (fe(w, h-2) + fo(w, h-2)) - fo(w, h-2)

de(w, h) - do(w, h) = fe(w, h-2) - fo(w, h-2) = p

fe(w, h) - fo(w, h) = p

So:

fe(w, h) - fo(w, h) = -p (if w is even) fe(w, h) - fo(w, h) = p (if w is odd)

Combining all the cases:

fe(w, 1) - fo(w, 1) = -1

fe(w, 2) - fo(w, 2) = -1 (if w is even) fe(w, 2) - fo(w, 2) = 1 (if w is odd)

and for h >= 3:

fe(w, h) - fo(w, h) = -(fe(w, h-2) - fo(w, h-2)) (if w is even) fe(w, h) - fo(w, h) = fe(w, h-2) - fo(w, h-2) (if w is odd)

When w is even:

fe(w, 1) - fo(w, 1) = -1 fe(w, 2) - fo(w, 2) = -1

and for h >= 3:

fe(w, h) - fo(w, h) = -(fe(w, h-2) - fo(w, h-2))

The sequence is: -1, -1, 1, 1, -1, -1, ...

fe(w, h) - fo(w, h) = -1 (if h mod 4 = 1 or 2) fe(w, h) - fo(w, h) = 1 (if h mod 4 = 0 or 3)

When w is odd:

fe(w, 1) - fo(w, 1) = -1 fe(w, 2) - fo(w, 2) = 1

and for h >= 3:

fe(w, h) - fo(w, h) = fe(w, h-2) - fo(w, h-2)

The sequence is: -1, 1, -1, 1, -1, 1, ...

fe(w, h) - fo(w, h) = -1 (if h mod 2 = 1) fe(w, h) - fo(w, h) = 1 (if h mod 2 = 0)

Tom

Cris Moore via math-fun writes:

...

My friend Stephan Mertens and I just proved something you might enjoy. Consider filling a subset of the cells of an n-by-m rectangular lattice. Call the resulting configuration “spanning" if there is a path of occupied cells from the top row to the bottom row (stepping orthogonally).

Let N_even (N_odd) be the number of spanning configurations with an even (resp. odd) number of occupied cells. Show that N_even-N_odd = +1 or -1, and determine the sign as a function of n and m. As a corollary, the total number of spanning configurations is odd.

For instance, for n=m=2 there are 7 spanning configurations, with N_even=3 and N_odd=4.

Cris

Cris Moore moore@santafe.edu

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun