I think they're called one factorizations Yes K_2n always has a one-factorization, with 2n-1 "factors", that's a folk theorem. I'm not sure about cyclic ones There's a notion of orthogonality between one factors---the orthogonality property is that they should have at most one edge in common. below, Stuff I copied from a 1985 paper by dinitz/wallis I just found: orthogonal one-factorizations of complete graphs correspond to "room squares" just like orthogonal one factorizations of bipartite graphs corrspond to latin squares For Michael's case, k_6, it admits fifteen one factors and six one-factorizations; each factor lies in exactly two factorizations and any two factorizations have exactly one factor in common; the six factorizations are isomorphic. So there is one factorization up to isomorphism, so no pairs of orthogonal factorizations, up to order 6. I think there's a relationship to the outer automorphism of K_6? k_8 has six non-iso one factorizations, k_10 has 396 and four mutually orthogonal ones it's known that the # of mutually orthogonal ones goes to infinity Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/ehome.htm ----- Original Message ----- From: "Michael Kleber" <kleber@brandeis.edu> To: <math-fun@mailman.xmission.com> Sent: Monday, September 15, 2003 8:16 AM Subject: [math-fun] round robin
Hi Funsters,
Surely this is well known, but somehow not to me. How do you arrange round robin tournament pairings?
I actually needed to do it for six teams, and after a little doodling I came up with a pretty symmetric- looking pairing scheme. Numbering points in cyclic order, you pair 1-2 3-4 5-6 and its (one) cyclic shift, and pair 1-4 2-6 3-5 and its (two) cyclic shifts. The first two match each person with the two sitting on either side of them, and the last three match each person with their antipode and antipode's neighbors.
Is it always possible to do this? (Where "this" is a set of pairings that's invariant under cyclic shifts.)
For an odd number of people, I can certainly come up with one. Number the people from -n to n, and have each k play -k, with 0 sitting out. This plus its cyclic shifts (just adding mod n) do the job, and it's easy to see why -- draw the people in order in a circle, and each round's pairings are a full family of parallel lines.
For any even number of players, you can run the above scheme, with one distinguished person playing againt the guy who would have sat out above. But I don't like singling someone out like that. (Though I guess you can still draw asymmetric-looking picture of it, by having the distinguished person sitting in the middle of the circle.) But is there always a way that's as symmetric as the 6-person example?
And of course there are the counting questions: in how many different ways (modulo renaming the players, of course!) can you pair people up, both in general and with the symmetry requirement. I looked in the EIS for round-robin and didn't get any answers.
Okay, now you can all tell me how well-known all this is.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun