betaFeedback

WorksMathematics

Supersaturation and reconfiguration diameter of independent transversals

Abstract

Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree ΔΔ. It is a classic result that when all parts have size at least 2Δ2Δ, the collection is nonempty. Recently, it was found that if the parts have size at least 2Δ+12Δ+1, then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least 2Δ2Δ, and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least 4Δ4Δ.

Introduction

Given an integer Δ≥3\Delta\ge3, let GG be a graph of maximum degree at most Δ\Delta. Consider an arbitrary vertex-partition P={P1,…,Pn}\mathcal{P} = \{P_1, \ldots, P_n\} for GG. An independent transversal of (G,P)(G,\mathcal{P}) is an independent set of GG containing exactly one vertex from each part. This is guaranteed to exist, by a result of Haxell [18], if all parts of P\mathcal{P} have size at least 2Δ2\Delta. The size-constraint 2Δ2\Delta is precisely optimal, in that there are examples of (G,P)(G,\mathcal{P}) where the parts are only of size 2Δ−12\Delta- 1 for which there is no independent transversal [24] (see also [16]).

Consider the collection of all independent transversals of (G,P)(G,\mathcal{P}). How does this collection change as we increase the size-constraint beyond 2Δ2\Delta?

  1. Can we guarantee it has a certain cardinality, as a function of natural parameters in (G,P)(G,\mathcal{P})?

  1. What about changes in the collection’s qualitative structure, such as its topology or geometry?

The result of [18] guarantees only that the cardinality in Question 1 is at least 1 for any size-constraint at least 2Δ2\Delta, and so Question 1 constitutes a natural ‘supersaturation’ refinement. To make Question 2 precise, we study the (independent transversal) reconfiguration graph of (G,P)(G,\mathcal{P}), which is the graph whose vertices are the independent transversals of (G,P)(G,\mathcal{P}) and whose edges join two transversals that differ in exactly one part. Under what circumstances is the reconfiguration graph connected, and how small is its diameter? These kinds of questions are relevant for applications to sampling and counting algorithms via Markov chains (see, e.g., [20]).

Buys, Kang, and Ozeki [6] used combinatorial methods to prove that the reconfiguration graph of (G,P)(G,\mathcal{P}) is connected when every part has size at least 2Δ+12\Delta+ 1. Wdowinski reproved this result within a framework of topological methods [27], analogous to those that were used to prove Haxell’s existence theorem (e.g., [1, 3, 23]). If every part has size exactly 2Δ2\Delta, connectivity can fail only if some parts P′⊆P\mathcal{P}' \subseteq\mathcal{P} induce ∣P′∣|\mathcal{P}'| disjoint copies of KΔ,ΔK_{\Delta,\Delta} in GG. Wdowinski [28], resolving a question in [6], exactly characterized which partitions may occur in the exceptional instances. These results give a sharp qualitative picture for connectivity around Haxell’s threshold, while leaving quantitative diameter and supersaturation questions open.

Diameters of reconfiguration graphs

One of our main results provides a linear upper bound on the diameter under the stronger assumption that the parts have size ∣Pi∣≥4Δ|P_i| \ge4\Delta. The diameter bound 2n−12n - 1 is sharp due to examples coming from correspondence-colouring reconfiguration [7 Proposition 2(ii)].

Theorem 1. Let GG be a graph of maximum degree Δ\Delta, and let P={P1,…,Pn}\mathcal{P} = \{P_1,\ldots,P_n\} be a partition of V(G)V(G) such that ∣Pi∣≥4Δ|P_i| \ge4\Delta for every i∈[n]i \in[n]. Then the reconfiguration graph of independent transversals of (G,P)(G,\mathcal{P}) has diameter at most 2n−12n - 1.

Related diameter questions have been studied before for list colourings, which can be viewed as independent transversals of an auxiliary vertex-partitioned graph, and hence constitute a special case (see [19]). In that setting, a list colouring is already guaranteed to exist when parts have size Δ+1\Delta+ 1, and the associated reconfiguration graph is connected when the parts have size at least Δ+2\Delta+ 2. At that same threshold of parts of size Δ+2\Delta+ 2, Jerrum [20] gave an argument that yields a 2O(n)2^{O(n)} upper bound on the diameter of the reconfiguration graph, Cereceda [10] improved it to O(n2)O(n^2), and finally Cambie, Cames van Batenburg, and Cranston [7] showed that the diameter is at most 2n−12n-1. See [9, 11] for a generalization to hypergraphs and refinements of this sharp bound.

For general independent transversals, this raises the question of whether the 2n−12n - 1 bound in Theorem 1 might still hold close to the 2Δ2\Delta connectivity threshold. We show that this is the case asymptotically if the average degree of the vertices in each block is o(Δ)o(\Delta) (see Corollary 8), but this still leaves open the general case. Is the diameter still at most 2n−12n - 1, or at least linear in nn, under the weaker condition that all parts have size at least 2Δ+12\Delta+ 1? And when the parts have size ≥2Δ\ge2\Delta, does every connected component have diameter O(n)O(n)? So far, the best result we know [14] is that when parts have size at least 2Δ+12\Delta+ 1, the diameter is polynomial in nn for every fixed Δ\Delta, but the dependence on Δ\Delta in the exponent is huge. In this current work, we show that linear diameter fails below the connectivity threshold, and that connected components can have at least quadratic diameter.

Theorem 2. For every Δ≥3\Delta\ge3 there are infinitely many nn for which there exists a graph GG of maximum degree at most Δ\Delta, together with a partition P\mathcal{P} of $V(G) into nn parts each of size $2\Delta - 1$, such that the reconfiguration graph of independent transversals of (G,P)(G,\mathcal{P}) has a connected component of diameter at least n24Δ2\frac{n^2}{4\Delta^2}.

Our construction simulates the 3-colouring reconfiguration graph of a path (from [5]) inside the independent transversal reconfiguration graph.

Number of independent transversals

In the direction of counting independent transversals, our next main result is that there exist exponentially many independent transversals when the parts have size ∣Pi∣≥2Δ|P_i| \ge2\Delta, where the exponential dependence is in the number of parts nn.

Theorem 3. Let GG be a graph of maximum degree Δ\Delta, and let P={P1,…,Pn}\mathcal{P} = \{P_1,\ldots,P_n\} be a partition of V(G)V(G) such that ∣Pi∣≥2Δ|P_i| \ge2\Delta. Then the number of independent transversals of (G,P)(G,\mathcal{P}) is at least

(2Δ)(1−12Δ−1)n2.(2\Delta)^{\left(1-\frac{1}{2\Delta-1}\right)\frac{n}{2}}.

Our proof is an interesting application of Lindsey’s edge-isoperimetric inequality [22] on the Hamming graph. Our theorem appears to be the first result demonstrating exponentially many independent transversals at the threshold 2Δ2\Delta that works for all values of nn and Δ\Delta.

