Can local flip moves connect dimer matchings on 'quadrangulated' planar bipartite graphs? (perfect matching reconfiguration problem)

Question

I'm interested in the structure of dimer matchings on planar graphs with a bipartite structure. In particular, I'm interested in whether any two perfect matchings can be connected, i.e. transformed into each other, by 'flip moves', which replace a dimer pair on opposite edges of a 4-cycle with the other possible pair. This problem was dubbed the "Perfect Matching Reconfiguration Problem" by the paper by Bonamy et al (where the picture is from). The linked paper studies this problem for many different types of graphs, but not for the general class of planar bipartite graphs.

Similar constructions for 'quadriculated graphs' in the plane that consist of squares meeting in an array in the plane have been in the affirmative by Thurston, in "Conway's Tiling Groups", and given necessary and sufficient conditions for other flat 2D surfaces like the torus, Mobius band Klein bottle in work by Saldanha et al, in "Spaces of domino tilings". And, similar statements showed some structure for the case of a 3D grid in work by Freire, Saldanha, et al, where they consider an additional 'trit' move.

My question is, for the case of planar graphs, when can we say that the space of tilings is connected under face flip moves? This is obviously false for the cycle graph of even length, since there are no 4-cycles at all. But, the case I'm specifically interested in is for the case, similar to the picture and references above, where the planar bipartite graph is generated by 2-cells which are 4-cycles. This is more general than the case of 'quadriculated' regions answered previously, but I can't seem to find if this is shown by anyone.

EDIT: I want to consider the case where the cellulated manifold is simply connected, since there are simple counterexamples if this condition isn't met, as indicated in Brendan's answer.

EDIT: Brendan has shown a counterexample for certain configurations of quadrangulations.

EDIT: See Lev's proof below, which verifies the conjecture for a large class of quadrangulations, where each vertex is attached to at least 4 facets.

Answer 1

I think the answer is "yes" for such quadrangulations that at least $4$ squares meet up in each inner vertex.

---

Snake game lemma

Consider the following game. We are given a planar graph $G$ with boundary being one cycle (called outer cycle $\partial G$). First player chooses a vertex on a boundary and then picks a neighboring vertex (not on a boundary).

The game proceeds as follows: players take turns moving the chosen vertex along the edges. They can not visit vertices which were already visited.

The goal of the first player is to move the chosen vertex to the outer cycle (on their turn). The second player is not allowed to move to the outer cycle, and wins if the first player can not take a turn. If the second player can not take a turn, the draw is called (this case will not be important in the application)

Note. For a square-tiled region on a plane the first player has an obvious strategy - always go up.

Proposition Suppose the graph is quadrangulated and $2$-colored, and also that in every vertex at least $4$ squares meet up. Then, the first player has a non-losing strategy.

Proof Put a metric structure of a surface with conical singularities on a disk in such a way that every square is an actual euclidean square with the side $1$. It is a space of non-positive curvature (CAT(0) space).

Fact the ball of radius $r$ in CAT(0) space is always strictly convex.

This is true because of the comparison triangle with the plane.

Strategy of the first player. The first player should at every turn attempt to increase the distance from the initial vertex $v_0$ on the boundary they started on. Consider the collection of squares meeting up in a vertex $v$ which is on a distance $r$ from $v_0$. The ball $B_r(v_0)$ intersects interiors of at most three squares neighboring each other (due to being convex). It means that first player can take a turn which increases the distance function.

Consider the set of diagonals emanating from the vertex $v$. Any two neighboring diagonals have the angle $\frac{\pi}{2}$ between them, so there exist two such neighboring diagonals that they are not contained in $B_r(v_0)$ (for the same reason - the directions such that the ray in this direction intersects $B_r(v_0)$ form an angle of at most $\pi$ due to the ball being convex).

Now, the first player should take turn along the edge which is contained between two such neighboring diagonals. Then, the second player can respond with two turns "the rightmost one" and the "leftmost one" which lead them to the ends of these diagonals (and hence the distance to the vertex $v_0$ be increased), or take any of the edges inbetween, which also won't lie in $B_r(v_0)$ due to convexity.

By following this strategy, the first player will increase the distance function every turn, hence has no chance at meeting the vertex the have already met at all and will eventually end up on a border.

Note. I believe for the quadrangulations of positive curvature the second player should typically win, but I had not prove it.

---

Global move lemma

