Perfect 1-factorisations

Complete graphs

With Michael Gill I enumerated the P1Fs of K16. It turns out that there are 3155 of them, up to isomorphism. This includes 89 with non-trivial automorphism group. You can download the P1Fs here. They are written using vertices a,b,...,p. Each line lists the 15 factors that comprise the P1F; each factor is given as 8 edges concatenated without spaces. Every P1F includes the factors abcdefghijklmnop and apbcdefghijklmno, and is the lexicographically least representative of its isomorphism class under this constraint. The list is sorted in decreasing order of the size of the automorphism group. Representatives with the same sized automorphism groups are sorted lexicographically.

New orders of P1Fs

The method used in my paper for constructing perfect 1-factorisations has certainly not been exhausted yet. There are two further orders claimed in reference [10] which I should have recognised in my paper as having been found by Volker Leck. They are 1092728 and 1225044. These and many other examples can be added to the tables in my paper as detailed below.

Note that this page will be periodically updated and the date on which each new result was added is given at the end of each line.

P1Fs of orders p3+1

To table 6 add the lines

p=101, q=1030301, ζ(x)=x3+x+3, c=[813092,759910,233271,3]     (24 Mar 2007)

p=103, q=1092727, ζ(x)=x3+x+4, c=[828376,896]     (31 May 2006)

p=107, q=1225043, ζ(x)=x3+x+9, c=[1107573,151]     (31 May 2006)

p=109, q=1295029, ζ(x)=x3+x+6, c=[271574,645911,1082655,4]     (17 Apr 2007)

p=127, q=2048383, ζ(x)=x3+x+15, c=[840749,23]     (24 Mar 2007)

p=131, q=2248091, ζ(x)=x3+x+3, c=[2096100,298]     (31 May 2006)

p=139, q=2685619, ζ(x)=x3+x+7, c=[436598,2118]     (31 May 2006)

p=149, q=3307949, ζ(x)=x3+x+14, c=[1861398,3141536,1357853,1]     (17 Apr 2007)

p=151, q=3442951, ζ(x)=x3+x+5, c=[1492322,66]     (31 May 2006)

p=163, q=4330747, ζ(x)=x3+x+4, c=[2015256,4602]     (24 Mar 2007)

p=167, q=4657463, ζ(x)=x3+x+3, c=[3183263,109]     (31 May 2006)

p=179, q=5735339, ζ(x)=x3+x+4, c=[2740965,1219]     (31 May 2006)

p=191, q=6967871, ζ(x)=x3+x+3, c=[4789910,1160]     (24 Mar 2007)

p=199, q=7880599, ζ(x)=x3+x+13, c=[3457494,2368]     (24 Mar 2007)

p=211, q=9393931, ζ(x)=x3+x+24, c=[5457264,1168]     (24 Mar 2007)

p=223, q=11089567, ζ(x)=x3+x+9, c=[4722613,4305]     (24 Mar 2007)

p=227, q=11697083, ζ(x)=x3+x+9, c=[9051956,1442]     (24 Mar 2007)

p=239, q=13651919, ζ(x)=x3+x+11, c=[1597504,5918]     (24 Mar 2007)

p=251, q=15813251, ζ(x)=x3+x+7, c=[9285089,11965]     (24 Mar 2007)

p=263, q=18191447, ζ(x)=x3+x+8, c=[8313030,2840]     (24 Mar 2007)

p=271, q=19902511, ζ(x)=x3+x+4, c=[6563520,170]     (24 Mar 2007)

p=283, q=22665187, ζ(x)=x3+x+24, c=[2245440,3574]     (24 Mar 2007)

P1Fs of orders p5+1

To table 7 add the lines

p=19, q=2476099, ζ(x)=x5+x+9, c=[949007,791]     (24 Mar 2007)

p=23, q=6436343, ζ(x)=x5+x+3, c=[1045440,7580]     (24 Mar 2007)

Summary

To the best of my knowledge, the following cases cover all known existence results. A perfect 1-factorisation of Kn+1 exists if n is odd and
  1. n<50,
  2. n=p for some prime p (two non-isomorphic constructions known),
  3. n=2p-1 for some prime p,
  4. n=p2 for some prime p<280 such that p=3 or 5 mod 8,
  5. n=p2 for some prime p<30 such that p=7 mod 8,
  6. n=p3 for some prime p<300 such that p=3 mod 4,
  7. n=p3 for some prime p<150 such that p=5 mod 8,
  8. n=p4 for some prime p<6
  9. n=p5 for some prime p<25 except possibly p=17
  10. n=p6 for some prime p<6
    11. or
  11. n=57
It's tempting to look at this and believe the "orthomorphism method" (also known as quotient coset starters) will work for all prime powers. But it fails in some cases: eg. 37 and 77.

Complete bipartite graphs

Up to isomorphism there are

I have given these P1Fs in the form of row-Hamiltonian Latin squares. In the case of order 11, some of these are conjugates to each other, so if you want representatives of the species of row-Hamiltonian Latin squares instead, there are slightly fewer of those (namely 687115). These results are from joint work with Jack Allsop. In our paper, we describe an invariant that we invented to help distinguish P1Fs. It is calculated from each set of 3 one-factors in the factorisation and was able to distinguish almost of the isomorphisms classes, with just 6 pairs coinciding.

Related literature

If you've got this far, you may be interested in the following papers I've written on perfect 1-factorisations and related topics.

  1. J. Allsop and I. M. Wanless, Perfect 1-factorisations of K11,11 Submitted (2025).
  2. J. Allsop and I. M. Wanless, Row-Hamiltonian Latin squares and Falconer varieties, Proc. London Math. Soc. (3) 128 (2024), e12575.
  3. M. J. Gill and I. M. Wanless, Perfect 1-factorisations of K16, Bull. Aust. Math. Soc. 101 (2020), 177-185.
  4. D. Bryant, B. M. Maenhaut and I. M. Wanless, New families of atomic Latin squares and perfect one-factorisations, J. Combin. Theory A 113, (2006) 608-624.
  5. I. M. Wanless, Atomic Latin squares based on cyclotomic orthomorphisms, Electron. J. Combin. 12 (2005) R22.
  6. I. M. Wanless and E. C. Ihrig, Symmetries that Latin squares inherit from 1-factorizations, J. Combin. Des., 13 (2005) 157-172.
  7. B. M. Maenhaut and I. M. Wanless, Atomic Latin squares of order eleven, J. Combin. Designs, 12 (2004), 12-34.
  8. D. Bryant, B. M. Maenhaut and I. M. Wanless, A family of perfect factorisations of complete bipartite graphs, J. Combin. Theory A 98 (2002) 328-342.
  9. I. M. Wanless, Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles, Electron. J. Combin. 6 (1999) R9.