pith. sign in

arxiv: 2604.21576 · v1 · submitted 2026-04-23 · 🧮 math.CO

Tight constructions for reconfigurations of independent transversals

Ronen Wdowinski This is my paper

Pith reviewed 2026-05-09 21:37 UTC · model grok-4.3

classification 🧮 math.CO
keywords independent transversalsreconfiguration graphsgraph partitionsconnectivityconstructive characterizationK_{Delta,Delta}maximum degree
0
0 comments X

The pith

The exceptional partitions that disconnect independent transversal reconfiguration graphs are all generated by one simple constructive procedure.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper exactly characterizes the exceptional partitions where the reconfiguration graph on independent transversals fails to be connected, even though the maximum degree is at most Delta and every block has size at least 2Delta. It shows that while these exceptional structures come in a rich variety, every one of them arises from a single straightforward constructive procedure built on unions of blocks that induce disjoint copies of K_{Delta,Delta}. A reader would care because the result finishes the classification begun in the prior theorem: it tells precisely when any two valid independent transversals can be transformed into each other by changing one vertex at a time without ever losing independence or missing a block.

Core claim

The central claim is that the partitions leading to disconnected reconfiguration graphs under the stated degree and block-size conditions consist exactly of those that can be constructed by a simple procedure whose only building blocks are unions of k blocks inducing k disjoint copies of K_{Delta,Delta}. This procedure produces many different partition structures, yet it captures every exception without remainder.

What carries the argument

The simple constructive procedure that generates every exceptional partition from unions of blocks inducing disjoint K_{Delta,Delta} copies.

If this is right

  • The reconfiguration graph is connected for every partition that cannot be generated by the procedure.
  • Every disconnected case under the given conditions arises from the procedure and from no other source.
  • The classification of connectivity is now complete: no additional exceptional partition structures exist outside those constructed this way.
  • Any concrete partition built by the procedure serves as a tight example showing that the 2Delta block-size bound cannot be lowered without creating more exceptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The procedure supplies an explicit way to build infinite families of tight examples for the original theorem.
  • One could check in polynomial time whether a given partition is exceptional by attempting to reverse the construction steps.
  • Analogous constructive classifications may exist for other reconfiguration problems that involve selecting one vertex per group under independence constraints.

Load-bearing premise

That the only obstructions to connectivity are those specific unions of blocks inducing disjoint K_{Delta,Delta} and that the given constructive procedure produces every such obstruction.

What would settle it

Exhibit a partition satisfying the maximum-degree and minimum-block-size conditions whose reconfiguration graph is disconnected but cannot be produced by the procedure, or exhibit one produced by the procedure whose reconfiguration graph is nevertheless connected.

Figures

Figures reproduced from arXiv: 2604.21576 by Ronen Wdowinski.

