3
$\begingroup$

I have been confronted with the following homework question:

Let $M$ be a table of size $N \times N$. A legal filling of $M$ with the numbers $\{1,\dots,N\}$ is one such that each cell of the table has exactly one number and each line and each row contains each number exactly once.

Prove that for any partial filling of $M$, of the first $0 < k < n$ rows, it is possible to completely fill $M$ in a legal way.

Hint: Use bipartite matching

$\endgroup$
3
  • $\begingroup$ Are you allowed to assume Hall's condition for a perfect matching? $\endgroup$ – almagest Jun 11 '16 at 10:01
  • $\begingroup$ @almagest I would suppose so because the hint given is to use bipartite matching. $\endgroup$ – Ashwin Ganesan Jun 11 '16 at 15:57
  • $\begingroup$ @almagest yes, I am allowed to assume Hall's condition $\endgroup$ – Nivolas Jun 12 '16 at 14:06
1
$\begingroup$

Given a table of size $k \times N$, construct a bipartite graph whose left vertices $c_1,\ldots,c_N$ correspond to the $N$ columns of the table and whose right vertices are $1,\ldots,N$. For each $i$, join $c_i$ to $j$ whenever $j$ does not occur as an entry in column $i$. In other words, the neighbors of $c_i$ are the numbers which do not appear in column $i$ of the given table.

Since the given table contains $k$ entries in each column (and so has $N-k$ entries missing in each column), each left vertex $c_i$ has valency $N-k$. In the given table, each entry has appeared $k$ times and so is missing from exactly $N-k$ columns. Thus, each right vertex $j$ in the bipartite graph has valency $N-k$. Hence, the bipartite graph is regular of valency $N-k$.

The bipartite graph which we constructed satisfies Hall's condition: any subset $S$ in the left vertex set has at least $|S|$ neighbors in the right vertex set. This is because $S$ is incident to $(N-k)|S|$ edges, and each right vertex is incident to exactly $(N-k)$ edges, whence the number of right vertices needed to cover $(N-k)|S|$ edges is at least $|S|$.

By Hall's theorem, the bipartite graph has a perfect matching. A perfect matching is a set of $N$ edges which gives the entries for the next row of the table. This process can be repeated to complete the table. We have shown that any $k \times N$ Latin rectangle can be completed to a Latin square.

$\endgroup$
2
  • $\begingroup$ what promises that there are exactly n-k such matchings? Is that part of the fact that the graph has a regular valency of n-k? $\endgroup$ – Nivolas Jun 12 '16 at 15:33
  • 1
    $\begingroup$ yes. When the valency is $N-k$, there exists a perfect matching. Remove this perfect matching from the graph. The resulting graph is again regular, of valency $N-k-1$. So it too has a perfect matching. Repeat this process until we end up with a 1-regular graph, which is a perfect matching. $\endgroup$ – Ashwin Ganesan Jun 14 '16 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.