# Reconfiguration of Independent Transversals

Pjotr Buys Korteweg–de Vries Institute for Mathematics, University of
Amsterdam, Netherlands. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Ross J.
Kang11footnotemark: 1 Kenta Ozeki Faculty of Environment and Information
Sciences, Yokohama National University, Japan. Email: ozeki-kenta-
<EMAIL_ADDRESS>
###### Abstract

Given integers $\Delta\geq 2$ and $t\geq 2\Delta$, suppose there is a graph of
maximum degree $\Delta$ and a partition of its vertices into blocks of size at
least $t$. By a seminal result of Haxell, there must be some independent set
of the graph that is transversal to the blocks, a so-called independent
transversal. We show that, if moreover $t\geq 2\Delta+1$, then every
independent transversal can be transformed within the space of independent
transversals to any other through a sequence of one-vertex modifications,
showing connectivity of the so-called reconfigurability graph of independent
transversals.

This is sharp in that for $t=2\Delta$ (and $\Delta\geq 2$) the connectivity
conclusion can fail. In this case we show furthermore that in an essential
sense it can only fail for the disjoint union of copies of the complete
bipartite graph $K_{\Delta,\Delta}$. This constitutes a qualitative
strengthening of Haxell’s theorem.

##  1 Introduction

A common refrain in combinatorics is that once you have one you have many,
that is to say, combinatorial objects of a desired structure. The phenomenon,
going back at least to unpublished work in 1941 of Rademacher (see [Erd55]),
is referred to as supersaturation and may be observed in many, especially
extremal, combinatorial contexts. We pursue a similar line that, rather than
multitude, asks instead for topological structure in the space of desired
combinatorial objects. Our study sits in a broader programme called
combinatorial reconfiguration, see [vdH13], an area that was originally
motivated by various Markov chains arising in theoretical computer science.
Despite there being a conceptual link between the two areas through discrete
probability, there has been surprisingly little exploration of reconfiguration
in the context of extremal combinatorics. Here we take a marked step in this
direction.

The background for the result we build upon began in a dialogue between Erdős
and Woodall at a problem session of the 3rd British Combinatorial Conference
at Merton College, Oxford in 1972 (see [Erd72, BES75]). There arose the
following problem. Given $\Delta\geq 2$, what is the least $t=t(\Delta)$ such
that the following holds: for any graph of maximum degree $\Delta$ and any
partition of its vertices into blocks each of order at least $t$, there is
guaranteed to exist some independent set that is transversal to the vertex-
partition? In a notable application of topological methods, solving a
conjecture of Bollobás, Erdős and Szemerédi [BES75], Haxell [Hax95, Hax01]
resolved this problem by showing that a choice of $t=2\Delta$ suffices. It is
interesting to note, moreover, that for every $\Delta\geq 2$ the choice
$t=2\Delta-1$ is not sufficient, as shown by Szabó and Tardos [ST06]. As such,
Haxell’s result is exactly extremal, marking out its importance in (extremal)
combinatorics.

Given this sharpness, it might be natural to ask for more in a sense alluded
to in the first paragraph. What conditions guarantee connectedness in the
space of independent transversals of a given vertex-partitioned graph? We give
a sharp answer to this question that is analogous to Haxell’s theorem. We show
that, if $t\geq 2\Delta+1$, then every independent transversal (of some graph
of maximum degree $\Delta$ vertex-partitioned into blocks of size at least
$t$) can be modified one vertex at a time to obtain any other, all the while
remaining within the space of independent transversals. This result is also
exactly extremal in that there are examples of vertex-partitioned
$\Delta$-regular graphs that show how the assertion fails when $t=2\Delta$.
Below, we state a more precise result which implies the above statements and
also gives a partial characterisation of connectivity in the space of
independent transversals at the threshold $t=2\Delta$.

Before that let us present our findings again in a different, perhaps more
evocative way. Let $V(H)$ be a collection of particles and suppose each
particle can take one of $t$ spins chosen from $[t]=\\{1,\dots,t\\}$. Suppose
that the admissibility of a spin configuration on $V(H)$ is governed (on the
basis of hard-core interactions) by some graph $G$ on the vertex set
$V(G)=V(H)\times[t]$: we have an edge of $G$ between $(u,i)$ and $(v,j)$
whenever $u\neq v$ and spin $i$ on particle $u$ is incompatible with spin $j$
on particle $v$. Equivalently, every admissible configuration is an
independent set of $G$ that takes each particle of $V(H)$ in a pair exactly
once. Consider the following Markov chain Monte Carlo algorithm which runs
over the state space consisting of all admissible configurations on $V(H)$.

> Initialise $X_{0}\subseteq V(G)$ as an arbitrary admissible configuration on
> $V(H)$.
>
> Perform the following for $s=0,1,\dots$
>

>> Choose some vertex $(u,i)$ of $G$ uniformly at random.

>>

>> If $(u,i)$ is adjacent in $G$ to some vertex of $X_{s}$, then go directly
to iteration $s+1$.

>>

>> Else, let $X_{s+1}$ be the admissible configuration formed from $X_{s}$ by
including $(u,i)$ (and so excluding the vertex of $X_{s}$ that contains the
particle $u$).

While Haxell’s theorem guarantees the state space of this Markov chain to be
nonempty (so that $X_{0}$ is well-defined) provided $t\geq 2\Delta(G)$, where
$\Delta(G)$ denotes the maximum degree of $G$, our main result guarantees the
Markov chain to be ergodic provided $t\geq 2\Delta(G)+1$.

We remark that Glauber dynamics on the proper $t$-colourings of some graph $H$
may be formulated in a similar way as above. The ergodicity of the
corresponding Markov chain provided $t\geq\Delta(H)+2$ is an exercise, as is
non-emptiness of its state space when $t\geq\Delta(H)+1$; see [Jer95] for more
context.

We next introduce some notation in order to state our main result more
carefully, as well as set up terminology for the proof. Let $G$ be a graph and
let $\mathcal{U}$ be a partition of the vertex set $V(G)$. An independent
transversal of the pair $(G,\mathcal{U})$ is an independent set $S$ of $G$
such that $|S\cap U|=1$ for all $U\in\mathcal{U}$. The partition $\mathcal{U}$
is said to be _$t$ -thick_ if the cardinality of each block $U\in\mathcal{U}$
satisfies $|U|\geq t$. Here is a restatement of Haxell’s theorem in this
notation.

######  Theorem 1.1 ([Hax95, Hax01]).

Let $G$ be a graph of maximum degree $\Delta$ and let $\mathcal{U}$ be a
$(2\Delta)$-thick partition of $V(G)$. Then there exists an independent
transversal of $(G,\mathcal{U})$.

We denote the set of independent transversals of a pair
$\mathcal{G}=(G,\mathcal{U})$ by $\operatorname{IT}(\mathcal{G})$. We define
an adjacency relation on $\operatorname{IT}(\mathcal{G})$ by stipulating that
$S\sim T$ for $S,T\in\operatorname{IT}(\mathcal{G})$ if and only if $S\cup T$
is an independent set of size $|\mathcal{U}|+1$. In other words, $S$ and $T$
are adjacent if and only if they agree on all but one block $U\in\mathcal{U}$
and on $U$ their respective vertices are not adjacent in $G$ (this seemingly
extraneous condition will be important to the argument). We call the graph on
vertex set $\operatorname{IT}(\mathcal{G})$ defined by this adjacency relation
the _reconfigurability graph_ of $\mathcal{G}$. We say that $S$ is
_reconfigurable_ to $T$ if $S$ and $T$ lie in the same connected component of
the reconfigurability graph.