Figure 1
Figure 1. Figure 1: Successive applications of Lemma 1.4. At each step, we add a new copy of (H, V) = (KA,B, {A, B}) with |A|, |B| = 3, choose a block Ui from the previous graph, and distribute the vertices of Ui into A and B. Definition 1.3. We define an elementary non-reconfigurable instance (G, U) as follows. The graph G is a disjoint union of m complete bipartite graphs KA1,B1 ⊔ · · · ⊔ KAm,Bm. Next, the partition U = {U1… view at source ↗
Figure 2
Figure 2. Figure 2: A feasible 3-tuple (R, S, T). The top three blocks represent the roots of the forest GR−(S−T) . R : S : T [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An induced matching configuration (R, S, T). We have I(R) = I(S ∪ T) and G[R] is a matching. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) Reconfiguration in proof of Claim 10. The arrows with numbers represent the movement of the black vertex within a block at a given step. (b) Reconfigurations in proof of Claim 11. The arrows with numbers represent the movement of both the black and white vertex within a block at a given step. 3.3 Finishing the proof of Theorem 2.5 In this subsection, we finish the proof of Theorem 2.5. Let (G, U) satis… view at source ↗
read the original abstract

For a graph $G$ and partition $\mathcal{U}$ of its vertex set, an independent transversal of $(G, \mathcal{U})$ is an independent set of $G$ that contains one vertex from each block of $\mathcal{U}$. Buys, Kang, and Ozeki studied when a reconfiguration graph on independent transversals of $(G,\mathcal{U})$ is connected, meaning any independent transversal can be transformed into any other one through a sequence of one-vertex modifications while always maintaining an independent transversal. Analogous to a theorem of Haxell, they proved that this is the case if $G$ has maximum degree $\Delta$ and each block of $\mathcal{U}$ has size at least $2\Delta$, except if the union of some $k \ge 1$ blocks of $\mathcal{U}$ induces $k$ disjoint copies of the complete bipartite graph $K_{\Delta, \Delta}$ in $G$. Solving one of their problems, we exactly characterize the partition structure in the latter exceptional instances of their theorem, showing that there is a rich variety of them but they are generated by a simple constructive procedure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper solves an open problem of Buys, Kang, and Ozeki by exactly characterizing the exceptional partitions U of V(G) for which the reconfiguration graph on independent transversals of (G,U) fails to be connected, even though G has maximum degree Δ and every block of U has size at least 2Δ. The exceptions are precisely those in which some subcollection of k blocks induces k disjoint copies of K_{Δ,Δ}; the authors give a simple constructive procedure that generates all such partitions and prove that every exceptional instance arises this way.

Significance. The result supplies the missing structural half of the Buys–Kang–Ozeki theorem, yielding a complete, if-and-only-if criterion for connectivity of the reconfiguration graph under the stated degree and block-size hypotheses. The constructive procedure is a genuine strength: it is parameter-free, explicitly generates an infinite family of examples, and makes the exceptional cases fully explicit rather than merely existential. This advances the reconfiguration literature by furnishing both a clean classification and a practical method for producing tight examples.

major comments (1)
  1. The manuscript states that the constructive procedure captures every exceptional partition, but the proof that no other obstructions exist (beyond the K_{Δ,Δ} unions already identified by Buys–Kang–Ozeki) is only sketched in the abstract. A self-contained verification that the generated objects satisfy the prior theorem’s hypotheses and that every exception is obtained should be expanded, ideally with an explicit bijection or inductive argument.
minor comments (2)
  1. Notation for the blocks of U and the induced subgraphs on their unions should be introduced once and used consistently; the current alternation between “subcollection of blocks” and “union of some k blocks” is slightly ambiguous on first reading.
  2. The abstract claims “a rich variety” of exceptional partitions; a short table or figure exhibiting the smallest non-trivial examples generated by the procedure would make this claim immediately visible to readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: The manuscript states that the constructive procedure captures every exceptional partition, but the proof that no other obstructions exist (beyond the K_{Δ,Δ} unions already identified by Buys–Kang–Ozeki) is only sketched in the abstract. A self-contained verification that the generated objects satisfy the prior theorem’s hypotheses and that every exception is obtained should be expanded, ideally with an explicit bijection or inductive argument.

    Authors: We agree that greater explicitness improves readability. The body of the manuscript (Section 3) already contains a full inductive proof on the number of blocks showing that every exceptional partition arises from the procedure, together with a direct verification that all generated instances meet the Δ-degree and ≥2Δ block-size hypotheses of Buys–Kang–Ozeki. To address the request for an explicit bijection, we have added Subsection 3.4 that constructs the inverse map: given an exceptional partition, the matching structure of the K_{Δ,Δ} components is extracted and the construction steps are recovered in reverse. The revised version therefore supplies a self-contained, bijective characterization. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper extends an external theorem of Buys, Kang, and Ozeki by providing a graph-theoretic characterization of the exceptional partitions (those inducing k disjoint K_{Δ,Δ} copies). The constructive procedure is derived from direct analysis of the given conditions on Δ and block sizes, without reducing to any fitted parameter, self-referential definition, or load-bearing self-citation. The prior result is independent (different authors) and the new contribution is a structural enumeration that does not rename or smuggle in prior results by the same authors. The derivation chain is self-contained against the stated hypotheses.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph-theoretic definitions of independent sets, transversals, and reconfiguration graphs; no free parameters, new axioms beyond domain standards, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions and basic properties of graphs, independent sets, and transversals in combinatorial graph theory.
    Invoked throughout to define independent transversals and reconfiguration steps.

pith-pipeline@v0.9.0 · 5489 in / 1155 out tokens · 39688 ms · 2026-05-09T21:37:39.245779+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Aharoni, E

    R. Aharoni, E. Berger, and R. Ziv. Independent systems of representatives in weighted graphs.Com- binatorica, 27(3):253–267, 2007

    work page 2007

  2. [2]

    Aharoni, M

    R. Aharoni, M. Chudnovsky, and D. Kotlov. Triangulated spheres and colored cliques.Discrete Com- put. Geom., 28(2):223–229, 2002

    work page 2002

  3. [3]

    Aharoni and P

    R. Aharoni and P. Haxell. Hall’s theorem for hypergraphs.J. Graph Theory, 35(2):83–88, 2000

    work page 2000

  4. [4]

    Aharoni, R

    R. Aharoni, R. Holzman, D. Howard, and P. Spr¨ ussel. Cooperative colorings and independent systems of representatives.Electron. J. Combin., 22(2):P2–27, 2015

    work page 2015

  5. [5]

    Asadpour, U

    A. Asadpour, U. Feige, and A. Saberi. Santa claus meets hypergraph matchings.ACM Trans. Algo- rithms, 8(3):1–9, 2012

    work page 2012

  6. [6]

    Bohman and R

    T. Bohman and R. Holzman. On a list coloring conjecture of Reed.J. Graph Theory, 41(2):106–109, 2002

    work page 2002

  7. [7]

    P. Buys, R. J. Kang, and K. Ozeki. Reconfiguration of independent transversals.Random Structures Algorithms, 67(1):e70025, 2025. 16

    work page 2025

  8. [8]

    Cambie, P

    S. Cambie, P. Haxell, R. J. Kang, and R. Wdowinski. A precise condition for independent transversals in bipartite covers.SIAM J. Discrete Math., 38(2):1451–1461, 2024

    work page 2024

  9. [9]

    Graf and P

    A. Graf and P. Haxell. Finding independent transversals efficiently.Combin. Probab. Comput., 29(5):780– 806, 2020

    work page 2020

  10. [10]

    P. Haxell. On forming committees.Amer. Math. Monthly, 118(9):777–788, 2011

    work page 2011

  11. [11]

    P. Haxell. Topological connectedness and independent sets in graphs. InSurveys in Combinatorics

    work page

  12. [12]

    Cambridge University Press, 2019

    London Mathematical Society Lecture Notes, volume 456, pages 89–114. Cambridge University Press, 2019

    work page 2019

  13. [13]

    Haxell and T

    P. Haxell and T. Szab´ o. Improved integrality gap in max–min allocation, or, topology at the north pole.Combinatorica, 45(2):22, 2025

    work page 2025

  14. [14]

    Haxell and T

    P. Haxell and T. Szab´ o. Odd independent transversals are odd.Combin. Probab. Comput., 15(1-2):193– 211, 2006

    work page 2006

  15. [15]

    Haxell and R

    P. Haxell and R. Wdowinski. Constructing graphs with no independent transversals.Electron. J. Combin., 31(2):P2–39, 2024

    work page 2024

  16. [16]

    Haxell and R

    P. Haxell and R. Wdowinski. Degree criteria and stability for independent transversals.J. Graph Theory, 106(2):352–371, 2024

    work page 2024

  17. [17]

    P. E. Haxell. A condition for matchability in hypergraphs.Graphs Combin., 11(3):245–248, 1995

    work page 1995

  18. [18]

    P. E. Haxell. A note on vertex list colouring.Combin. Probab. Comput., 10(4):345–347, 2001

    work page 2001

  19. [19]

    G. Jin. Complete subgraphs of r-partite graphs.Combin. Probab. Comput., 1(3):241–250, 1992

    work page 1992

  20. [20]

    Meshulam

    R. Meshulam. Domination numbers and homology.J. Combin. Theory Ser. A, 102(2):321–330, 2003

    work page 2003

  21. [21]

    C. M. Mynhardt and S. Nasserasr. Reconfiguration of colourings and dominating sets in graphs. In 50 Years of Combinatorics, Graph Theory, and Computing, pages 171–191. Chapman and Hall/CRC, 2019

    work page 2019

  22. [22]

    Nishimura

    N. Nishimura. Introduction to reconfiguration.Algorithms, 11(4):52, 2018

    work page 2018

  23. [23]

    B. Reed. The list colouring constants.J. Graph Theory, 31(2):149–153, 1999

    work page 1999

  24. [24]

    Szab´ o and G

    T. Szab´ o and G. Tardos. Extremal problems for transversals in graphs with bounded degree.Combi- natorica, 26(3):333–351, 2006

    work page 2006

  25. [25]

    Tang and Y

    Y. Tang and Y. Zhao. Number of independent transversals in multipartite graphs.arXiv preprint arXiv:2504.03950, 2025

    work page arXiv 2025

  26. [26]

    van den Heuvel

    J. van den Heuvel. The complexity of change. In volume 409 of number 2013, pages 127–160. Cambridge University Press, 2013

    work page 2013

  27. [27]

    Wdowinski

    R. Wdowinski. Bounded degree graphs and hypergraphs with no full rainbow matchings.European J. Combin., 133:104316, 2026

    work page 2026

  28. [28]

    Wdowinski

    R. Wdowinski. Hall’s theorem for reconfigurations and higher dimensional topological connectedness. arXiv preprint arXiv:2511.04863, 2025

    work page arXiv 2025

  29. [29]

    R. Yuster. Independent transversals in r-partite graphs.Discrete Math., 176(1-3):255–261, 1997. 17 A Proof of Lemmas 2.2 and 2.3 In this appendix, we provide proofs of Lemmas 2.2 and 2.3. Proof of Lemma 2.2.We prove the following four separate claims, assuming throughout that (H,V) is minimally NIT: (i) IfRG(G,U) is disconnected, thenRG(G∪H,W) is disconne...

    work page 1997

  30. [30]

    InitiateG ′ ←G,U ′ i ←U i for alli∈[m],I←[m], andT← ∅

    work page

  31. [31]

    InitiateJ← {i∈I:U ′ i =A i}

    work page

  32. [32]

    Choose anyu i ∈U ′ i for alli∈J, and updateT←T∪ {u i :i∈J}

    WhileJ̸=∅: a. Choose anyu i ∈U ′ i for alli∈J, and updateT←T∪ {u i :i∈J}. b. UpdateG ′ ←G ′ − S i∈J KAi,Bi,U ′ i ←U ′ i ∩V(G ′) for alli∈I−J, andI←I−J. d. UpdateJ← {i∈I:U ′ i =A i}

    work page

  33. [33]

    Choose anyu i ∈U ′ i −A i for alli∈I,

    work page

  34. [34]

    Notice that Algorithm 3 terminates because the cardinality ofIdecreases after each loop, so eventuallyJ=∅

    UpdateT←T∪ {u i :i∈I}, and returnT. Notice that Algorithm 3 terminates because the cardinality ofIdecreases after each loop, so eventuallyJ=∅. Notice also that all of theU ′ i remain nonempty after each iteration, since we start with an elementary non-reconfigurable instance. We claim that the outputTof the algorithm is an IT of (G,U). Assume that at the ...

    work page