Exponential lower bounds on the number of independent transversals have previously been obtained through the Lovász Local Lemma and variations of it, but they require larger part sizes. For example, Wanless and Wood [26] proved the existence of at least (t/2)n(t/2)^n independent transversals when ∣Pi∣=t≥4Δ|P_i| = t \ge4\Delta for all ii. This was actually shown with the maximum degree Δ\Delta replaced by the maximum block average degree DD of (G,P)(G,\mathcal{P}), which is defined as the maximum over all parts PiP_i of the average degree of the vertices in PiP_i. In this average degree setting, the part size threshold 4D4D was shown to be best possible even for the existence of a single independent transversal [13, 17]. And while it is suggestive based on Theorem 1 that the reconfiguration graph of (G,P)(G,\mathcal{P}) ought to be connected when ∣Pi∣≥4D|P_i| \ge4D, that hunch fails spectacularly: It is not hard to construct examples with two parts P1,P2P_1, P_2 of arbitrarily large size and D<2D < 2 such that the independent transversal reconfiguration graph is disconnected.

Another exponential-type lower bound is due to Tang and Zhao [25]. Their main result implies that if ∣Pi∣≥2Δ|P_i| \ge2\Delta for all ii, then the number of independent transversals is at least cnΔnc_n\Delta^n, where cn>0c_n > 0 depends only on nn. However, they require that Δ\Delta be sufficiently large compared to nn. We are more interested in the situation when Δ\Delta is fixed and nn is growing. Buys, Kang, and Ozeki [6] posed the following conjecture giving a sharp lower bound on the number of independent transversals at Haxell’s theshold 2Δ2\Delta. This would be tight by a simple construction (see Example 17).

Conjecture 4. Let GG be a graph with maximum degree Δ\Delta, and let P={P1,…,Pn}\mathcal{P} = \{P_1,\ldots,P_n\} be a partition of V(G)V(G) with ∣Pi∣=2Δ|P_i| = 2\Delta for all ii. Then the number of independent transversals of (G,P)(G,\mathcal{P}) is at least 2Δn2\Delta^n.