Given two graph-partition pairs $\mathcal{G}_{1}=(G_{1},\mathcal{U}_{1})$ and
$\mathcal{G}_{2}=(G_{2},\mathcal{U}_{2})$ we define their union as
$\mathcal{G}_{1}\cup\mathcal{G}_{2}=(G_{1}\sqcup
G_{2},\mathcal{U}_{1}\cup\mathcal{U}_{2})$, where $\sqcup$ denotes disjoint
graph union. Observe that there is a natural bijection between
$\operatorname{IT}(\mathcal{G}_{1}\cup\mathcal{G}_{2})$ and
$\operatorname{IT}(\mathcal{G}_{1})\times\operatorname{IT}(\mathcal{G}_{2})$
and that $(S_{1},S_{2})$ is reconfigurable to $(T_{1},T_{2})$ within
$\mathcal{G}_{1}\cup\mathcal{G}_{2}$ if and only if $S_{1}$ is reconfigurable
to $T_{1}$ within $\mathcal{G}_{1}$ and $S_{2}$ is reconfigurable to $T_{2}$
within $\mathcal{G}_{2}$. Therefore, when studying reconfigurablity, we will
often assume that our graph-partition pairs $\mathcal{G}$ cannot be written as
$\mathcal{G}_{1}\cup\mathcal{G}_{2}$ for nontrivial
$\mathcal{G}_{1},\mathcal{G}_{2}$. In such cases, we refer to $\mathcal{G}$ as
_irreducible_.

We are now prepared to fully state our main theorem.

######  Theorem 1.2.

Let $G$ be a graph of maximum degree $\Delta$ and let $\mathcal{U}$ be a
$(2\Delta)$-thick partition of $V(G)$ for which $\mathcal{G}=(G,\mathcal{U})$
is irreducible. If $G$ is not a disjoint union of $|\mathcal{U}|$ copies of
$K_{\Delta,\Delta}$, then the reconfigurability graph of $\mathcal{G}$ is
connected.

Note that if $\mathcal{U}$ is a $(2\Delta+1)$-thick partition of $V(G)$, then
the hypothesis is trivially satisfied, immediately yielding one of our main
claims. By contrast, clearly there are $(2\Delta)$-thick examples where the
conclusion fails when the hypothesis fails. A simple example is a single copy
of $K_{\Delta,\Delta}$ with a single-block partition, but there are more
intricate examples, and it would be an interesting problem to find a
characterisation.

As an aside, we find it curious to juxtapose Theorem 1.2 and a result of
Aharoni, Holzman, Howard, Sprüssel [AHHS15]: if $G$ is a graph of maximum
degree $\Delta$ and $\mathcal{U}$ is a $(2\Delta-1)$-thick partition of
$V(G)$, then if $G$ contains fewer than $2\Delta-1$ disjoint copies of
$K_{\Delta,\Delta}$, then there exists an independent transversal of
$(G,\mathcal{U})$. The proof of Theorem 1.2 builds conceptually upon one of
the (combinatorial) proofs of Theorem 1.1 (see [GH20]), even though it needs
much more technical care. To aid the comparison, we give below a proof of
Theorem 1.1 in our setup/notation as a warmup. (As a bonus, this warmup
ensures that with respect to Theorem 1.2 our paper is logically self-
contained.)

At the end of the paper, we offer a few thoughts on further research
directions leading on directly from Theorem 1.2.

##  2 Proof of the main theorem

In this section we will refer to a pair $\mathcal{G}=(G,\mathcal{U})$, where
$\mathcal{U}$ is a $(2\Delta(G))$-thick partition of $V(G)$, as an _instance_.
For the rest of this section we will, given an instance, write $\Delta$
instead of $\Delta(G)$, which, to avoid trivialities, we will assume to be
strictly positive.

We refer to the elements of $\mathcal{U}$ as _blocks_. For
$\mathcal{R}\subseteq\mathcal{U}$ we define
$V_{\mathcal{R}}=\bigcup_{U\in\mathcal{R}}U$, we let $G_{\mathcal{R}}$ denote
the induced subgraph $G[V_{\mathcal{R}}]$, and we let
$\mathcal{G}_{\mathcal{R}}$ denote the instance
$(G_{\mathcal{R}},\mathcal{R})$. For a subset of vertices $X\subseteq V(G)$ we
let $\mathcal{U}_{X}$ denote the set of blocks that intersect $X$, i.e.
$\mathcal{U}_{X}=\\{U\in\mathcal{U}:U\cap X\neq\emptyset\\}$, and we define
the _closure_ of $X$ as $\operatorname{cl}(X)=V_{\mathcal{U}_{X}}$. Finally we
let $X_{\mathcal{R}}=X\cap V_{\mathcal{R}}$ and for a single block
$U\in\mathcal{U}$ we write $X_{U}$ to mean $X_{\\{U\\}}$.

Given two independent transversals $S,T\in\operatorname{IT}(\mathcal{G})$ we
say that $S$ and $T$ _agree_ on a block $U\in\mathcal{U}$ if $S_{U}=T_{U}$ and
we say that $S$ and $T$ agree on a subset $\mathcal{R}\subseteq\mathcal{U}$ if
$S$ and $T$ agree on every block in $\mathcal{R}$. Given a vertex $v\in V(G)$
for which $\\{v\\}\cup S$ is an independent set we let $S\oplus v$ denote the
independent transversal $(S\setminus S_{U})\cup\\{v\\}$, where $U$ is the
block containing $v$. Note that $S$ and $S\oplus v$ are adjacent (or equal)
independent transversals in the reconfigurability graph.

We proceed by proving an extremal version of Theorem 1.2.

######  Lemma 2.1.

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance and suppose
$S,T\in\operatorname{IT}(\mathcal{G})$ cannot be reconfigured to agree on any
block. Then $G$ is isomorphic to the disjoint union of $|\mathcal{U}|$ copies
of $K_{\Delta,\Delta}$.

###### Proof.

Any $v\in V(G)$ must be adjacent to at least one vertex in $S\cup T$ since
otherwise $S$ and $T$ could be reconfigured to $S\oplus v$ and $T\oplus v$
respectively. We therefore find

$2\Delta|\mathcal{U}|\leq|V(G)|\leq\sum_{v\in V(G)}|N_{G}(v)\cap(S\cup
T)|=\sum_{u\in S\cup T}|N_{G}(u)|\leq\Delta\cdot|S\cup
T|=2\Delta|\mathcal{U}|.$

We find that every inequality must be an equality from which we can conclude
that $\\{N_{G}(u):u\in S\cup T\\}$ partitions $V(G)$ into neighbourhoods of
size $\Delta$. In particular $S\cup T$ must induce a matching between $S$ and
$T$, which can be lifted to a permutation $\sigma:\mathcal{U}\to\mathcal{U}$
sending $U$ to the block containing the matched vertex in $T$ of the unique
vertex in $S\cap U$.