Consider a graph $G$ as above. Suppose we fix a perfect matching of internal vertices (it is "frozen"). Then the two ways of perfect matching of this graph are connected by local moves (which will unfreeze the internal part of the perfect matching and then freeze it back). This operation will be called "global move".

Proof: let us call the vertices which are edge distance $1$ from the outer cycle "neighboring". We are going to find the path (inside the frozen part) between the neighboring vertices which is perfectly matched.

Let us play a Snake Game, starting from any vertex in the boundary, where the first player plays according to the non-losing strategy above, and the second player (who receives the vertex $v_i$) always picks the vertex which is matched with the current position. The draw case is not possible, because second player always has a correct turn.

So, the produced sequence of vertices will form a path of even length which is perfectly matched. It separates the disk into two parts. One of these parts admits the global move, and other will admit after we do the first global move (both can be done by induction hypothesis).

Composition of such moves will be a global move of the whole graph.

---

Local move connectivity

Consider a pair of dimer configurations on a graph. Their difference is a union of non-intersecting cycles (this is clear and seems to be very classical).

Let us proceed by doing global moves along these cycles.

$\blacksquare$

---

And now some notes on height functions. Consider the dual graph $T$ of our planar graph. Then, we have facets of $T$ colored in two colors. Consider the following (discrete) $2$-form $\alpha$: it takes value $+1$ over black facets and $-1$ over white facets.

The height function is constructed as follows: we need to find discrete $1$-form $\beta$ such that $d\beta = \alpha$. Then, integral of $\beta$ over the boundary of 2 neighboring facets is $0$, and integrating over the boundary of our tiles gives us the height function. It is always possible by Poincare lemma

The height function approach will work if the form $\beta$ satisfies the following positivity condition: for every edge $s$ oriented counterclockwise along the black facets $\beta (s) > 0$.

Important example is if our graph $G$ was $k$-regular (which means dual graph $T$ has only $k$-gonal dual facets). Then, the form can be taken $1/k$ on every edge (with orientation described above).

Then, if this positivity condition is fulfilled, the possible vertices for local moves will be exactly local minima and local maxima of height function (check it!)

Thurston proceeds doing local moves untill all local maxima in the interior of the tiling are removed, and then proves that the matching such that it has no local maxima in the interior is unique - by finding the maximum of the height function on the boundary and checking that it is unique near it and proceeding by induction. The argument transitions well (it is another simple check).

The question is how does one find such form $\beta$. I've tried using Hodge theory, but it didn't seem to be too successful.

Answer 2

Counterexample for general planar bipartite graphs

I'll take "the planar bipartite graph is generated by 2-cells which are 4-cycles" to mean that every edge lies on at least one 4-face.

Consider a circular ladder consisting of two cycles of even length $2k$ joined by $2k$ rungs. This a planar bipartite cubic graph.

There are four different perfect matchings which do not use any rungs. Two of them do not allow any flips at all, since each 4-cycle has only one matching edge.

For planar quadrangulations:

Such a simple counterexample is impossible. Since the number of faces is less (by 2) than the number of vertices, for any perfect matching there must be faces that have two edges of the matching. So flips are always possible.

(The above left so that the comments make sense.)

=============================================================

For general flips the conjecture is false:

Suppose we have a connected bipartite graph drawn in the plane. It might be thought that any two perfect matchings are connected by a sequence of flips, where a flip is to select a face whose boundary cycle is alternately in and out of the matching, then to complement the matching along that cycle.

Here is a counterexample.

In the left figure, flips can be done in the two 4-faces, but there is no way to make the matching in the right figure.

For quadrangulations the conjecture is false:

The only faces that can be flipped are the two yellow faces, and that fact is unchanged if they are flipped. So it is impossible to get from the left picture to the right picture. This and one other are the smallest counterexamples for simple (no parallel edges) quadrangulations. Starting at 26 vertices there are even counterexamples for 3-connected quadangulations.

Also on 26 vertices are two examples which are 3-connected and have no 4-cycles except face boundaries. Here is one.

Answer 3

I think I've come up with a condition for flip-connectivity for which Lev's elegant answer is a special case and that avoid Brendan's counterexamples. We'll also see that it supports Lev's intuition that a limited number of vertices with degree<4 are okay in some cases. The condition is the non-existence of certain configurations of cycles on the graph's interior and the faces surrounding them, which we'll call "daisy chains". A daisy chain $\mathcal{D}$ is a loop in the graph G (with possibly repeating vertices) that satisfies two conditions.

