Id: arxiv/2607.13165 Url: https://arxiv.org/abs/2607.13165 Tags: math.CO, cs.DM Score: 0 Title: Interchange graphs of (0,1)-matrices are maximally Hamiltonian Domain: math.CO Source: arxiv Authors: Jeffrey S. Baggett, Huiya Yan Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-14 Page: https://delphi.science/r/arxiv/2607.13165 For integer vectors R,S let A(R,S) denote the class of (0,1)-matrices with row sum vector R and column sum vector S. Its interchange graph G(R,S) has A(R,S) as its vertex set, two matrices being adjacent when they differ by a single 2 x 2 interchange. Brualdi asked whether G(R,S) is Hamiltonian for every R,S. We prove the stronger statement that G(R,S) is maximally Hamiltonian: Hamilton-laceable when bipartite, and Hamilton-connected when not. The proof is a structural induction on the number of matrices in the class, organized by the structure theory of interchange graphs. Deleting inactive…