For $U\in\mathcal{U}$ let $R_{U}=N_{G}(T)\cap U$ and $B_{U}=N_{G}(S)\cap U$.
We claim that any $s\in R_{U}$ is adjacent to any $t\in B_{\sigma(U)}$.
Indeed, observe that $S\oplus s$ and $T\oplus t$ are again independent
transversals, and together, by the same reasoning as above, they induce a
matching in $G$ which lifts to a permutation $\sigma^{\prime}$ of
$\mathcal{U}$. Because $\sigma$ and $\sigma^{\prime}$ are equal on
$\mathcal{U}\setminus\\{U\\}$ they must in fact be equal on $\mathcal{U}$ and
thus $s$ is adjacent to $t$.

We can conclude that $|R_{U}|\leq\Delta$ and $|B_{U}|\leq\Delta$ for all
$U\in\mathcal{U}$. On the other hand we have that
$2\Delta\leq|U|=|R_{U}|+|B_{U}|$. Therefore $|R_{U}|=|B_{U}|=\Delta$ for all
$U\in\mathcal{U}$. This shows that $G$ is isomorphic to the disjoint union of
$|\mathcal{U}|$ copies of $K_{\Delta,\Delta}$, namely those induced by the
parts $(R_{U},B_{\sigma(U)})_{U\in\mathcal{U}}$. ∎

###  2.1 Transforming instances

The proof of Theorem 1.2 that we give is by induction on $|\mathcal{U}|$. The
induction step involves transforming an instance $\mathcal{G}$ into a smaller
instance $\mathcal{G}^{\prime}$. We describe this transformation in this
section.

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance and suppose that $G$ has a
component $K$ isomorphic to $K_{\Delta,\Delta}$ with bipartition $(A,B)$.
Suppose furthermore that there is a block $U\in\mathcal{U}$ such that
$A\subseteq U$. Let $\mathcal{B}=\mathcal{U}_{B}\setminus\\{U\\}$ and let
$\mathcal{R}=\mathcal{U}\setminus(\\{U\\}\cup\mathcal{B})$. Observe that

$\bigcup_{W\in\mathcal{B}}|W\cap B|=\Delta-|U\cap B|=2\Delta-|U\cap(A\cup
B)|\leq|U\setminus(A\cup B)|,$

and thus we can partition $U\setminus(A\cup B)$ into sets
$\\{Y(W):W\in\mathcal{B}\\}$ satisfying $|B\cap W|\leq|Y(W)|$. For
$W\in\mathcal{B}$ we define $W^{\prime}=(W\setminus B)\cup Y(W)$, we let
$\mathcal{B}^{\prime}=\\{W^{\prime}:W\in\mathcal{B}\\}$, and we let
$\mathcal{G}^{\prime}=(G-K,\mathcal{B}^{\prime}\cup\mathcal{R})$. Observe that
$\mathcal{G}^{\prime}$ is an instance with one fewer block than $\mathcal{G}$.
We say that $\mathcal{G}^{\prime}$ _is obtained by swapping $B$ and
$U\setminus A$_.

We describe a map from the independent transversals of $\mathcal{G}^{\prime}$
to sets of independent transversals of $\mathcal{G}$, i.e. a map
$M:\operatorname{IT}(\mathcal{G}^{\prime})\to\mathcal{P}(\operatorname{IT}(\mathcal{G}))$.
Let $S$ be an independent transversal of $\mathcal{G}^{\prime}$ and partition
$\mathcal{B}^{\prime}$ into
$\mathcal{V}_{S}^{\prime}\cup\mathcal{Y}_{S}^{\prime}$ where
$\mathcal{V}_{S}^{\prime}=\\{W^{\prime}\in\mathcal{B}^{\prime}:S\cap
W^{\prime}\subseteq W\\}$ and
$\mathcal{Y}_{S}^{\prime}=\\{W^{\prime}\in\mathcal{B}^{\prime}:S\cap
W^{\prime}\subseteq Y(W)\\}$. If $\mathcal{Y}_{S}^{\prime}$ is empty we let

$M(S)=\\{\\{a\\}\cup S:a\in A\\}.$

Otherwise we let

$M(S)=\\{\\{y\\}\cup X\cup S_{\mathcal{V}^{\prime}_{S}\cup\mathcal{R}}:y\in
S_{\mathcal{Y}_{S}^{\prime}}\text{ and $X$ a transversal of }\\{B\cap
W:W^{\prime}\in\mathcal{Y}_{S}^{\prime}\\}\\}.$

Observe that indeed every $T\in M(S)$ is a transversal of $\mathcal{U}$ and
$\bigcup_{T\in M(S)}T$ is an independent set of $G$. It follows that $M$ is a
well-defined map from $\operatorname{IT}(\mathcal{G}^{\prime})$ to
$\mathcal{P}(\operatorname{IT}(\mathcal{G}))$ and that any pair in $M(S)$ is
reconfigurable to each other. See Figure 1 for an example.

######  Lemma 2.2.

Let $S_{1},S_{2}\in\operatorname{IT}(\mathcal{G}^{\prime})$ be adjacent
(within $\mathcal{G}^{\prime}$) independent transversals. Then any independent
transversal in $M(S_{1})$ is reconfigurable (within $\mathcal{G}$) to any
independent transversal in $M(S_{2})$.

###### Proof.

It is sufficient to show that there are independent transversals $T_{1}\in
M(S_{1})$ and $T_{2}\in M(S_{2})$ such that $T_{1}$ is reconfigurable to
$T_{2}$ within $\mathcal{G}$.

Let $v,w\in V(G-K)$ such that $S_{2}=S_{1}\setminus\\{v\\}\cup\\{w\\}$ and let
$T_{1}\in M(S_{1})$. If both $v,w$ are elements of a block in $\mathcal{R}$ or
if $v,w$ are either both in $Y(W)$ or both in $W^{\prime}\setminus Y(W)$ for
some $W\in\mathcal{B}$ then $T_{1}\oplus w\in M(S_{2})$. We will thus assume
that there is a block $W\in\mathcal{B}$ such that $v\in W^{\prime}\setminus
Y(W)$ and $w\in Y(W)$. We take $b\in B\cap W$.

If $\mathcal{Y}_{S_{1}}^{\prime}$ is empty then $T_{1}\to T_{1}\oplus
w\to(T_{1}\oplus w)\oplus b$ is a valid reconfiguration from an independent
transversal in $M(S_{1})$ to an independent transversal in $M(S_{2})$. If
$\mathcal{Y}_{S_{1}}^{\prime}$ is not empty then $T_{1}\to T_{1}\oplus b$ is a
valid reconfiguration from an independent transversal in $M(S_{1})$ to an
independent transversal in $M(S_{2})$. ∎

$\mathcal{G}$$\mathcal{G}^{\prime}$$y_{3}$$Y(W_{3})$$Y(W_{2})$$Y(W_{1})$$B$$A$$U$$B$$W_{3}$$B$$W_{2}$$B$$W_{1}$$v_{1}$$v_{0}$$\mathcal{B}$$\mathcal{R}$$Y(W_{1})$$W_{1}^{\prime}$$v_{1}$$v_{0}$$Y(W_{2})$$y_{2}$$W_{2}^{\prime}$$Y(W_{3})$$y_{3}$$W_{3}^{\prime}$$\mathcal{B}^{\prime}$$\mathcal{R}$$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{0}$$u_{1}$$u_{2}$$u_{3}$
Figure 1: An example of an instance $\mathcal{G}^{\prime}$ obtained by
swapping $B$ and $U\setminus A$ in $\mathcal{G}$. The sets
$S_{1}=\\{u_{0},u_{1},u_{2},u_{3}\\}$ and
$S_{2}=\\{v_{0},v_{1},y_{2},y_{3}\\}$ are two examples of independent
transversals in $\mathcal{G}^{\prime}$ an element from both $M(S_{1})$ and
$M(S_{2})$ is drawn in $\mathcal{G}$.

###  2.2 Descent using augmenting sequences

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance, let $S$ be a partial
independent transversal of $\mathcal{G}$, i.e. an independent set for which
$|S_{U}|\leq 1$ for all $U\in\mathcal{U}$, and let $C\subseteq
V_{\mathcal{U}\setminus\mathcal{U}_{S}}$. Given a sequence of vertices
$\mathbf{v}=(v_{1},\dots,v_{m})$ we define the sequence of blocks
$\mathcal{B}_{n}$ by $\mathcal{B}_{0}=\mathcal{U}\setminus\mathcal{U}_{S}$ and
$\mathcal{B}_{n}=\mathcal{B}_{n-1}\cup\mathcal{U}_{N_{S}(v_{n})}$ for
$n=1,\dots,m$ and we define the sequence of vertex sets $C_{n}$ by $C_{0}=C$
and $C_{n}=C_{n-1}\cup N_{S}[v_{n}]$ for $n=1,\dots,m$. We define the degree
sequence $d(\mathbf{v})=(d_{1}(\mathbf{v}),\dots,d_{m}(\mathbf{v}))$ with
$d_{k}(\mathbf{v})=|N_{S}(v_{k})|$ for all $k=1,\dots,m$, and the number of
degrees is denoted by $\textrm{length}(\mathbf{v})$, that is,
$\textrm{length}(\mathbf{v})=m$. We say that $\mathbf{v}$ is _augmenting_ for
$(S,C)$ if for all $k=1,\dots,m$ we have

  1. 1.

$v_{k}\in V_{\mathcal{B}_{k-1}}$;

  2. 2.

$v_{k}$ is not adjacent to any vertex in $C_{k-1}$; and

  3. 3.

$d_{k}(\mathbf{v})>0$ if $k\neq m$.

The empty sequence, denoted by $\varnothing$, is considered augmenting. We
call a tuple $(S,C,\mathbf{v})$ _feasible_ for $\mathcal{G}$ if $S$ and $C$
are as described above and $\mathbf{v}$ is augmenting for $(S,C)$.

We introduce a strict partial order on the set of all feasible tuples. We say
that $(S,C,\mathbf{v})<(S^{\prime},C^{\prime},\mathbf{v}^{\prime})$ if
$|S|>|S^{\prime}|$ or if $|S^{\prime}|=|S|$ and there is an index $1\leq
k\leq\textrm{length}(\mathbf{v})$ such that
$d_{i}(\mathbf{v})=d_{i}(\mathbf{v}^{\prime})$ for all $i<k$ and either
$k>\textrm{length}(\mathbf{v}^{\prime})$ or
$d_{k}(\mathbf{v})<d_{k}(\mathbf{v}^{\prime})$. This condition is equivalent
to the following lexicographical inequality of infinite padded sequences

$(d_{1}(\mathbf{v}),\dots,d_{m}(\mathbf{v}),\infty,\infty,\dots)<(d_{1}(\mathbf{v}^{\prime}),\dots,d_{m^{\prime}}(\mathbf{v}^{\prime}),\infty,\infty,\dots).$

We remark that $(S,C,\mathbf{v})<(S,C,\varnothing)$ for any nonempty sequence
$\mathbf{v}$ that is augmenting for $(S,C)$. It follows directly from the
definition that, given a feasible tuple $(S,C,\mathbf{v})$, we have

$|C_{k}|\leq|C|+k+\sum_{i=1}^{k}d_{i}(\mathbf{v})\quad\text{ and
}\quad|\mathcal{B}_{k}|=|\mathcal{U}\setminus\mathcal{U}_{S}|+\sum_{i=1}^{k}d_{i}(\mathbf{v}).$
(1)

Haxell’s theorem (c.f. Theorem 1.1) can be proved via a descent through the
space of feasible tuples as is sketched in [GH20]. To familiarise ourselves
with the technique we reproduce the argument with our notation.

###### Proof of Haxell’s theorem.

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance and let
$(S,\emptyset,\mathbf{v})$ with $\mathbf{v}=(v_{1},\dots,v_{m})$ be a minimal
feasible tuple for $\mathcal{G}$. We will prove that $S$ is a full independent
transversal. We suppose otherwise, i.e. we suppose that
$\mathcal{U}\setminus\mathcal{U}_{S}$ is not empty.

We first claim $\mathbf{v}$ is nonempty and that $d_{m}(\mathbf{v})=0$.
Otherwise

$|V_{\mathcal{B}_{m}}|\geq
2\Delta\left(|\mathcal{U\setminus}\mathcal{U}_{S}|+\sum_{i=1}^{m}d_{i}(\mathbf{v})\right)\geq\Delta\left(2|\mathcal{U}\setminus\mathcal{U}_{S}|+m+\sum_{i=1}^{m}d_{i}(\mathbf{v})\right)>\Delta\cdot|C_{m}|.$

This implies that there is a vertex $v_{m+1}\in V_{\mathcal{B}_{m}}$
independent of $C_{m}$ and thus the sequence
$\mathbf{v}^{\prime}=(v_{1},\dots,v_{m},v_{m+1})$ is augmenting for
$(S,\emptyset)$ and thus $(S,\emptyset,\mathbf{v}^{\prime})$ is a strictly
smaller feasible tuple than $(S,\emptyset,\mathbf{v})$. This contradicts
minimality.

We may thus assume that $m\geq 1$ and $d_{m}(\mathbf{v})=0$. Let $k$ be the
smallest index for which $v_{m}\in V_{\mathcal{B}_{k}}$. If $k=0$ then
$v_{m}\in V_{\mathcal{U}\setminus\mathcal{U}_{S}}$ and thus
$S^{\prime}=S\cup\\{v_{m}\\}$ is strictly larger partial independent
transversal than $S$. This implies that
$(S^{\prime},\emptyset,\varnothing)<(S,\emptyset,\mathbf{v})$, contradicting
minimality. If $k\geq 1$ let $S^{\prime}=S\oplus v_{m}$ and
$\mathbf{v}^{\prime}=(v_{1},\dots,v_{k})$. Now $\mathbf{v}^{\prime}$ is
augmenting for $(S^{\prime},\emptyset)$, $|S^{\prime}|=|S|$,
$d_{i}(\mathbf{v}^{\prime})=d_{i}(\mathbf{v})$ for $i<k$, and
$d_{k}(\mathbf{v}^{\prime})=d_{k}(\mathbf{v})-1$. It follows that
$(S^{\prime},\emptyset,\mathbf{v}^{\prime})<(S,\emptyset,\mathbf{v})$, which
again contradicts minimality. ∎

The proof of the following lemma is very similar. Its corollary will be used
in the proof of Theorem 1.2.

######  Lemma 2.3.

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance with independent transversal
$S$. Moreover, let $X\subseteq V(G)$ with $|X|<\Delta$. Then $S$ can be
reconfigured to $S^{\prime}$ satisfying $S^{\prime}\cap X=\emptyset$.

###### Proof.

We can reconfigure $S$ to $T$ where $(T\setminus X,T\cap X,\mathbf{v})$ is a
minimal element within the following set:

$\\{(T\setminus X,T\cap X,\mathbf{v}):S\text{ can be reconfigured to $T$ and
$\mathbf{v}\cap X=\emptyset$}\\}.$