For comparison, the total number of (not necessarily independent) transversals of P\mathcal{P} is (2Δ)n(2\Delta)^n. Our last main result is proving the first non-trivial case of Conjecture 4, namely when $n = 3 ({xref}Theorem 19). Interestingly, while there are various tight constructions for {xref}Conjecture 4 when $n \in \{1,2\}$, we show that the mentioned tight construction ({xref}Example 17`) is unique when n=3n = 3, and we conjecture that this is the case for all n≥3n \ge3.

Organization

This paper is organized as follows. In Section 2, we prove Theorem 1 on linear diameter. In § 3, we prove Theorem 2 on quadratic diameter components. In § 4, we prove Theorem 3 as well as a more elementary result coming from double-counting. In § 5, we prove Conjecture 4 when n≤3n \le3.

Linear diameter when parts have size ≥4Δ\ge4\Delta

In this section, we prove Theorem 1 demonstrating that the reconfiguration graph of (G,P)(G,\mathcal{P}) has linear diameter when the parts of P\mathcal{P} have size at least 4Δ4\Delta. Before that, let us recall Haxell’s Theorem [18, 19].

Theorem 5 (Haxell [18, 19]). Let GG be a graph of maximum degree at most Δ\Delta with a vertex partition P={P1,…,Pn}\mathcal{P} = \{P_1, \ldots, P_n\}. If ∣Pi∣≥2Δ|P_i| \ge2\Delta for every ii, then (G,P)(G,\mathcal{P}) has an independent transversal. In fact, every vertex is contained in some independent transversal.

Theorem 1 will be a direct corollary of Theorem 5 and the following theorem, which more generally provides a linear upper bound on the diameter under the condition that the existence of an independent transversal is sufficiently robust under vertex removal.

Theorem 6. Let GG be a graph with maximum degree at most Δ\Delta and let P={P1,…,Pn}\mathcal{P} = \{P_1, \ldots, P_n\} be a partition of V(G)V(G) into nn parts. Suppose that whenever one removes at most 2Δ2\Delta vertices from each part of P\mathcal{P}, the resulting induced subgraph G′G' and vertex partition P′\mathcal{P}' has an independent transversal. Then the reconfiguration graph of independent transversals of (G,P)(G,\mathcal{P}) has diameter at most 2n−12n - 1.

Proof. Let A={a1,…,an}A = \{a_1, \ldots, a_n\} and B={b1,…,bn}B = \{b_1, \ldots, b_n\} be two independent transversals of (G,P)(G,\mathcal{P}). We will show that dist⁡(A,B)≤2n−1\operatorname{dist}(A, B) \le2n - 1. Essentially, the proof proceeds by finding some suitable independent transversal CC such that both AA and BB can be reconfigured to CC in at most nn steps. We construct an ordering ρ\rho of the parts PiP_i, together with large subsets Ri⊆PiR_i \subseteq P_i, with the ordering ρ\rho chosen so that every vertex of RiR_i avoids all vertices aja_j and bjb_j appearing later than ii in the order ρ\rho. We construct ρ\rho greedily.

Suppose that U⊆[n]U \subseteq[n] is the set of indices of parts that are not yet ordered. For i∈Ui \in U, define

Block⁡i(U):=Pi∩N({aj∪bj:j∈U∖{i}}).\operatorname{Block}_i(U) := P_i \cap N\left(\{a_j \cup b_j : j \in U \setminus\{i\}\}\right).

Thus Block⁡i(U)\operatorname{Block}_i(U) is the set of vertices in PiP_i blocked by the still-unordered vertices of AA and BB. Since

∑i∈U∣Block⁡i(U)∣≤∑j∈Udeg⁡(aj)+deg⁡(bj)≤∣U∣⋅2Δ,\sum_{i \in U} |\operatorname{Block}_i(U)| \le\sum_{j \in U} \deg(a_j) + \deg(b_j) \le|U| \cdot2\Delta,

some i∈Ui \in U satisfies

∣Block⁡i(U)∣≤2Δ.|\operatorname{Block}_i(U)| \le2\Delta.

Put this part PiP_i next in the order ρ\rho, and define Ri:=Pi∖Block⁡i(U)R_i := P_i \setminus\operatorname{Block}_i(U). Then

∣Ri∣≥∣Pi∣−2Δ.|R_i| \ge|P_i| - 2\Delta.

It follows from the hypothesis of Theorem 6 that the graph induced by ⋃i=1nRi\bigcup_{i=1}^{n} R_i has an independent transversal C={ci:ci∈Ri}C = \{c_i : c_i \in R_i\}. Moreover, by construction, every vertex of RiR_i is nonadjacent to every aja_j and bjb_j whose part appears after PiP_i in the order ρ\rho.

We now show that AA can be reconfigured to CC in at most nn steps. We reconfigure the parts in the order ρ\rho. Suppose we are reconfiguring the part PiP_i. At this moment, the parts earlier than PiP_i in ρ\rho have already been changed to their vertices of CC, while the parts later than PiP_i in ρ\rho are still at their vertices of AA. We now reconfigure aia_i to cic_i. This is allowed because:

  • cic_i is nonadjacent to all earlier vertices of CC, since CC is independent; and

  • cic_i is nonadjacent to all later vertices aja_j of AA, since ci∈Ric_i \in R_i.

By the same argument, the transversal BB can be reconfigured to CC in at most nn steps according to the same order ρ\rho. This already gives that dist⁡(A,B)≤dist⁡(A,C)+dist⁡(B,C)≤n+n=2n\operatorname{dist}(A,B) \le\operatorname{dist}(A,C) + \operatorname{dist}(B,C) \le n+n=2n. However, we can do slightly better. Let r∈{1,…,n}r \in\{1,\ldots,n\} be the index whose part PrP_r comes last in the order ρ\rho. As above we reconfigure aia_i and bib_i to cic_i according to order ρ\rho, except we do not yet execute the last reconfiguration, from ara_r to crc_r and from brb_r to crc_r. Instead we can then finish by directly reconfiguring ara_r to brb_r, saving one reconfiguration step. □

As another application of Theorem 6, we prove Corollary 8 below, showing that we have linear diameter whenever the parts have size (2+o(1))Δ(2+o(1))\Delta, under the additional assumption that the maximum block average degree DD of (G,P)(G,\mathcal{P}) is o(Δ)o(\Delta). Recall that the maximum block average degree of (G,P)(G,\mathcal{P}) is defined as D:=max⁡Pi∈P1∣Pi∣∑v∈PidG(v)D:=\max_{P_i\in\mathcal{P}}\frac{1}{|P_i|}\sum_{v\in P_i}d_G(v). In place of Haxell’s Theorem 5, we use the following theorem that comes from variations of the Lovász Local Lemma [21, 26] (see also [4]).

Theorem 7 (Kang, Kelly [21]; Wanless, Wood [26]). Let GG be a graph and let P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} be a vertex partition. If (G,P)(G,\mathcal{P}) has maximum block average degree DD and ∣Pi∣≥4D|P_i|\ge4D for every ii, then (G,P)(G,\mathcal{P}) has an independent transversal.

Corollary 8. Let GG be a graph of maximum degree Δ\Delta and maximum block average degree DD, together with a vertex partition P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} such that ∣Pi∣≥2Δ+6DΔ|P_i|\ge2\Delta+6\sqrt{D\Delta} for every i∈[n]i\in[n]. Then the reconfiguration graph of independent transversals of (G,P)(G,\mathcal{P}) has diameter at most 2n−12n-1.

Proof. We verify the hypothesis of Theorem 6. Let G′G' be obtained from GG by deleting at most 2Δ2\Delta vertices from each part, and put Pi′:=Pi∩V(G′)P'_i:=P_i\cap V(G') for every ii. Then ∣Pi′∣≥6DΔ|P'_i|\ge6\sqrt{D\Delta}. Let D′D' be the maximum block average degree of (G′,{P1′,…,Pn′})(G',\{P'_1,\ldots,P'_n\}), say that the average degree is maximised at Pj′P'_j. Since D≤ΔD\le\Delta, we have

D′=1∣Pj′∣∑v∈Pj′dG′(v)≤1∣Pj′∣∑v∈PjdG(v)≤∣Pj∣D∣Pj∣−2Δ≤(2Δ+6DΔ)D6DΔ≤43DΔ.D'=\frac{1}{|P'_j|}\sum_{v\in P'_j}d_{G'}(v)\le\frac{1}{|P'_j|}\sum_{v\in P_j}d_G(v)\le\frac{|P_j|D}{|P_j|-2\Delta}\le\frac{(2\Delta+6\sqrt{D\Delta})D}{6\sqrt{D\Delta}}\le\frac{4}{3}\sqrt{D\Delta}.

Hence 4D′<6DΔ≤∣Pi′∣4D'<6\sqrt{D\Delta}\le|P'_i| for every ii. By Theorem 7, it follows that (G′,{P1′,…,Pn′})(G',\{P'_1,\ldots,P'_n\}) has an independent transversal. Therefore, Theorem 6 applies to give the diameter result. □

Remark 9. Due to the construction in [7 Proposition 2(ii)], for every Δ=n−1\Delta=n-1 and p≥3p\ge3 there exist examples of graphs GG with maximum degree Δ\Delta and a partition P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} where ∣Pi∣≥p|P_i|\ge p for all ii and the reconfiguration graph of (G,P)(G,\mathcal{P}) has diameter at least 2n−12n-1. Thus the upper bound 2n−12n-1 in Theorem 1 is sharp for all values of Δ\Delta.

Remark 10. If the parts have size k≥2Δ+1k \ge2\Delta+ 1, then there exists at least one “unfrozen” part. More precisely: Suppose P={P1,…,Pn}\mathcal{P} = \{P_1, \ldots, P_n\} and ∣Pi∣=k|P_i| = k for all ii. Given independent transversals AA and BB, say that PiP_i is (A,B)(A, B)-unfrozen if some y∈Piy \in P_i satisfies y≁A∖{ai}y \not\sim A \setminus\{a_i\} and y≁B∖{bi}y \not\sim B \setminus\{b_i\}. Suppose for a contradiction that no such yy exists for any ii. Then with eA(i)=e(A∖{ai},Pi)e_A(i) = e(A \setminus\{a_i\}, P_i) and eB(i)=e(B∖{bi},Pi)e_B(i) = e(B \setminus\{b_i\}, P_i), we have eA(i)+eB(i)≥ke_A(i) + e_B(i) \ge k for all ii. Since ∑ieA(i)≤nΔ\sum_i e_A(i) \le n\Delta and ∑ieB(i)≤nΔ\sum_i e_B(i) \le n\Delta, it follows that kn≤2nΔkn \le2n\Delta, contradiction. So there must exist some (A,B)(A, B)-unfrozen part PiP_i. This could be a somewhat desirable property for a potential proof by induction, because it means that aia_i can be reconfigured to yy without being blocked by either AA or BB.

Quadratic diameter components when parts have size ≤2Δ−1\le2\Delta- 1

In this section, we prove Theorem 2. When the parts of a partition have size less than 2Δ2\Delta, there might not be an independent transversal, and if there does exist one, the reconfiguration graph may not be connected. However, here we zoom in on the situation that the reconfiguration graph is nonempty, and we ask how large the maximum diameter among all connected components can be. We show that it can be at least n24Δ2\frac{n^2}{4\Delta^2}. We use the following result as input.

Theorem 11 (Bonamy, Johnson, Lignos, Patel, Paulusma [5]). For every s≥2s \ge2, the 3-colouring reconfiguration graph of the ss-vertex path PsP_s has diameter at least s2−14\frac{s^2-1}{4}.

The idea of the construction of (G,P)(G,\mathcal{P}) in the proof of Theorem 2 is to “simulate” the 3-colour reconfiguration graph C3(Ps)C_3(P_s) of an ss-vertex path on ss vertices, by forcing it to occur as an induced subgraph of the reconfiguration graph of (G,P)(G,\mathcal{P}). This is inspired by [8 Lemma 17], where a very different simulation of C3(Ps)C_3(P_s) was used for list-colouring reconfiguration. The construction is illustrated in Figure 1.

Illustration of the construction with main parts, auxiliary parts, dummy sets, and path edges

Figure 1. Illustration of the construction in Theorem 2. The big blue boxes depict the main parts MiM_i; they contain Δ−2\Delta- 2 dummy sets of size 2, as well as a triple of three vertices that represent the three possible colours of the ii-th vertex of the path PsP_s. The green boxes depict the auxiliary parts Ai,jA_{i,j}, split into XX, YY, and ZZ sets. The thick edges indicate a complete bipartite graph. The thin edges depict the path edges, which can be viewed as the edges between equal colours of adjacent vertices of PsP_s.

Proof of Theorem 2. Put t:=Δ−2t := \Delta- 2 and let ss be a positive integer. Partition P\mathcal{P} will have n:=s(Δ−1)n := s(\Delta- 1) parts.

We first build ss main parts M1,…,MsM_1, \ldots, M_s. Each main part MiM_i consists of a core set Micore:={pi1,pi2,pi3}M_i^{\mathrm{core}} := \{p_i^1, p_i^2, p_i^3\} and tt dummy sets Di,jD_{i,j}, j∈[t]j \in[t], each of size 2. Thus ∣Mi∣=3+2t=2Δ−1|M_i| = 3 + 2t = 2\Delta- 1.

For each dummy set Di,jD_{i,j}, we introduce an auxiliary part Ai,jA_{i,j}. This part is split into three sets

Ai,j:=Xi,j∪Yi,j∪Zi,j,A_{i,j} := X_{i,j} \cup Y_{i,j} \cup Z_{i,j},

where ∣Xi,j∣=Δ|X_{i,j}| = \Delta, ∣Yi,j∣=1|Y_{i,j}| = 1, and ∣Zi,j∣=Δ−2|Z_{i,j}| = \Delta- 2. Hence every auxiliary part also has size 2Δ−12\Delta- 1. The partition is

P:={Mi:i∈[s]}∪{Ai,j:i∈[s], j∈[t]}.\mathcal{P} := \{M_i : i \in[s]\} \cup\{A_{i,j} : i \in[s],\ j \in[t]\}.

We now define the edges. First, between consecutive main parts, add the path edges picpi+1cp_i^c p_{i+1}^c for every i∈[s−1]i \in[s - 1] and c∈{1,2,3}c \in\{1,2,3\}. Second, make Xi,jX_{i,j} complete to Di,jD_{i,j}, for every i,ji,j. Third, make Yi,jY_{i,j} complete to MicoreM_i^{\mathrm{core}}, for every i,ji,j. Finally, cyclically order all pairs (i,j)(i,j), and for every (i,j)(i,j), make Zi,jZ_{i,j} complete to Xsucc⁡(i,j)X_{\operatorname{succ}(i,j)}, where succ⁡(i,j)≠(i,j)\operatorname{succ}(i,j) \ne(i,j) is the successor of (i,j)(i,j) in this cyclic order. (We note in passing that it is not essential to do this via a cyclic order; the only important thing is that each Zi,jZ_{i,j} is made complete to some unique Xp,qX_{p,q} with (i,j)≠(p,q)(i,j) \ne(p,q).) There are no other edges.

We first check the maximum degree. A vertex in MicoreM_i^{\mathrm{core}} has at most two path-neighbours and is adjacent to the unique vertex of Yi,jY_{i,j} for each j∈[t]j \in[t], so its degree is at most 2+t=Δ2 + t = \Delta. A vertex in Xi,jX_{i,j} is adjacent to the two vertices of Di,jD_{i,j} and to the Δ−2\Delta- 2 vertices of the unique ZZ-set made complete to Xi,jX_{i,j}, so its degree is exactly Δ\Delta. The unique vertex of Yi,jY_{i,j} has degree 3, and every vertex in a dummy set Di,jD_{i,j} or Zi,jZ_{i,j} has degree exactly Δ\Delta. Hence Δ(G)≤Δ\Delta(\mathcal{G}) \le\Delta.

Call an independent transversal core if it chooses a vertex from MicoreM_i^{\mathrm{core}} in every main part MiM_i, and a vertex from Xi,jX_{i,j} in every auxiliary part Ai,jA_{i,j}. The crucial claim is that every core transversal can only be reconfigured to another core transversal. Indeed, in a core transversal, each vertex of Di,jD_{i,j} is blocked by the selected vertex of Xi,jX_{i,j}. The unique vertex of Yi,jY_{i,j} is blocked by the selected vertex of MicoreM_i^{\mathrm{core}}. Finally, every vertex of Zi,jZ_{i,j} is blocked by the selected vertex of Xsucc⁡(i,j)X_{\operatorname{succ}(i,j)}. Therefore the core transversals form a closed union of connected components.

Inside the core transversals, the choices in the main parts M1,…,MsM_1,\ldots,M_s are exactly proper 3-colourings of a path on ss vertices: choosing picp_i^c corresponds to giving colour cc to the ii-th path vertex, and the edges picpi+1cp_i^c p_{i+1}^c forbid equal colours on consecutive path vertices. The auxiliary parts impose no further restrictions on these path choices, because there is no edge between the cores ⋃iMicore\bigcup_i M_i^{\mathrm{core}} of the main parts and the cores ⋃i,jXi,j\bigcup_{i,j} X_{i,j} of the auxiliary parts.

It follows that the reconfiguration graph G\mathcal{G} of (G,P)(G,\mathcal{P}) contains a copy H\mathcal{H} of the 3-colour reconfiguration graph of the path PsP_s as an induced subgraph, and moreover any shortest path between two vertices of H\mathcal{H} is also a shortest path in G\mathcal{G}. In particular, the diameter of the connected component of G\mathcal{G} containing H\mathcal{H} is at least the diameter of H\mathcal{H}. By Theorem 11, H\mathcal{H} has diameter ≥s2−14\ge\frac{s^2-1}{4}. Plugging in s=n/(Δ−1)s=n/(\Delta-1) yields the result. □

Exponentially many independent transversals

In this section, we prove Theorem 3, demonstrating the existence of exponentially many independent transversals when parts have size 2Δ2\Delta. We prove it in a more general form involving arbitrary part sizes t≥2Δt \ge2\Delta (see Theorem 15).

For a graph GG and vertex partition P\mathcal{P}, the number of independent transversals of (G,P)(G,\mathcal{P}) is denoted by N(G,P)N(G,\mathcal{P}).

Double counting argument

Before proving Theorem 3, in this subsection we give an elementary double-counting argument demonstrating exponentially many independent transversals when parts have size 2Δ+12\Delta+ 1. This is an adaptation of a folklore proof for showing the existence of exponentially many (list) colourings of graphs.

Proposition 12. Let GG be a graph of maximum degree Δ\Delta, and let P={P1,…,Pn}\mathcal{P} = \{P_1,\ldots,P_n\} be a partition of V(G)V(G) with ∣Pi∣≥2Δ|P_i| \ge2\Delta for all ii. Then

N(G,P)≥2Δ∏i=1n∣Pi∣2Δ.N(G,\mathcal{P}) \ge2\Delta\prod_{i=1}^{n} \frac{|P_i|}{2\Delta}.

In particular, if ∣Pi∣≥2Δ+1|P_i| \ge2\Delta+ 1 for every ii, then

N(G,P)≥2Δ(1+12Δ)n.N(G,\mathcal{P}) \ge2\Delta\left(1+\frac{1}{2\Delta}\right)^n.

Proof. For each ii, choose a subset Qi⊆PiQ_i \subseteq P_i with ∣Qi∣=2Δ|Q_i| = 2\Delta. Write Q={Q1,…,Qn}\mathcal{Q} = \{Q_1,\ldots,Q_n\}. The induced subgraph G[Q1∪⋯∪Qn]G[Q_1 \cup\cdots\cup Q_n] has maximum degree at most Δ\Delta, and its vertex set is partitioned into Q\mathcal{Q}. By Haxell’s theorem, every such choice of Q\mathcal{Q} has at least 2Δ2\Delta independent transversals. Let X\mathcal{X} be the set of pairs (Q,A)(\mathcal{Q}, A) where Q={Q1,…,Qn}\mathcal{Q} = \{Q_1,\ldots,Q_n\} with Qi⊆PiQ_i \subseteq P_i and ∣Qi∣=2Δ|Q_i| = 2\Delta for every ii, and where AA is an independent transversal of Q\mathcal{Q}. We will double count ∣X∣|\mathcal{X}|.

First count X\mathcal{X} by starting from a fixed choice of Q\mathcal{Q}. There are ∏i=1n(∣Pi∣2Δ)\prod_{i=1}^{n} \binom{|P_i|}{2\Delta} choices for Q\mathcal{Q}, each of which has at least 2Δ2\Delta independent transversals, so ∣X∣≥2Δ∏i=1n(∣Pi∣2Δ)|\mathcal{X}| \ge2\Delta\prod_{i=1}^{n} \binom{|P_i|}{2\Delta}.

Now count X\mathcal{X} by starting from some fixed choice of independent transversal AA of P\mathcal{P}. For AA to be an independent transversal of {Q1,…,Qn}\{Q_1,\ldots,Q_n\}, each QiQ_i must contain the unique vertex of A∩PiA \cap P_i. After this vertex has been included, the remaining 2Δ−12\Delta- 1 vertices of QiQ_i may be chosen arbitrarily from the other ∣Pi∣−1|P_i| - 1 vertices of PiP_i. Hence, the number of choices of Q\mathcal{Q} compatible with AA is ∏i=1n(∣Pi∣−12Δ−1)\prod_{i=1}^{n} \binom{|P_i|-1}{2\Delta-1}. Thus ∣X∣=N∏i=1n(∣Pi∣−12Δ−1)|\mathcal{X}| = N \prod_{i=1}^{n} \binom{|P_i|-1}{2\Delta-1}, where N=N(G,P)N = N(G,\mathcal{P}).

Combining the two estimates yields N∏i=1n(∣Pi∣−12Δ−1)=∣X∣≥2Δ∏i=1n(∣Pi∣2Δ)N \prod_{i=1}^{n} \binom{|P_i|-1}{2\Delta-1} = |\mathcal{X}| \ge2\Delta\prod_{i=1}^{n} \binom{|P_i|}{2\Delta}. Therefore,

N(G,P)=N≥2Δ∏i=1n(∣Pi∣2Δ)(∣Pi∣−12Δ−1)=2Δ∏i=1n∣Pi∣2ΔN(G,\mathcal{P}) = N \ge2\Delta\prod_{i=1}^{n} \frac{\binom{|P_i|}{2\Delta}}{\binom{|P_i|-1}{2\Delta-1}} = 2\Delta\prod_{i=1}^{n} \frac{|P_i|}{2\Delta}

as required.

The above proposition and proof, though not fully optimized, easily adapt to other settings. For example, if GG is a chordal graph, then a result of Aharoni, Berger, and Ziv [2] guarantees that every vertex lies in an independent transversal whenever ∣Pi∣≥Δ+1|P_i| \ge\Delta+ 1 for every ii. The above proof then yields that, when GG is chordal and ∣Pi∣≥Δ+2|P_i| \ge\Delta+ 2 for every ii, we have N(G,P)≥(Δ+1)(1+1Δ+1)nN(G,\mathcal{P}) \ge(\Delta+1)\left(1+\frac{1}{\Delta+1}\right)^n.

We also mention that when nn is relatively small (2Δ2\Delta or smaller), then we obtain a better lower bound on N(G,P)N(G,\mathcal{P}) by applying the above proof on another refined version of Haxell’s Theorem 5, due to Haxell and Szabó [15], stated below.

Theorem 13 (Haxell, Szabó [15]). Let GG be a graph of maximum degree at most Δ\Delta with a vertex partition P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\}. Then (G,P)(G,\mathcal{P}) has an independent transversal whenever

  • ∣Pi∣≥⌈2Δ(n−1)n⌉+1|P_i| \ge\left\lceil\frac{2\Delta(n-1)}{n}\right\rceil+1 for every ii, if n≥2n\ge2 is even;

  • ∣Pi∣≥⌈2Δ(n−2)n−1⌉+1|P_i| \ge\left\lceil\frac{2\Delta(n-2)}{n-1}\right\rceil+1 for every ii, if n≥3n\ge3 is odd.

However, the resulting lower bound is superseded by the following theorem, mentioned in the Introduction, of Tang and Zhao [25] when n≥4n\ge4 is even and Δ\Delta is sufficiently large.

Theorem 14 (Tang, Zhao [25]). For any even integer n≥4n\ge4, there exist Δ0≥1\Delta_0\ge1 and λ0>0\lambda_0>0 such that whenever Δ≥Δ0\Delta\ge\Delta_0 and 0≤k≤λ0t0\le k\le\lambda_0t and t≥⌈2(Δ+k)(n−1)n⌉+1t\ge\left\lceil\frac{2(\Delta+k)(n-1)}{n}\right\rceil+1, the following holds. If GG is a graph of maximum degree Δ\Delta, P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} is a partition of V(G)V(G), and ∣Pi∣=t|P_i|=t for every ii, then

N(G,P)≥14(2k(n−1)+1)(tn2(n−1))n−1.N(G,\mathcal{P})\ge\frac{1}{4}\bigl(2k(n-1)+1\bigr)\left(\frac{tn}{2(n-1)}\right)^{n-1}.

In particular:

  • For any even n≥4n\ge4 and sufficiently large Δ\Delta, if ∣Pi∣≥⌈2Δ(n−1)n⌉+1|P_i|\ge\left\lceil\frac{2\Delta(n-1)}{n}\right\rceil+1 for every ii, then N(G,P)≥14Δn−1N(G,\mathcal{P})\ge\frac{1}{4}\Delta^{n-1}.

  • For any n≥3n\ge3 and sufficiently large Δ\Delta, if ∣Pi∣≥2Δ|P_i|\ge2\Delta for every ii, then N(G,P)≥cnΔnN(G,\mathcal{P})\ge c_n\Delta^n for some constant cn>0c_n>0 depending only on nn.

Isoperimetric approach

In this subsection, we prove the following more general version of Theorem 3, as an application of edge-isoperimetric inequalities.

Theorem 15. Let GG be a graph of maximum degree Δ\Delta, and let P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} be a partition of V(G)V(G). For every integer tt satisfying 2Δ≤t≤min⁡i∣Pi∣2\Delta\le t\le\min_i|P_i|, we have

N(G,P)≥∏i=1n∣Pi∣tnΔ/(t−1).N(G,\mathcal{P})\ge\frac{\prod_{i=1}^{n}|P_i|}{t^{n\Delta/(t-1)}}.

In particular:

  • If ∣Pi∣≥2Δ+1|P_i|\ge2\Delta+1 for every ii, then N(G,P)≥(2Δ+1)n/2N(G,\mathcal{P})\ge(2\Delta+1)^{n/2}.

  • If ∣Pi∣≥2Δ|P_i| \ge2\Delta for every ii, then N(G,P)≥(2Δ)(1−12Δ−1)n2N(G,\mathcal{P}) \ge(2\Delta)^{\left(1-\frac{1}{2\Delta-1}\right)\frac{n}{2}}.

The basic idea is to view our reconfiguration graph on independent transversals as a subgraph of the Hamming graph, show that it induces many edges, and thus by isoperimetric inequalities deduce that it has many vertices.

For integers n,t≥1n,t \ge1, the tt-ary nn-dimensional Hamming graph H(n,t)H(n,t) has vertex set [t]n[t]^n, with two words in [t]n[t]^n connected by an edge if they differ in exactly one coordinate. We use the following formulation of Lindsey’s edge-isoperimetric inequality on the Hamming graph [22] (see also inequality (3) in [12], from which it easily follows).

Lemma 16. For any vertex subset SS of the Hamming graph H(n,t)H(n,t), with n≥1n \ge1 and t≥2t \ge2, the number of edges induced by SS is at most

12(t−1)∣S∣log⁡t∣S∣.\frac{1}{2}(t-1)|S|\log_t|S|.

Proof of Theorem 15. We prove the stated lower bound when every part has size exactly tt, where the claimed lower bound is tn⋅t−nΔ/(t−1)t^n \cdot t^{-n\Delta/(t-1)}. To get the statement for general part sizes ∣Pi∣|P_i|, we then apply the same double counting argument as in Proposition 12.

Identify each part PiP_i with the set [t][t] in arbitrary fashion, and let T⊆[t]n\mathcal{T} \subseteq[t]^n represent the family of independent transversals of (G,P)(G,\mathcal{P}) under these identifications. We view T\mathcal{T} as a vertex subset of the Hamming graph H(n,t)H(n,t). Since t≥2Δt \ge2\Delta, Haxell’s Theorem 5 gives T≠∅\mathcal{T} \ne\varnothing.

Fix an independent transversal A={a1,…,an}∈TA=\{a_1,\ldots,a_n\}\in\mathcal{T}, with ai∈Pia_i\in P_i for every ii, identified as vertices of H(n,t)H(n,t). Define the set Pi(A)={x∈Pi:(A∖{ai})∪{x}∈T}P_i(A)=\{x\in P_i:(A\setminus\{a_i\})\cup\{x\}\in\mathcal{T}\}. Every vertex in Pi∖Pi(A)P_i\setminus P_i(A) has a neighbour in A∖{ai}A\setminus\{a_i\}, which implies that ∑i=1n(∣Pi∣−∣Pi(A)∣)≤∑j=1ndG(aj)≤nΔ\sum_{i=1}^{n}(|P_i|-|P_i(A)|)\le\sum_{j=1}^{n}d_G(a_j)\le n\Delta. Thus, the degree of AA in the subgraph of H(n,t)H(n,t) induced by T\mathcal{T} satisfies

dT(A)=∑i=1n(∣Pi(A)∣−1)=n(t−1)−∑i=1n(∣Pi∣−∣Pi(A)∣)≥n(t−1)−nΔ≥n(t−1−Δ).\begin{aligned} d_{\mathcal{T}}(A)=\sum_{i=1}^{n}(|P_i(A)|-1)=n(t-1)-\sum_{i=1}^{n}(|P_i|-|P_i(A)|) \\ &\ge n(t-1)-n\Delta\ge n(t-1-\Delta). \end{aligned}

Since AA was an arbitrary vertex in T\mathcal{T}, we get that the number of edges induced by T\mathcal{T} in H(n,t)H(n,t) is at least 12n(t−1−Δ)∣T∣\frac{1}{2}n(t-1-\Delta)|\mathcal{T}|. Combining this with Lemma 16 gives 12n(t−1−Δ)∣T∣≤12(t−1)∣T∣log⁡t∣T∣\frac{1}{2}n(t-1-\Delta)|\mathcal{T}|\le\frac{1}{2}(t-1)|\mathcal{T}|\log_t|\mathcal{T}|, and therefore

∣T∣≥tn(t−1−Δ)/(t−1)=tn⋅t−nΔ/(t−1),|\mathcal{T}|\ge t^{n(t-1-\Delta)/(t-1)}=t^n\cdot t^{-n\Delta/(t-1)},

as required. □

Conjecture 4 for small number of parts

In this section, we prove the first few cases of Conjecture 4, namely when n≤3n\le3. Recall that N(G,P)N(G,\mathcal{P}) denotes the number of independent transversals of (G,P)(G,\mathcal{P}), and recall that Conjecture 4 of Buys, Kang, and Ozeki [6] states that, if ∣Pi∣=2Δ|P_i|=2\Delta for all ii, then

N(G,P)≥2Δn.N(G,\mathcal{P})\ge2\Delta^n.

This lower bound would be best possible, as it is attained by the following basic cyclic construction, a special case of Wdowinski’s characterization [28] of when the reconfiguration graph of (G,P)(G,\mathcal{P}) is disconnected.

Example 17. Let K1,…,KnK^1,\ldots,K^n be disjoint copies of KΔ,ΔK_{\Delta,\Delta}, where KiK^i has bipartition Ai∪BiA_i \cup B_i. Let G=K1∪⋯∪KnG=K^1\cup\cdots\cup K^n, and let P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} consist of Pi=Ai−1∪BiP_i=A_{i-1}\cup B_i for every i∈{1,…,n}i\in\{1,\ldots,n\} (where A0=AnA_0=A_n). Then every independent transversal of (G,P)(G,\mathcal{P}) is either a transversal of A1,…,AnA_1,\ldots,A_n or a transversal of B1,…,BnB_1,\ldots,B_n, and there are 2Δn2\Delta^n such transversals.

Observe that Conjecture 4 trivially holds when n=1n=1, with equality. Next, it is straightforward to show that the conjecture holds when n=2n=2, although in this case the cyclic construction of Example 17 is not the unique minimizer.

Proposition 18. Let GG be a graph of maximum degree Δ\Delta and let vertex partition P={P1,P2}\mathcal{P}=\{P_1,P_2\} satisfy ∣P1∣,∣P2∣≥2Δ|P_1|,|P_2|\ge2\Delta. Then N(G,P)≥2Δ2N(G,\mathcal{P})\ge2\Delta^2, and equality holds if and only if ∣P1∣=∣P2∣=2Δ|P_1|=|P_2|=2\Delta and GG is a Δ\Delta-regular bipartite graph with bipartition {P1,P2}\{P_1,P_2\}.

Proof. The independent transversals of (G,P)(G,\mathcal{P}) consist of a vertex v∈P1v\in P_1 together with a non-neighbour of vv in P2P_2. Every vertex in P1P_1 has at least ∣P2∣−Δ|P_2|-\Delta non-neighbours in P2P_2, so all together there are at least ∣P1∣(∣P2∣−Δ)≥2Δ⋅Δ=2Δ2|P_1|(|P_2|-\Delta)\ge2\Delta\cdot\Delta=2\Delta^2 independent transversals of (G,P)(G,\mathcal{P}). Equality holds if and only if ∣P1∣=∣P2∣=2Δ|P_1|=|P_2|=2\Delta and every vertex of P1P_1 has exactly Δ\Delta neighbours in P2P_2. In this case, GG is a Δ\Delta-regular bipartite graph with bipartition P\mathcal{P}.

Our next goal is to prove the conjecture for n=3n=3, and demonstrate that the described cyclic construction of Example 17 is indeed the unique minimizer of N(G,P)N(G,\mathcal{P}).

Theorem 19. Let GG be a graph of maximum degree Δ\Delta and let vertex partition P={P1,P2,P3}\mathcal{P}=\{P_1,P_2,P_3\} satisfy ∣P1∣,∣P2∣,∣P3∣≥2Δ|P_1|,|P_2|,|P_3|\ge2\Delta. Then N(G,P)≥2Δ3N(G,\mathcal{P})\ge2\Delta^3, and equality holds if and only if (G,P)(G,\mathcal{P}) is a cyclic construction of the form described in Example 17.

We prove Theorem 19 using the following lemma, which comes from an inclusion-exclusion argument. Recall that a transversal of partition P\mathcal{P} is a set with one element from each part of P\mathcal{P}.

Lemma 20. For a graph GG and partition P={P1,…,Pn}\mathcal{P}=\{P_1,\ldots,P_n\} of V(G)V(G) with ∣Pi∣=t|P_i|=t for all ii, we have

N(G,P)≥tn−1(t−Δn2)+∑T transversalof Pmax⁡{0,∣E(T)∣−1}.N(G,\mathcal{P})\ge t^{n-1}\left(t-\frac{\Delta n}{2}\right)+\sum_{\substack{T\ \mathrm{transversal}\\\mathrm{of}\ \mathcal{P}}}\max\{0,|E(T)|-1\}.

Proof. For an arbitrary transversal T={v1,…,vn}T=\{v_1,\ldots,v_n\}, with vi∈Piv_i\in P_i for all ii, let Xi,jX_{i,j} be the indicator variable for vi,vjv_i,v_j inducing an edge. Then TT is an independent transversal of (G,P)(G,\mathcal{P}) precisely when

∏{i,j}⊆[n](1−Xi,j)\prod_{\{i,j\}\subseteq[n]}(1-X_{i,j})

equals 1, and otherwise XTX_T equals 0. Thus, the number of independent transversals of (G,P)(G,\mathcal{P}) is

N(G,P)=∑T={v1,…,vn} transversal∏{i,j}⊆[n](1−Xi,j).(1)N(G,\mathcal{P})=\sum_{T=\{v_1,\ldots,v_n\}\ \mathrm{transversal}}\prod_{\{i,j\}\subseteq[n]}(1-X_{i,j}). \tag*{(1)}

For a fixed transversal T={v1,…,vn}T = \{v_1,\ldots,v_n\}, we expand the associated product as

∏{i,j}⊆[n](1−Xi,j)=1−∑{i,j}⊆[n]Xi,j+∑{i1,j1},{i2,j2}⊆[n]distinctXi1,j1Xi2,j2−⋯\prod_{\{i,j\}\subseteq[n]} (1-X_{i,j}) = 1-\sum_{\{i,j\}\subseteq[n]}X_{i,j}+\sum_{\substack{\{i_1,j_1\},\{i_2,j_2\}\subseteq[n]\\\mathrm{distinct}}}X_{i_1,j_1}X_{i_2,j_2}-\cdots

Summing over all TT, the first term becomes tnt^n, the number of transversals TT of P\mathcal{P}. The second term becomes −tn−2∣E(G)∣-t^{n-2}|E(G)| because a given edge lies in tn−2t^{n-2} transversals TT. (1) becomes

N(G,P)=tn−tn−2∣E(G)∣+∑T transversal∑k=2(n2)(−1)k(∣E(T)∣k)=tn−tn−2∣E(G)∣+∑T transversalmax⁡{0,∣E(T)∣−1}≥tn−1(t−Δn2)+∑T transversalmax⁡{0,∣E(T)∣−1},\begin{aligned} N(G,\mathcal{P}) &= t^n-t^{n-2}|E(G)|+\sum_{T\ \mathrm{transversal}}\sum_{k=2}^{\binom{n}{2}}(-1)^k\binom{|E(T)|}{k}\\ &=t^n-t^{n-2}|E(G)|+\sum_{T\ \mathrm{transversal}}\max\{0,|E(T)|-1\}\\ &\geq t^{n-1}\left(t-\frac{\Delta n}{2}\right)+\sum_{T\ \mathrm{transversal}}\max\{0,|E(T)|-1\}, \end{aligned}

where the last inequality uses that ∣E(G)∣≤Δtn2|E(G)|\leq\frac{\Delta tn}{2}. This gives the required result.

Proof of Theorem 19. The lower bound N(G,P)≥2Δ3N(G,\mathcal{P})\geq2\Delta^3 comes directly from Lemma 20 by plugging in t=2Δt=2\Delta and n=3n=3 (the last sum is always nonnegative). Equality holds if and only if GG is Δ\Delta-regular and ∣E(T)∣∈{0,1}|E(T)|\in\{0,1\} for every transversal TT of P\mathcal{P}, and each PiP_i is an independent set. In this case, we have that the non-neighbours of P1P_1 inside P2∪P3P_2\cup P_3 form a Δ\Delta-regular bipartite subgraph of GG with bipartition (inherited from) P2∪P3P_2\cup P_3. Since ∣N(P1)∣≥2Δ|N(P_1)|\geq2\Delta, there are at most 2Δ2\Delta non-neighbours of P1P_1 inside P2∪P3P_2\cup P_3. Hence by Δ\Delta-regularity these non-neighbours must induce a KΔ,ΔK_{\Delta,\Delta}. This then implies that ∣N(P1)∣=2Δ|N(P_1)|=2\Delta. Moreover, N(P1)N(P_1) is an independent set, and no vertex in P1P_1 can have neighbours in both P2P_2 and P3P_3 (by ∣E(T)∣∈{0,1}|E(T)|\in\{0,1\} for every transversal TT). From these, we obtain that P1∪(N(P1)∩P2)P_1\cup(N(P_1)\cap P_2) and P1∪(N(P1)∩P3)P_1\cup(N(P_1)\cap P_3) contain vertex-disjoint induced copies of KΔ,ΔK_{\Delta,\Delta}, with those bipartitions. This gives the cyclic construction (G,P)(G,\mathcal{P}).

Declaration of use of AI

The majority of this work was done in May, June and July 2026. For Theorems 15 and 19, the main ideas were originally found through multiple queries of ChatGPT-5.5. The authors verified, cleaned up, and generalized the details. ChatGPT-5.5 was also used for initial versions of Figure 1.

Acknowledgments

We would like to thank Pjotr Buys, Carla Groenland, and Jan van den Heuvel for fruitful discussions. This project started during the “Phase Transitions in Combinatorics, Algorithms, Probability” (PhaseCAP) Research Semester Programme at CWI in 2026. W.CvB. was supported by the Belgian National Fund for Scientific Research (FNRS). P.H. was partially supported by NSERC as well as the CWI Visiting Programme. R.J.K. was partially supported by the Dutch Research Council (NWO) grants OCENW.M20.009 and OCENW.M.25.085. R.W. was supported in part by the Austrian Science Fund (FWF) [10.55776/F1002]. For open access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.

References

  1. [1]R. Aharoni and E. Berger. The intersection of a matroid and a simplicial complex. Transactions of the American Mathematical Society, 358(11):4895–4918, 2006. doi:10.1090/S0002-9947-06-03333-5.DOI
  2. [2]R. Aharoni, E. Berger, and R. Ziv. A tree version of König’s theorem. Combinatorica, 22(3):335–343, 2002. doi:10.1007/s004930200016.DOI
  3. [3]R. Aharoni, E. Berger, and R. Ziv. Independent systems of representatives in weighted graphs. Combinatorica, 27(3):253–267, 2007. doi:10.1007/s00493-007-2086-y.DOI
  4. [4]R. Bissacot, R. Fernández, A. Procacci, and B. Scoppola. An improvement of the Lovász local lemma via cluster expansion. Combinatorics, Probability and Computing, 20(5):709–719, 2011. doi:10.1017/S0963548311000253.DOI
  5. [5]M. Bonamy, M. Johnson, I. Lignos, V. Patel, and D. Paulusma. On the diameter of reconfiguration graphs for vertex colourings. Electronic Notes in Discrete Mathematics, 38:161–166, 2011. doi:10.1016/j.endm.2011.09.028.DOI
  6. [6]P. Buys, R. J. Kang, and K. Ozeki. Reconfiguration of independent transversals. Random Structures & Algorithms, 67(1), 2025, arXiv:2407.04367. doi:10.1002/rsa.70025.DOI
  7. [7]S. Cambie, W. Cames van Batenburg, and D. W. Cranston. Optimally reconfiguring list and correspondence colourings. European Journal of Combinatorics, 115:103798, 2024, arXiv:2204.07928. doi:10.1016/j.ejc.2023.103798.DOI
  8. [8]S. Cambie, W. Cames van Batenburg, and D. W. Cranston. Sharp bounds on lengths of linear recolouring sequences. The Electronic Journal of Combinatorics, 33(1), 2026. doi:10.37236/13788.DOI
  9. [9]W. Cames van Batenburg. Large diameter for (Δ + 2)-colouring reconfiguration, 2026, arXiv:2611.17022. doi:10.48550/arXiv.2611.17022.arxiv.org/abs/2611.17022
  10. [10]L. Cereceda. Mixing Graph Colourings. PhD thesis, London School of Economics and Political Science, 2007.
  11. [11]L. De Meyer. Optimal list recoloring of subcubic graphs and complete multipartite graphs. Discrete Mathematics, 349(8):115155, 2026. doi:10.1016/j.disc.2026.115155.DOI
  12. [12]S. Diskin and W. Samotij. Isoperimetry in product graphs. The Electronic Journal of Combinatorics, 32(3):P3.12, 2025. doi:10.37236/13585.DOI
  13. [13]C. Groenland, T. Kaiser, O. Treffers, and M. Wales. Graphs of low average degree without independent transversals. Journal of Graph Theory, 102(2):374–387, 2023. doi:10.1002/jgt.22876.DOI
  14. [14]S. Hajebi and P. Haxell. Efficient reconfiguration of independent transversals, 2026, arXiv:2611.18474. doi:10.48550/arXiv.2611.18474.arxiv.org/abs/2611.18474
  15. [15]P. Haxell and T. Szabó. Odd independent transversals are odd. Combinatorics, Probability and Computing, 15(1-2):193–211, 2006. doi:10.1017/S0963548305007157.DOI
  16. [16]P. Haxell and R. Wdowinski. Constructing graphs with no independent transversals. Electron. J. Combin., 31(2):P2–39, 2024. doi:10.37236/12429.DOI
  17. [17]P. Haxell and R. Wdowinski. Degree criteria and stability for independent transversals. J. Graph Theory, 106(2):352–371, 2024. doi:10.1002/jgt.23085.DOI
  18. [18]P. E. Haxell. A condition for matchability in hypergraphs. Graphs and Combinatorics, 11(3):245–248, 1995. doi:10.1007/BF01793010.DOI
  19. [19]P. E. Haxell. A note on vertex list colouring. Combinatorics, Probability and Computing, 10(4):345–347, 2001. doi:10.1017/S0963548301004758.DOI
  20. [20]M. 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.DOI
  21. [21]R. J. Kang and T. Kelly. Colorings, transversals, and local sparsity. Random Structures & Algorithms, 61(1):173–192, 2022. doi:10.1002/rsa.21051.DOI
  22. [22]J. H. Lindsey. Assignment of numbers to vertices. The American Mathematical Monthly, 71(5):508–516, 1964. doi:10.1080/00029890.1964.11992272.DOI
  23. [23]R. Meshulam. Domination numbers and homology. Journal of Combinatorial Theory, Series A, 102(2):321–330, 2003. doi:10.1016/S0097-3165(03)00045-1.DOI
  24. [24]T. Szabó and G. Tardos. Extremal problems for transversals in graphs with bounded degree. Combinatorica, 26(3):333–351, 2006. doi:10.1007/s00493-006-0019-9.DOI
  25. [25]Y. Tang and Y. Zhao. Number of independent transversals in multipartite graphs, 2025, arXiv:2504.03950. doi:10.48550/arXiv.2504.03950.DOI
  26. [26]I. M. Wanless and D. R. Wood. A general framework for hypergraph coloring. SIAM Journal on Discrete Mathematics, 36(3):1663–1677, 2022. doi:10.1137/21M1421015.DOI
  27. [27]R. Wdowinski. Hall’s theorem for reconfigurations and higher dimensional topological connectedness, 2025, arXiv:2511.04863. doi:10.48550/arXiv.2511.04863.DOI
  28. [28]R. Wdowinski. Tight constructions for reconfigurations of independent transversals, 2026, arXiv:2604.21576. doi:10.48550/arXiv.2604.21576.DOI

Paper details

vlnc:W_cyp8zxqt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents