pith. sign in

arxiv: 2506.02455 · v2 · submitted 2025-06-03 · 🧮 math.CO

Perfect 1-factorisations of K_(11,11)

Jack Allsop , Ian M. Wanless This is my paper

Pith reviewed 2026-05-19 11:47 UTC · model grok-4.3

classification 🧮 math.CO
keywords perfect 1-factorisationcomplete bipartite graphrow-Hamiltonian Latin squareK_{11,11}enumerationHamiltonian cycle
0
0 comments X

The pith

Computer enumeration determines all perfect 1-factorisations of K_{11,11} and all row-Hamiltonian Latin squares of order 11.

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

The paper carries out an exhaustive computer search for perfect 1-factorisations of the complete bipartite graph on 22 vertices. Such a factorisation breaks the edges into 1-factors so that the union of any two is a single cycle through all vertices. The same search yields every row-Hamiltonian Latin square of order 11, because these objects are equivalent under a standard bijection. The work also supplies the missing counts for row-Hamiltonian Latin squares that arise from the known infinite families of perfect 1-factorisations of complete graphs.

Core claim

A computer enumeration has produced the complete list of perfect 1-factorisations of K_{11,11}; the same list gives all row-Hamiltonian Latin squares of order 11, and the counts for those associated with the classical families of perfect 1-factorisations of K_{2m+1} are now known.

What carries the argument

A perfect 1-factorisation: an edge-decomposition of K_{n,n} into 1-factors such that any two 1-factors union to a Hamiltonian cycle.

Load-bearing premise

The computer search examined every possible case without missing any decompositions or introducing implementation errors.

What would settle it

An independent program or hand-check that produces a different total number of distinct perfect 1-factorisations of K_{11,11}.

Figures

Figures reproduced from arXiv: 2506.02455 by Ian M. Wanless, Jack Allsop.

