Bipartite matching to construct schedule

601 Views Asked by At

Follow the hint below to construct a schedule for the matches in a league of $2n$ teams which meets the following constraints:

a) In each round each team plays exactly one match.

b) In the end each team must have played against each of the other teams exactly once.

Hint: Consider the graph $K_{2n}$ on the vertex set $\{1, 2, ..., 2n\}$ and show that each of the sets $M_i=\{1i\} \cup \{xy | x + y \equiv 2i $ mod $2n -1$ and $x \neq y$, $x \neq 1$, $x \neq i$, $y \neq 1$, $y \neq i\}$ is a perfect matching (for $i = 2,...,2n$).

I assume I will need to divide the $2n$ vertexes into a complete bipartite graph of $K_{n,n}$, so actually if each vertex corresponds to a team, it means that each team will play each other. But, I have no idea whether this is correct, or how to proceed. Any ideas?

1

There are 1 best solutions below

0
On BEST ANSWER

Each perfect matching for $K_{2n}$ can be thought of as a bipartite graph with two parts of size $n$, but that has no real bearing on the problem. What you want to do here is think of each of the $2n-1$ matchings $M_i$ for $i=2,\ldots,2n$ as specifying the pairings in one round of the tournament.

The first step is to show that each $M_i$ really is a perfect matching of $K_{2n}$: if that’s true, then each team plays $2n-1$ matches. Then you need to show that each team plays each of the other teams. Since each team plays $2n-1$ matches, and there are $2n-1$ other teams, this guarantees that each team plays each other team exactly once.

Let’s take a closer look at the set of edges $M_i$, where $2\le i\le 2n$:

$$M_i=\{1i\}\cup\big\{xy:x+y\equiv 2i\pmod{2n-1}\text{ and }x\ne y\text{ and }\{x,y\}\cap\{1,i\}=\varnothing\big\}\;.$$

The condition that $\{x,y\}\cap\{1,i\}=\varnothing$ ensures that none of the edges in the second set on the righthand side is incident to vertex $1$ or vertex $i$. Now suppose that $uv,xy\in M_i\setminus\{1i\}$; then $u,v,x,y\in[2n]\setminus\{1,i\}$, $u\ne v$, $x\ne y$, and $u+v\equiv 2i\equiv x+y\pmod{2n-1}$. We want to show that either $uv$ and $xy$ are the same edge, or they have no vertex in common, so suppose that $u=x$; we want to show that this forces $v=y$.

It definitely implies that $v\equiv y\pmod{2n-1}$, since $u+v\equiv x+y\pmod{2n-1}$. There is no harm in assuming that $v\le y$, in which case we have $2\le v\le y\le 2n$, and hence $y-v\le 2n-2$. And since $v\equiv y\pmod{2n-1}$, we know that $2n-1\mid y-v$. What does this tell you about $y-v$?

It should be very clear that team $1$ plays each other team: it plays team $i$ in the round whose pairings are given by the matching $M_i$. Suppose that $x$ and $y$ are two teams other than team $1$; we need to show that they play each other, i.e., that $xy$ appears in one of the matchings $M_i$. In other words, we need to show that there is an $i\in[2n]\setminus\{1\}$ such that $x+y\equiv 2i\pmod{2n-1}$. If $x+y$ is even, this is easy. If $x+y$ is odd, note that $x+y+2n-1$ is even, and use this to find a suitable $i$.