We claim that $T\cap X=\emptyset$. To show this we assume otherwise and we
will find that this contradicts the minimality of $(T\setminus X,T\cap
X,\mathbf{v})$. We write $\mathbf{v}=(v_{1},\dots,v_{m})$.

Suppose $m\geq 1$ and $d_{m}(\mathbf{v})=0$. Then $v_{m}$ is independent of
$T$ and thus we can reconfigure $T$ to $T^{\prime}=T\oplus v_{m}$. If
$v_{m}\in\operatorname{cl}(T\cap X)$ then $T^{\prime}$ is an independent
transversal satisfying $|T^{\prime}\setminus X|>|T\setminus X|$, contradicting
the minimality of $(T\setminus X,T\cap X,\mathbf{v})$. Otherwise there is an
index $k<m$ such that $v_{m}\in\mathcal{U}_{N_{T}(v_{k})}$. In this case we
let $\mathbf{v}^{\prime}=(v_{1},\dots,v_{k})$ and we observe that
$\mathbf{v}^{\prime}$ is feasible for $(T^{\prime}\setminus X,T^{\prime}\cap
X)$ with $d_{i}(\mathbf{v}^{\prime})=d_{i}(\mathbf{v})$ for $i<k$ and
$d_{k}(\mathbf{v}^{\prime})=d_{k}(\mathbf{v})-1$ and thus
$(T^{\prime}\setminus X,T^{\prime}\cap X,\mathbf{v}^{\prime})<(T\setminus
X,T\cap X,\mathbf{v})$.

We can thus assume that $d_{i}(\mathbf{v})\geq 1$ for $i=1,\dots,m$ (where we
now allow $m=0$). Then we see, using equation (1), that

$|V_{\mathcal{B}_{m}}|\geq 2\Delta\left(|T\cap
X|+\sum_{i=1}^{m}d_{i}(\mathbf{v})\right)\geq\Delta\left(1+|T\cap
X|+m+\sum_{i=1}^{m}d_{i}(\mathbf{v})\right)>|X|+|N_{G}(C_{m})|.$

This means that there is a vertex $u\in V_{\mathcal{B}_{m}}\setminus X$
independent of $C_{m}$, and thus $\mathbf{v}^{\prime}=(v_{1},\dots,v_{m},u)$
is an augmenting sequence for $(T\setminus X,T\cap X)$ with $(T\setminus
X,T\cap X,\mathbf{v}^{\prime})<(T\setminus X,T\cap X,\mathbf{v})$
contradicting the minimality assumption. This concludes the proof. ∎

######  Corollary 2.4.

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance with
$S,T\in\operatorname{IT}(\mathcal{G})$ and let
$\mathcal{R}\subseteq\mathcal{U}$ such that $S,T$ agree on $\mathcal{R}$ and
$N_{G}((S\cup T)\cap V_{\mathcal{U}\setminus\mathcal{R}})\subseteq
V_{\mathcal{U}\setminus\mathcal{R}}$. Suppose $x\in
V_{\mathcal{U}\setminus\mathcal{R}}$ has at least one neighbour in
$V_{\mathcal{U}\setminus\mathcal{R}}$. Then $(S,T)$ can be reconfigured to
$(S_{x},T_{x})$ such that $S_{x}$ and $T_{x}$ agree on $\mathcal{R}$, both $S$
agrees with $S_{x}$ and $T$ agrees with $T_{x}$ on
$\mathcal{U}\setminus\mathcal{R}$, and $x$ is independent of $(S_{x}\cup
T_{x})\cap V_{\mathcal{R}}$.

###### Proof.

Observe that $R:=S_{\mathcal{R}}\cap V_{\mathcal{R}}=T_{\mathcal{R}}\cap
V_{\mathcal{R}}$ is an independent transversal of $\mathcal{G}_{\mathcal{R}}$.
Let $X=N_{G}(x)\cap V_{\mathcal{R}}$ and observe that $|X|<\Delta$. It follows
from the previous lemma that $R$ can be reconfigured on
$\mathcal{G}_{\mathcal{R}}$ to $R^{\prime}$ with $R^{\prime}\cap X=\emptyset$.
Because $N_{G}((S\cup T)\cap V_{\mathcal{U}\setminus\mathcal{R}})\subseteq
V_{\mathcal{U}\setminus\mathcal{R}}$ this corresponds to a valid
reconfiguration of $(S,T)$ to $(S_{x},T_{x})$. ∎

###  2.3 Reconfiguring independent transversals

In this section we will prove Theorem 1.2. For two sets $X,Y$ we let
$X\triangle Y=(X\cup Y)\setminus(X\cap Y)$ denote the symmetric difference of
$X$ and $Y$. Given an instance $\mathcal{G}=(G,\mathcal{U})$ with
$S_{0},T_{0}\in\operatorname{IT}(\mathcal{G})$ we define the set

${\bf{X}}(S_{0},T_{0})=\\{(S,T,\mathbb{\mathbf{v}}):\text{$(S_{0},T_{0})$ is
reconfigurable to $(S,T)$ and $\mathbf{v}$ is augmenting for $(S\cap
T,S\triangle T)$}\\}.$

The set ${\bf{X}}(S_{0},T_{0})$ is endowed with a strict partial order
inherited by the strict partial order on the feasible tuples $(S\cap
T,S\triangle T,\mathbf{v})$. Observe that $S_{0}$ can be reconfigured to
$T_{0}$ if and only if the minimal elements of ${\bf{X}}(S_{0},T_{0})$ are of
the form $(S^{\prime},S^{\prime},\varnothing)$. Given
$(S,T,\mathbf{v})\in{\bf{X}}(S_{0},T_{0})$ equation (1) simplifies to

$|C_{k}|\leq|S\triangle T|+k+\sum_{i=1}^{k}d_{i}(\mathbf{v})\quad\text{ and
}\quad|\mathcal{B}_{k}|=\frac{1}{2}|S\triangle
T|+\sum_{i=1}^{k}d_{i}(\mathbf{v}).$ (2)

######  Lemma 2.5.

Let $\mathcal{G}$ be an instance with
$S_{0},T_{0}\in\operatorname{IT}(\mathcal{G})$ and let
$(S,T,\mathbf{v})\in{\bf X}(S_{0},T_{0})$ with
$\mathbf{v}=(v_{1},\dots,v_{m})$. Suppose $m\geq 1$ and either
$d_{m}(\mathbf{v})=0$ or $d_{k}(\mathbf{v})\geq 2$ for some $k$. Then
$(S,T,\mathbf{v})$ is not minimal in ${\bf X}(S_{0},T_{0})$.

###### Proof.

Assume first that $d_{m}(\mathbf{v})=0$. This means that $v_{m}$ is not
adjacent to any element of $S\cup T$ and thus $(S,T)$ can be reconfigured to
$(S^{\prime},T^{\prime})=(S\oplus v_{m},T\oplus v_{m})$.

