Perfect 1-factorisations

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.

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. 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.
  2. I. M. Wanless, Atomic Latin squares based on cyclotomic orthomorphisms, Electron. J. Combin. 12 (2005) R22.
  3. I. M. Wanless and E. C. Ihrig, Symmetries that Latin squares inherit from 1-factorizations, J. Combin. Des., 13 (2005) 157-172.
  4. B. M. Maenhaut and I. M. Wanless, Atomic Latin squares of order eleven, J. Combin. Designs, 12 (2004), 12-34.
  5. 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.
  6. I. M. Wanless, Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles, Electron. J. Combin. 6 (1999) R9.