Re: Pair Up in Threes

• From: reelgore <no_reply_at_yahoogroups.com>
• Date: Mon, 25 Mar 2002 23:30:03 -0000
• Message-ID: <a7obtr+sboj_at_...>

Looks like nobody here ever answered this question from last August.
(It's not equivalent to the FAQ I usually answer)

An answer follows the quote ...

--- In quizbowl_at_y..., cooterchekov wrote:
> I now turn my attention, however, to the
> idea of QB tournaments played with three teams at
> once, with an ultimate hope of being able to generate
> pairings for tournaments in fours, fives, and so on --
> mostly I'm thinking of singles events here. So far I
> can:

- Generate a list of all the unique possible
> games
- Create complete schedules (ones using every
> possible combination) for from three to six
> teams.

And now I'm stuck. Anyone have experience with
> creating this kind of schedule?

It's enough to find a "factorization of the complete k-uniform
hypergraph on nk vertices" where k is the number of teams in each
game, and nk is the number of teams in the tournament, padded with 
bye teams if necessary.

Baranyai's Theorem states that such a factorization always exists,
but his proof is not constructive.  Explicit constructions, for
general n, are known for k=2 and k=3, but apparently not for k>3.
At least as of 1998, when the referenced article was posted.

-RL

Reference:
http://www.mathematik.uni-bielefeld.de/~tamm/commo
n/pub/tamm/baranyai.ps