Let $k$ be the smallest index for which $v_{m}\in C_{k}(\mathbf{v})$. If $k=0$
then $v_{m}\in\operatorname{cl}(S\triangle T)$ and thus $S^{\prime}$ and
$T^{\prime}$ agree on one more block and thus
$(S^{\prime},T^{\prime},\emptyset)<(S,T,\mathbf{v})$. Otherwise, we see that
$v_{m}\in\operatorname{cl}(N_{S,T}(v_{k}))$. Now
$\mathbf{v}^{\prime}=(v_{1},\dots,v_{k})$ is an augmenting sequence for
$(S^{\prime},T^{\prime})$ satisfying
$d_{i}(\mathbf{v}^{\prime})=d_{i}(\mathbf{v})$ for $i<k$ and
$d_{k}(\mathbf{v}^{\prime})=d_{k}(\mathbf{v})-1$, which implies
$(S^{\prime},T^{\prime},\mathbf{v}^{\prime})<(S,T,\mathbf{v})$. This proves
the statement if $d_{m}(\mathbf{v})=0$.

Now we assume that $d_{m}(\mathbf{v})\geq 1$ and there is some index $k$ for
which $d_{k}(\mathbf{v})\geq 2$. It follows from equation (2) that

$\displaystyle\Delta|C_{m}|\leq\Delta\left(|S\triangle
T|+m+\sum_{i=1}^{m}d_{i}(\mathbf{v})\right)<2\Delta\left(\frac{1}{2}|S\triangle
T|+\sum_{i=1}^{m}d_{i}(\mathbf{v})\right)\leq|V_{\mathcal{B}_{m}}|.$

It follows that there is a vertex $v_{m+1}\in V_{\mathcal{B}_{m}}$ not
adjacent to any vertex in $C_{m}$. Therefore, letting
$\mathbf{v}^{\prime}=(v_{1},\dots,v_{m},v_{m+1})$, we find
$(S,T,\mathbf{v}^{\prime})\in{\bf X}(S_{0},T_{0})$ with
$(S,T,\mathbf{v}^{\prime})<(S,T,\mathbf{v})$. ∎

######  Lemma 2.6.

Let $\mathcal{G}=(G,\mathcal{U})$ be an instance with
$S_{0},T_{0}\in\operatorname{IT}(\mathcal{G})$ and let $(S,T,\mathbf{v})$ be
minimal inside ${\bf{X}}(S_{0},T_{0})$. Then $\\{N_{G}(u):u\in C_{m}\\}$
partitions $V_{\mathcal{B}_{m}}$, where $m=\rm{length}(\mathbf{v})$.

###### Proof.

If $S=T$ then $\mathbf{v}$ is the empty sequence and both $C_{0}$ and
$V_{\mathcal{B}_{0}}$ are empty and thus the statement is trivially true.

Suppose now $S\neq T$ and write $\mathbf{v}=(v_{1},\dots,v_{m})$. It follows
from 2.5 that $d_{i}(\mathbf{v})=1$ for all $i$. We also observe that any
vertex in $V_{\mathcal{B}_{m}}$ must be adjacent to some vertex in $C_{m}$.
From equation (2) we obtain $\Delta|C_{m}|\leq\Delta(|S\triangle
T|+2m)\leq|V_{\mathcal{B}_{m}}|$, which shows that the neighbourhoods of
elements in $C_{m}(\mathbf{v})$ must all have size $\Delta$, cannot intersect,
and must cover $V_{\mathcal{B}_{m}}$. ∎

######  Lemma 2.7.

Let $\mathcal{G}=(G,\mathcal{U})$ be an irreducible instance with
$S_{0},T_{0}\in\operatorname{IT}(\mathcal{G})$ and let $(S,T,\mathbf{v})$ be
minimal inside ${\bf{X}}(S_{0},T_{0})$. Then either $S\cap T=\emptyset$,
$S=T$, or $\mathbf{v}\neq\varnothing$.

###### Proof.

We suppose that neither $S\cap T$ nor $S\triangle T$ is empty but that
$\mathbf{v}$ is empty. It follows from 2.6 that $\\{N_{G}(u):u\in S\triangle
T\\}$ partitions $\operatorname{cl}(S\triangle T)$. Let
$\mathcal{R}=\mathcal{U}_{S\cap T}$. Because $\mathcal{G}$ is irreducible
there is a vertex $x\in V_{\mathcal{U}\setminus\mathcal{R}}$ that has a
neighbour in $V_{\mathcal{R}}$. This implies that $x\not\in S\cup T$. The
vertex $x$ must have a unique neighbour in $S\triangle T$, say in $T$. It
follows from 2.4 that $(S,T)$ can be reconfigured to $(S_{x},T_{x})$ such that
$S_{x}$ and $T_{x}$ agree on $\mathcal{R}$, both $S$ agrees with $S_{x}$ and
$T$ agrees with $T_{x}$ on $\mathcal{U}\setminus\mathcal{R}$, and $(S_{x}\cup
T_{x})\cap V_{\mathcal{R}}\cap N_{G}(x)=\emptyset$. It follows that $S_{x}$ is
independent of $x$ and thus $(S,T)$ can be reconfigured to
$(S^{\prime},T^{\prime}):=(S_{x}\oplus x,T_{x})$.

The transversals $S^{\prime}$ and $T^{\prime}$ agree on exactly the same
blocks as $S$ and $T$ and thus $(S^{\prime},T^{\prime},\varnothing)$ is
minimal in ${\bf{X}}(S_{0},T_{0})$. This implies that $\\{N_{G}(u):u\in
S^{\prime}\triangle T^{\prime}\\}$ partitions
$\operatorname{cl}(S^{\prime}\triangle
T^{\prime})=\operatorname{cl}(S\triangle T)$. This contradicts the fact that
$x$ has a neighbour in $V_{\mathcal{R}}$, which concludes the proof. ∎

We are now ready to prove the main theorem, which we restate for convenience.
See 1.2

###### Proof.

The proof is by induction on $|\mathcal{U}|$. For $|\mathcal{U}|=1$ the
statement follows from 2.1. We will thus assume that $|\mathcal{U}|>1$ and
that the statement holds for instances with strictly fewer than
$|\mathcal{U}|$ blocks. Let $S_{0},T_{0}\in\operatorname{IT}(\mathcal{G})$ and
let $(S,T,\mathbf{v})$ be a minimal element in ${\bf X}(S_{0},T_{0})$ and
write $\mathbf{v}=(v_{1},\dots,v_{m})$. If $S=T$ we are done and thus we will
assume that $S\neq T$.

It follows from 2.1 that $|S\cap T|$ is not empty. By 2.5 and 2.7 it follows
that $\mathbf{v}$ is not empty and $d_{i}(\mathbf{v})=1$ for $i=1,\dots,m$. By
2.6 $\\{N_{G}(u):u\in C_{m}\\}$ is a partition of $V_{\mathcal{B}_{m}}$. Let
$x_{i}$ be the unique neighbour of $v_{i}$ in $S\cup T$. Note that $C_{m}$ can
be written as the disjoint union of $S\triangle T$, $\\{v_{1},\dots,v_{m}\\}$,
and $\\{x_{1},\dots,x_{m}\\}$ and the degree of any of these vertices is
exactly $\Delta$.

Let $\mathcal{R}=\mathcal{U}\setminus\mathcal{B}_{m}$. It follows from 2.4
that, given an $x\in N_{G}(v_{i})$, $(S,T)$ can be reconfigured to
$(S_{x},T_{x})$ such that $S_{x}$ and $T_{x}$ both contain $x$, still agree on
$\mathcal{R}$, and not only $S$ agrees with $S_{x}$ but also $T$ agrees with
$T_{x}$ on every block in $\mathcal{B}_{m}$ except possibly the block
containing $x$.