• The loop of $\mathcal{D}$ has an interior which is a set of polygons that share a vertex or are connected by line segments that the loop traverses along. The loop must always be on the boundary of these polygons/line segments.
• Every two edges adjacent on the loop whose vertex colors in sequence are "white $\rightarrow$ black $\rightarrow$ white" are part of a facet on the exterior of $\mathcal{D}$ (we could just as easily switch "black $\leftrightarrow$ white" in this part). We'll refer to this as the "outer facet condition"

An example of a daisy chain looks like

Here, the loop of vertices is colored red, the polygons and connecting lines are drawn in blue, the facets on the outside of the loop are drawn in yellow, and the dashed blue lines indicate either more polygons or a closure of of the polygon, all for which the loop goes around. Note that we may allow the outer facets to share vertices or edges.

Given this definition, our main claim is

Main Claim: Let $G$ be a bipartite quadrangulated graph. Then $G$ is flip-connected if $G$ has no daisy chains where all vertices in the loop are internal.

First before proving the claim, we'll show a stronger version of Lev's proposition, i.e. that flip-connectedness is true if every internal vertex has degree$\ge$4 holds if we assume this claim.

Proof of Lev's proposition assuming the main claim

Assuming the main claim, we'll show a stronger claim than Lev's. Namely if for every loop of internal vertices, the average degree of the vertex set $V_{in} := \{v | v \in \text{interior of loop OR } v \text{ is black and on the boundary of the loop} \}$ is at least 4, then no daisy chain of internal vertices can exist. This will be analogous to Brendan's observation in the comment section that the average degree of all vertices in a planar quadrangulated graph must be less than 4. But we'll need to write it out in more detail for this specfic case.

Define the set of white vertices contained on $\mathcal{D}'s$ boundary loop as $V^{w,\partial}$.

Let $|V|, E, F$ be the number of vertices, edges, faces of subgraph $S \subset G$ completely contained in the loop and inside the polygon. Then we'll have Euler's formula saying that $|V|-E+F=1$. First, we'll have that $|V| = |V_{in}| + |V^{w,\partial}|$.

To get expressions for $E$, the outer facet condition for the daisy chain is critical, since it ensures that the every edge of any vertex in $V_{in}$ is contained in the subgraph, i.e. that the degree of any $v \in V_{in}$ is the same when considered as a part of either the subgraph $S$ or the full graph $G$. We denote $\bar{d_{in}}$ as the average degree of vertices in $V_{in}$. And, we let $\bar{d_{in}}$ We'll note that there exists a positive integer $A \ge 0$ such that $\bar{d_{in}} |V_{in}| = 2E - 2 |V^{w,\partial}| - A$. This is because $\bar{d_{in}} |V_{in}|$ double counts every edge between vertices in $V_{in}$, but undercounts $2E$ by the sums of degrees of vertices in $V^{w,\partial}$ (where the 'degree' here means as a vertex in $S$). But every vertex in $V^{w,\partial}$ has at least two edges in $S$, which shows this formula.

Now, let's get one last expression for $E$. Since the graph is quadrangulated, we'll have that $4F = 2E - 2 |V^{w,\partial}| - A - B$, where $B \ge 0$ is an integer. This is because $4F$ gives a double count of all edges on the interior of S, but again undercounts because of the edges boundary loop and connectors. In fact, one can see that it undercounts by at least the same edges that $\bar{d_{in}} |V_{in}|$ does, which gives the "$-2 |V^{w,\partial}| - A$" terms. The extra positive number $B$ is because there might be vertices on the 'connecting part' between the polygons that don't get counted in $4F$ but do get counted in $\bar{d_{in}} |V_{in}|$

Putting these together, we get that $E = 2F + |V^{w,\partial}| + \frac{1}{2}(A + B)$, that $F = \frac{1}{4}(\bar{d_{in}} |V_{in}| - B)$, and that: $$V - E + F = (|V_{in}| + |V^{w,\partial}|) - (2F + |V^{w,\partial}| + \frac{1}{2}(A + B)) + F$$ So, we'll get that $$|V_{in}| - F - \frac{1}{2}(A + B) = |V_{in}| - \frac{1}{4}(\bar{d_{in}} |V_{in}| - B) - \frac{1}{2}(A + B)= 1$$

This gives us that $$(1-\frac{\bar{d_{in}}}{4}) |V_{in}| = 1 + \frac{A}{2} + \frac{B}{4} > 0$$ So, this is impossible if $\bar{d_{in}} \ge 4$, which implies the proposition of Lev.