Figure 1
Figure 1. Figure 1: Eight symmetric row-Hamiltonian Latin squares [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
read the original abstract

A perfect $1$-factorisation of a graph is a decomposition of that graph into $1$-factors such that the union of any two $1$-factors is a Hamiltonian cycle. A Latin square of order $n$ is row-Hamiltonian if for every pair $(r,s)$ of distinct rows, the permutation mapping $r$ to $s$ has a single cycle of length $n$. We report the results of a computer enumeration of the perfect $1$-factorisations of the complete bipartite graph $K_{11,11}$. This also allows us to find all row-Hamiltonian Latin squares of order $11$. Finally, we plug a gap in the literature regarding how many row-Hamiltonian Latin squares are associated with the classical families of perfect $1$-factorisations of complete graphs.

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 manuscript reports the results of an exhaustive computer enumeration of the perfect 1-factorisations of the complete bipartite graph K_{11,11}. Using this enumeration, the authors determine all row-Hamiltonian Latin squares of order 11 and supply counts of row-Hamiltonian Latin squares arising from the classical families of perfect 1-factorisations of complete graphs, thereby filling a stated gap in the literature.

Significance. If the computational enumeration is correct and exhaustive, the work supplies the first complete classification for this order, yielding concrete numerical data on the number of such objects and their relation to Latin squares. Such exhaustive results for small orders serve as benchmarks for conjectures and theoretical constructions in the study of 1-factorisations and orthogonal Latin squares.

major comments (1)
  1. [Enumeration procedure (likely §3 or §4)] The central results (the reported counts of perfect 1-factorisations and the derived counts of row-Hamiltonian Latin squares) rest entirely on the correctness and exhaustiveness of the computer search. The manuscript describes the enumeration procedure but supplies neither the source code, a machine-checkable certificate of completeness, nor an independent verification method (e.g., cross-check against a smaller order or an alternative implementation). This is load-bearing because any undetected omission or duplication in the search would invalidate all downstream claims.
minor comments (2)
  1. [Abstract] The abstract states that the enumeration 'also allows us to find all row-Hamiltonian Latin squares' but does not indicate whether the authors output the squares themselves or only their count; clarifying this would help readers assess the completeness of the contribution.
  2. [Introduction] Notation for the bipartite graph and the perfect property is standard, but a brief reminder of the precise definition of 'perfect' (union of any two 1-factors is Hamiltonian) in the introduction would improve readability for readers outside the immediate subfield.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our results and for the constructive comment on the computational aspects of the work. We respond to the major comment point by point below.

read point-by-point responses

  1. Referee: [Enumeration procedure (likely §3 or §4)] The central results (the reported counts of perfect 1-factorisations and the derived counts of row-Hamiltonian Latin squares) rest entirely on the correctness and exhaustiveness of the computer search. The manuscript describes the enumeration procedure but supplies neither the source code, a machine-checkable certificate of completeness, nor an independent verification method (e.g., cross-check against a smaller order or an alternative implementation). This is load-bearing because any undetected omission or duplication in the search would invalidate all downstream claims.

    Authors: We agree that the correctness and exhaustiveness of the enumeration are foundational to the reported counts. Section 3 of the manuscript provides a detailed description of the backtracking algorithm, including the orderly generation method, symmetry-breaking techniques, and pruning criteria employed to guarantee that every perfect 1-factorisation is generated exactly once. To address the referee's concern directly, we will revise the manuscript to include explicit cross-validation results: the same implementation reproduces the known enumerations for K_{5,5} and K_{7,7} reported in the literature. In addition, we will make the full source code available in a public repository (with a permanent link added to the revised paper) so that independent verification is possible. While a formal machine-checkable certificate lies outside the scope of this work, we believe the combination of algorithmic description, smaller-order verification, and code availability provides a practical and honest response to the load-bearing nature of the computation. revision: yes

Circularity Check

0 steps flagged

No significant circularity in direct computational enumeration

full rationale

The paper reports the results of a computer enumeration of perfect 1-factorisations of K_{11,11} and the associated row-Hamiltonian Latin squares of order 11. This constitutes a direct search over an externally defined combinatorial object with no claimed first-principles derivation, fitted parameters, or self-referential definitions that would reduce outputs to inputs by construction. Any self-citations address gaps in the literature on classical families but are not load-bearing for the enumeration counts themselves. The work is therefore self-contained against external benchmarks, with the central claims consisting of reported search outcomes rather than tautological reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from graph theory and Latin squares; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Standard definitions of 1-factors, Hamiltonian cycles, perfect 1-factorisations, and row-Hamiltonian Latin squares.
    These are established combinatorial objects used without redefinition.

pith-pipeline@v0.9.0 · 5663 in / 1105 out tokens · 33536 ms · 2026-05-19T11:47:43.737792+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

19 extracted references · 19 canonical work pages

  1. [1]

    Row-Hamiltonian Latin squares and Falconer varieties

    J. Allsop and I. M. Wanless. “Row-Hamiltonian Latin squares and Falconer varieties”. Proc. Lond. Math. Soc. (3) 128.1 (2024), Paper No. e12575, 28

    work page 2024

  2. [2]

    Finite topologies and Hamiltonian paths

    B. A. Anderson. “Finite topologies and Hamiltonian paths”. J. Combinatorial Theory Ser. B 14 (1973), pp. 87–93

    work page 1973

  3. [3]

    Symmetry groups of some perfect 1-factorizations of complete graphs

    B. A. Anderson. “Symmetry groups of some perfect 1-factorizations of complete graphs”. Discrete Math. 18.3 (1977), pp. 227–234

    work page 1977

  4. [4]

    New families of atomic Latin squares and perfect 1-factorisations

    D. Bryant, B. Maenhaut, and I. M. Wanless. “New families of atomic Latin squares and perfect 1-factorisations”. J. Combin. Theory Ser. A 113.4 (2006), pp. 608–624

    work page 2006

  5. [5]

    A family of perfect factorisations of com- plete bipartite graphs

    D. Bryant, B. M. Maenhaut, and I. M. Wanless. “A family of perfect factorisations of com- plete bipartite graphs”. J. Combin. Theory Ser. A 98.2 (2002), pp. 328–342

    work page 2002

  6. [6]

    There are 23 nonisomorphic perfect one-factorizations of K14

    J. H. Dinitz and D. K. Garnick. “There are 23 nonisomorphic perfect one-factorizations of K14”. J. Combin. Des. 4.1 (1996), pp. 1–4

    work page 1996

  7. [7]

    On 1-factorizations of the complete graph and the relation- ship to round robin schedules

    E. N. Gelling and R. E. Odeh. “On 1-factorizations of the complete graph and the relation- ship to round robin schedules”. Proceedings of the Third Manitoba Conference on Numerical Mathematics (Winnipeg, Man., 1973) . Vol. IX. Congress. Numer. Utilitas Math., Winnipeg, MB, 1974, pp. 213–221

    work page 1973

  8. [8]

    Perfect 1-factorisations of K16

    M. J. Gill and I. M. Wanless. “Perfect 1-factorisations of K16”. Bull. Aust. Math. Soc. 101.2 (2020), pp. 177–185

    work page 2020

  9. [9]

    Hamilton graphs and Hamilton circuits

    A. Kotzig. “Hamilton graphs and Hamilton circuits”. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 63– 82

    work page 1963

  10. [10]

    Atomic Latin squares of order eleven

    B. M. Maenhaut and I. M. Wanless. “Atomic Latin squares of order eleven”. J. Combin. Des. 12.1 (2004), pp. 12–34. 13

    work page 2004

  11. [11]

    Practical graph isomorphism, II

    B. D. McKay and A. Piperno. “Practical graph isomorphism, II”. J. Symbolic Comput. 60 (2014), pp. 94–112

    work page 2014

  12. [12]

    There are 3155 nonisomorphic perfect one-factorizations of K16

    M. Meszka. “There are 3155 nonisomorphic perfect one-factorizations of K16”. J. Combin. Des. 28.1 (2020), pp. 85–94

    work page 2020

  13. [13]

    Some new non-cyclic Latin squares that have cyclic and Youden properties

    P. J. Owens and D. A. Preece. “Some new non-cyclic Latin squares that have cyclic and Youden properties”. Ars Combin. 44 (1996), pp. 137–148

    work page 1996

  14. [14]

    Intersection of perfect 1-factorizations of complete graphs

    A. P. Petrenyuk and A. Ya. Petrenyuk. “Intersection of perfect 1-factorizations of complete graphs”. Cybernetics 16.1 (1980), pp. 6–9

    work page 1980

  15. [15]

    Atomic Latin squares based on cyclotomic orthomorphisms

    I. M. Wanless. “Atomic Latin squares based on cyclotomic orthomorphisms”. Electron. J. Combin. 12 (2005), Research Paper 22, 23

    work page 2005

  16. [16]

    Diagonally cyclic Latin squares

    I. M. Wanless. “Diagonally cyclic Latin squares”. European J. Combin. 25.3 (2004), pp. 393– 413

    work page 2004

  17. [17]

    Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles

    I. M. Wanless. “Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles”. Electron. J. Combin. 6 (1999), Research Paper 9, 16

    work page 1999

  18. [18]

    I. M. Wanless. User homepage. url: https://users.monash.edu.au/~iwanless/data/

    work page

  19. [19]

    Symmetries that Latin squares inherit from 1-factorizations

    I. M. Wanless and E. C. Ihrig. “Symmetries that Latin squares inherit from 1-factorizations”. J. Combin. Des. 13.3 (2005), pp. 157–172. 14

    work page 2005