For $i=1,\dots,m$ let $X_{i}$ be the block containing $x_{i}$. We claim that
$N_{G}(v_{m})\subseteq X_{m}$. Indeed, suppose that there is some $x\in
N_{G}(v_{m})$ with $x\not\in X_{m}$. Then either
$x\in\operatorname{cl}(S\triangle T)$, which would imply $|S_{x}\triangle
T_{x}|<|S\triangle T|$ contradicting the minimality of $(S,T,\mathbf{v})$
within ${\bf X}(S_{0},T_{0})$. Or $x\in X_{k}$ for some $k<m$. But then
$\mathbf{v}^{\prime}:=(v_{1},\dots,v_{k})$ is an augmenting sequence for
$(S_{x}\cap T_{x},S_{x}\triangle T_{x})$ with $d_{k}(\mathbf{v}^{\prime})=0$
and thus $\mathbf{v}^{\prime}<\mathbf{v}$. This again contradicts minimality.

Next we claim every $x\in N_{G}(v_{m})$ has the same set of neighbours. To see
this, take such an $x$ and observe that $\mathbf{v}$ is an augmenting sequence
for $(S_{x}\cap T_{x},S_{x}\triangle T_{x})$ with $d_{i}(\mathbf{v})=1$ for
all $i$. By 2.6

$\\{N_{G}(u):u\in(S\triangle
T)\cup\\{v_{1},\dots,v_{m}\\}\cup\\{x_{1},\dots,x_{m-1},x\\}\\}$

is a partition of $V_{\mathcal{U}\setminus\mathcal{R}}$. This shows that
$N_{G}(x)$ does not depend on $x$. We conclude that the edge $x_{m}v_{m}$ lies
in a component $K$ of $G$ isomorphic to $K_{\Delta,\Delta}$. We refer to the
sides containing $x_{m}$ and $v_{m}$ as $A$ and $B$ respectively and we recall
that we showed that $A\subseteq X_{m}$.

Let $Y=X_{m}\setminus(A\cup B)$ and let
$\mathcal{G}^{\prime}=(G-K,\mathcal{U}^{\prime})$ be an instance obtained from
swapping $B$ and $X_{m}\setminus A$; see Section 2.1. Recall that there is a
bijection $\mathcal{U}\setminus\\{X_{m}\\}\to\mathcal{U}^{\prime}$ by sending
$W$ to $W^{\prime}$ with $W=W^{\prime}$ if $W\cap B=\emptyset$ and
$W^{\prime}=(W\setminus B)\cup Y(W)$ otherwise. The independent transversals
$(S,T)$ of $\mathcal{G}$ restrict to independent transversals
$(S_{\mathcal{G}^{\prime}},T_{\mathcal{G}^{\prime}})$ of
$\mathcal{G}^{\prime}$. We claim that any irreducible component of
$\mathcal{G}^{\prime}$ contains a block on which $S_{\mathcal{G}^{\prime}}$
and $T_{\mathcal{G}^{\prime}}$ disagree. Observe that for $R\in\mathcal{R}$ we
have $R=R^{\prime}$ and thus, since $\mathcal{G}$ is irreducible, any
irreducible component of $\mathcal{G}^{\prime}$ contains a block in
$\mathcal{U}^{\prime}\setminus\mathcal{R}$. Let $\mathcal{G}^{\prime}_{C}$ be
such a component and assume it does not contain any block on which
$S_{\mathcal{G}^{\prime}}$ and $T_{\mathcal{G}^{\prime}}$ disagree. Since it
must contain a block in $\mathcal{U}^{\prime}\setminus\mathcal{R}$ it must
contain a block $X_{i}^{\prime}$ for some $i\in[m-1]$ and we may assume that
$i$ is chosen minimally. By definition either $v_{i}\in X_{j}$ for $j<i$ or
$v_{i}\in\operatorname{cl}(S\triangle T)$ within $\mathcal{G}$, and since the
edge $v_{i}x_{i}$ is not an edge of $K$ this would imply that either $v_{i}\in
X_{j}^{\prime}$ or
$v_{i}\in\operatorname{cl}(S_{\mathcal{G}^{\prime}}\triangle
T_{\mathcal{G}^{\prime}})$ within $\mathcal{G}^{\prime}$. Since $i$ was chosen
minimally this contradicts the fact that $\mathcal{G}^{\prime}_{C}$ is a
component that does not contain any block on which $S_{\mathcal{G}^{\prime}}$
and $T_{\mathcal{G}^{\prime}}$ disagree, which proves the claim.

Because $G$ is not a disjoint union of $|\mathcal{U}|$ copies of
$K_{\Delta,\Delta}$ there must be a component
$\mathcal{G}_{C}^{\prime}=(G_{C},\mathcal{U}_{C}^{\prime})$ of
$\mathcal{G}^{\prime}$ for which $G_{C}$ is not the disjoint union of
$|\mathcal{U}_{C}^{\prime}|$ copies of $K_{\Delta,\Delta}$. By induction we
can reconfigure $T_{\mathcal{G}^{\prime}}$ to $S_{\mathcal{G}^{\prime}}$ on
this component. This corresponds to a reconfiguration from
$T_{\mathcal{G}^{\prime}}$ to $\tilde{T}_{\mathcal{G}^{\prime}}$ on
$\mathcal{G}^{\prime}$ for which $|T_{\mathcal{G}^{\prime}}\cap
S_{\mathcal{G}^{\prime}}|<|\tilde{T}_{\mathcal{G}^{\prime}}\cap
S_{\mathcal{G}^{\prime}}|$. The independent transversal
$\tilde{T}_{\mathcal{G}^{\prime}}$ agrees with either
$S_{\mathcal{G}^{\prime}}$ or $T_{\mathcal{G}^{\prime}}$ on every block of
$\mathcal{G}^{\prime}$ and thus it does not intersect $Y$. By 2.2 it follows
that $T$ can be reconfigured to $\tilde{T}$ within $\mathcal{G}$ that agrees
with $S$ on $X_{m}$ and on every block in
$U\in\mathcal{U}\setminus\\{X_{m}\\}$ for which $S_{\mathcal{G}^{\prime}}$ and
$\tilde{T}_{\mathcal{G}^{\prime}}$ agree on $U^{\prime}$. It follows that

$|S\cap\tilde{T}|=|S_{\mathcal{G}^{\prime}}\cap\tilde{T}_{\mathcal{G}^{\prime}}|+1>|S_{\mathcal{G}^{\prime}}\cap
T_{\mathcal{G}^{\prime}}|+1=|S\cap T|.$

This contradicts the assumption that the pair $S,T$ was reconfigured to agree
on a maximal number of blocks. ∎

##  3 Concluding remarks

Our contribution in this work was to conceive of and establish Theorem 1.2,
which one may view as a qualitative strengthening, or a reconfiguration-
analogue, of Haxell’s theorem. From this result there open up numerous
intriguing lines for further research, which we briefly outline.

  * •

Since the class of graphs formed from the disjoint union of copies of
$K_{\Delta,\Delta}$ seems eminently tractable, Theorem 1.2 hints temptingly at
the feasibility of the following problem. What is an exact characterisation
(for part size $t=2\Delta$) of those irreducible vertex-partitioned
$\Delta$-regular graphs for which the reconfigurability graph of independent
transversals is disconnected?

  * •

What are the best upper bounds, as a function of $|\mathcal{U}|$ and $\Delta$
on the diameter of the reconfigurability graph of $\mathcal{G}$ in the
conclusion of Theorem 1.2? Similarly, what are the best diameter upper bounds
for the reconfigurability graph under the assumption that $|\mathcal{U}|$ is
$(2\Delta+1)$-thick?

  * •