Now it's time to prove the Main Claim.

Proof of Main Claim

The main idea is that these daisy chains end up being obstructions to being able to perform Lev's "global move" (see his answer for the definition) via local moves. I.e., if the global move is always possible to do from local moves, then the graph is flip-connected. However, if there is a loop in the graph such that the global move is impossible, we'll show that there must be a daisy chain in the graph.

Suppose that there is a perfect matching $\mathcal{P}$ of $G$ such that for some cycle $C$ in the graph with every alternate edge being in the perfect matching, the global move for $C$ is not possible (this cycle can't repeat vertices and is NOT the loop in the daisy chain). Without loss of generality, we'll focus our attention to the subgraph completely contained in $G$, so that the cycle $C$ is the boundary of $G$. From this, we can consider all matchings connected to $\mathcal{P}$ via flip moves. For all of these matchings, there must be a cycle $C'$ for which the global move is impossible, otherwise the graph would be flip-connected. We'll call such a cycle $C'$ irreducible.

Furthermore, we will choose the matching containing the "minimal" such irreducible cycle $C'$, defined as follows. $C'$ will be minimal if

• It contains the minimum number, $N$, of total vertices on the boundary of $C'$ and on the interior of $C'$
• Given the minimal $N$, $C'$ has a minimal number of strictly interior points for an irreducible cycle (i.e. maximal number of points on the boundary loop, $C'$).

So, again we can WLOG choose the graph $G$ with matching on it's boundary that is minimal and irreducible boundary cycle. First, we claim that there must be internal vertices inside $C$.

Suppose there are no internal vertices. We note that it's always possible to do at least one flip moves, since there are more edges in the matching than faces, so at least one face has two matched dimers on it. Performing a flip move on this face will split the outer cycle into two smaller cycles, contradicting the minimality of $C$. Induction will actually show that such an "outerplanar" graph is flip connected. (A statement for more general outerplanar graphs is in Bonamy et al).

So, let $w_0$ be an internal vertex that shares an edge with a boundary vertex $v$, and let's say that it is colored white. Note that $w_0$ must be matched with a black internal vertex $b_1$. Now, consider all (white) vertices $w_{1,i}$ indexed by $i$, that are connected to $b_1$. We'll have that the minimality and irreducibility of $C$ will guarantee that none of the $w_{1,i}$ are on the boundary.

If $w_{1,I}$ were on the boundary, then tracing the path $C'' := v \rightarrow w_0 \rightarrow b_1 \rightarrow w_{1,i} \rightarrow ...\text{boundary vertices}... \rightarrow v$ would create a cycle $C''$ with more boundary points or fewer internal vertices than $C$. So, since $C$ was minimal and irredicuble, the global move on $C''$ would be possible by local moves inside $C''$. And then the path in the other direction from the boundary point $w_{1,i}$ to $v$ would be a cycle of matches which also admits a global move, since it's not irreducible. This whole process is the global move on $C$. So since $C$ was irreducible and minimal, $w_{1,i}$ isn't on the boundary.

So, since the $w_{1,i}$ aren't on the boundary, if they are distinct from $w_0$, they have new vertices $b_{2,i}$ that they are matched with. Then consider all the white vertices $w_{2,I}$ (labeled by some appropriate multi-index $I$) who neighbor the $b_{2,i}$. The $w_{2,I}$ can't be on the boundary by the same argument as for the $w_{1,i}$. Iterating this process, we can consider the perfect matching partners $b_{n,I}$ of the new vertices in $w_{n-1,I}$ and then considering all the white neighbors of the $b_{n,I}$. The $w_{n-1,I}$ can never be on the boundary, again since $C$ is minimal and irreducible.

This process must terminate and eventually give no new vertices since $G$ is finite. When the process terminates, there will be a set of polygons and paths of links connecting them whose boundary consists of the vertices $w_{n,I}, b_{n,I}$ chosen, like the blue part of the figure above. (It is not necessary that all the vertices inside the polygons have been reached by the process, just that the boundary consists of ones that have been reached.) Since all these vertices are on the interior, each of them must be part of a 2-cell that is on the exterior of the polygons and connecting paths. But, any new edges coming from these external facets must be connected to the white vertices, since all the neighbors of black vertices have been chosen in the process. This means that on the boundary loop of the polygons and paths, every adjacent edges along the loop that have colors "white $\rightarrow$ black $\rightarrow$ white" must be part of a common facet.

These outer facets give our daisy chain, so we've completed out proof.