Skip to main content
MathOverflow

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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.

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.

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.

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.

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.

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.

minus sign
Source Link
Joe
Joe
  • 545
  • 3
  • 15

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)$$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$$$$|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$$

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$$

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$$

Source Link
Joe
Joe
  • 545
  • 3
  • 15

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 enter image description here

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.