We presented a Markov chain, which by Theorem 1.2 settles into an equilibrium
distribution over all admissible configurations. When does it mix rapidly,
that is, polynomially fast as a function of $|V(H)|$? Could it be shown
provided $t$ is large enough in comparison to $\Delta$, say, some constant
factor $C\geq 2$ larger? Put another way, is there some independent
transversals analogue of Jerrum’s result on Glauber dynamics for proper
colourings of bounded degree graphs [Jer95]?

We referred in passing to the fact that independent transversals nontrivially
generalise proper colourings of graphs. There are interesting notions
intermediate to proper colourings and independent transversals, where one
could also pursue a study analogous to ours. In fact, Theorem 1.2 validates
all such studies. We highlight two such (related) notions, especially as they
may demand techniques different from those we used here.

  * •

Let $H$ be a graph. Suppose that to each vertex $u\in V(H)$ we associate a
list $L(u)\subseteq\mathbb{Z}^{+}$ of $t$ positive integers. Let us
furthermore restrict ourselves to such $L$ satisfying for each $u$ and each
$c\in L(u)$ that $|\\{v\in N_{H}(u)\,\mid\,L(v)\ni c\\}|\leq\Delta$, that is,
the maximum colour-degree is bounded by $\Delta$. A proper $L$-colouring of
$H$ is a function $f:V(H)\to\mathbb{Z}^{+}$ that makes a choice $f(u)\in L(u)$
for each $u$ from its own list so that $f(u)\neq f(v)$ for any edge $uv\in
V(H)$. Reed and Sudakov [RS02] showed that some $t$ satisfying
$t=\Delta+o(\Delta)$ as $\Delta\to\infty$ suffices to always guarantee a
proper $L$-colouring under the above setup, while Bohman and Holzman [BH02]
showed that $t=\Delta+1$ does not suffice. What is the best choice of
$t=t(\Delta)$ that guarantees connectedness in the space of proper
$L$-colourings (changing the choice for one vertex of $H$ at a time) under
this setup?

  * •

Given a graph $G$, we say that a partition $\mathcal{U}$ of $V(G)$ has maximum
local degree $s$ if the maximum degree of any subgraph induced by two of the
parts is at most $s$. Loh and Sudakov [LS07] showed that provided
$s=s(\Delta)$ satisfies $s=o(\Delta)$ as $\Delta\to\infty$, there is some
choice of $t=t(\Delta)$ satisfying $t=\Delta+o(\Delta)$ as $\Delta\to\infty$
such that the following holds. For any graph $G$ of maximum degree $\Delta$,
and any $t$-thick partition $\mathcal{U}$ of maximum local degree $s$, there
is guaranteed to be an independent transversal of $(G,\mathcal{U})$. Note this
generalises the aforementioned result of Reed and Sudakov, as that could be
cast in terms of independent transversals under the condition of maximum local
degree $1$. As before, what is the best choice of $t=t(\Delta)$ that
guarantees connectedness in the space of independent transversals under this
setup?

For each of these, Theorem 1.2 shows that we can choose $t\leq 2\Delta$, but
is there some $1<c<2$ for which we can always choose $t\leq c\Delta$ for all
sufficiently large $\Delta$? Could it be any such $c$? And similarly, for
each, one might separately investigate bounds on the threshold for rapid
mixing (should one exist).

To cap things off, let’s remind the reader of our first sentence in the paper.
Theorem 1.2 and the methods for proving it suggest the following
supersaturation-type strengthening of Haxell’s theorem.

######  Conjecture 3.1.

Let $G$ be a graph with maximum degree $\Delta$ and let $\mathcal{U}$ be a
$(2\Delta)$-thick partition of $V(G)$. The number of independent transversals
of $(G,\mathcal{U})$ is minimised when $G$ is a disjoint union of
$|\mathcal{U}|$ copies of $K_{\Delta,\Delta}$.

More specifically, it could be that the hypothesis of 2.1 characterises the
extremal structure, and so it would suffice to show that the number of
independent transversals must be at least $2\Delta^{|\mathcal{U}|}$.

#### Acknowledgements.

This project began during a visit by the authors in the summer of 2023 to the
Department of Mathematics, Hokkaido University. We are grateful to Akira Sakai
for hosting that visit. PB was supported by the Dutch Research Council (NWO)
grant OCENW.M20.009. RJK was partially supported by the Gravitation Programme
NETWORKS (024.002.003) of NWO.

#### Open access statement.

For the purpose of open access, a CC BY public copyright license is applied to
any Author Accepted Manuscript (AAM) arising from this submission.

## References

  * [AHHS15] Ron Aharoni, Ron Holzman, David Howard, and Philipp Sprüssel.  Cooperative colorings and independent systems of representatives.  Electron. J. Combin., 22(2):Paper 2.27, 14, 2015.  doi:10.37236/2488.
  * [BES75] B. Bollobás, P. Erdős, and E. Szemerédi.  On complete subgraphs of $r$-chromatic graphs.  Discrete Math., 13(2):97–107, 1975.  doi:10.1016/0012-365X(75)90011-4.
  * [BH02] Tom Bohman and Ron Holzman.  On a list coloring conjecture of Reed.  J. Graph Theory, 41(2):106–109, 2002.  doi:10.1002/jgt.10054.
  * [Erd55] Paul Erdös.  Some theorems on graphs.  Riveon Lematematika, 9:13–17, 1955.
  * [Erd72] Paul Erdös.  Problem 2.  In Combinatorics, pages 353–354. The Institute of Mathematics and its Applications, 1972.
  * [GH20] Alessandra Graf and Penny Haxell.  Finding independent transversals efficiently.  Combin. Probab. Comput., 29(5):780–806, 2020.  doi:10.1017/s0963548320000127.
  * [Hax95] P. E. Haxell.  A condition for matchability in hypergraphs.  Graphs and Combinatorics, 11(3):245–248, 1995.  doi:10.1007/BF01793010.
  * [Hax01] P. E. Haxell.  A note on vertex list colouring.  Combinatorics, Probability and Computing, 10(4):345–347, 2001\.  doi:10.1017/S0963548301004758.
  * [Jer95] Mark Jerrum.  A very simple algorithm for estimating the number of $k$-colorings of a low-degree graph.  Random Structures Algorithms, 7(2):157–165, 1995.  doi:10.1002/rsa.3240070205.
  * [LS07] Po-Shen Loh and Benny Sudakov.  Independent transversals in locally sparse graphs.  J. Combin. Theory Ser. B, 97(6):904–918, 2007.  doi:10.1016/j.jctb.2007.02.003.
  * [RS02] Bruce Reed and Benny Sudakov.  Asymptotically the list colouring constants are 1.  J. Combin. Theory Ser. B, 86(1):27–37, 2002.  doi:10.1006/jctb.2002.2110.
  * [ST06] Tibor Szabó and Gábor Tardos.  Extremal problems for transversals in graphs with bounded degree.  Combinatorica, 26(3):333–351, 2006.  doi:10.1007/s00493-006-0019-9.
  * [vdH13] Jan van den Heuvel.  The complexity of change.  In Surveys in combinatorics 2013, volume 409 of London Math. Soc. Lecture Note Ser., pages 127–160. Cambridge Univ. Press, Cambridge, 2013.