Interchange Graphs of (0,1)-Matrices Are Maximally Hamiltonian

Overview

This study establishes a strong property of interchange graphs of (0,1)-matrices, demonstrating that these graphs are maximally Hamiltonian. The specific class of graphs, denoted as G(R,S), represents (0,1)-matrices that share a common row sum vector (R) and column sum vector (S). In this context, vertices of G(R,S) correspond to individual (0,1)-matrices within the class A(R,S). Two matrices are considered adjacent if they differ by a single 2x2 interchange. The central finding addresses and strengthens a question posed by Brualdi regarding the Hamiltonian nature of G(R,S).

Research Context

The research builds upon a standing question from Brualdi concerning the Hamiltonian property of interchange graphs G(R,S) for all possible integer vectors R and S. The current work does not merely affirm the Hamiltonian property but extends this to a stronger statement: these graphs are maximally Hamiltonian. This distinction means that G(R,S) is proven to be Hamilton-laceable in cases where it is bipartite, and Hamilton-connected when it is not bipartite.

Approach

The proof strategy employed is a structural induction, progressing based on the number of matrices present within the class A(R,S). This inductive process is structured by applying the existing structure theory pertinent to interchange graphs. The methodology involves several steps for simplifying and analyzing the graph classes:

• Decomposition: The approach utilizes techniques of deleting inactive lines and splitting invariant positions. These operations allow for the expression of any class A(R,S) as a Cartesian product of smaller components.
• Reduction: By decomposing the classes into Cartesian products, the argument is reduced to analyzing these smaller, prime factors.
• Bipartite Cases: For bipartite classes, the proof does not rely on induction. Instead, these are identified as products of complete transposition graphs. The study demonstrates that these specific products are 'paired 2-disjoint-path-coverable', a property that directly implies they are Hamilton-laceable. This specific step incorporates a recent theorem developed by Coleman, Fischberg, Gong, Harrington, and Wong concerning paired disjoint path covers.
• Non-Bipartite Cases: The non-bipartite classes are segmented into three distinct categories for analysis:
  1. Products that are assembled from smaller factors.
  2. A foundational group consisting of Johnson graphs and other small classes.
  3. Large prime classes, which are addressed through a 'pivot-and-fiber construction'. In this construction, the line quotients are identified as matroid base-exchange graphs.
• Formal Verification: The complete logical argument has undergone machine-checking using the Lean 4 proof assistant. This formalization process started from first principles and incorporated seven cited results from existing literature. Notably, the disjoint-path-cover results utilized in the proof were also formally proven within the Lean 4 framework.

Findings

The primary finding of this research is that the interchange graphs G(R,S) for (0,1)-matrices are maximally Hamiltonian. This generalizes and strengthens prior understandings of these graphs:

• G(R,S) is Hamilton-laceable when the graph is bipartite.
• G(R,S) is Hamilton-connected when the graph is not bipartite.

This finding resolves Brualdi's question by providing a more robust characterization of the Hamiltonian properties of these graphs.