On Rooks, Marriages, and Matchings or Steinhaus via Hall

Abstract

In 1957 Hugo Steinhaus published an elementary, recreational problem concerning a configuration of rooks on the chessboard (Steinhaus in Matematyka, czasopismo dla nauczycieli 1:55, 1957). Over the last 60 years, this problem has achieved quite a peculiar status: apparently, it had two (both published) solutions—one short and elegant (Steinhaus in Sto zadań [One Hundred Problems], PWN, Warszawa, 1958), but (as it soon turned out) incorrect (Zadania konkursowe, Rozwiązania [Competition problems, Solutions]. Matematyka, Czasopismo dla nauczycieli 4–6:62–65, 1958); while the other (Zadania konkursowe, 1958) (Steinhaus in One Hundred Problems in Elementary Mathematics. Popular Lectures in Mathematics, Pergamon Press, Oxford and PWN, Warszawa, 1963)—known internationally, yet long and complex, so probably never read (except, perhaps, by its author) and never checked for its correctness. It was only in 2004 when a correct and short solution of the original Steinhaus’ problem was found and published (Morawiec in Matematyka Czasopismo dla nauczycieli 2:46–50, 2004). The solution involved the well-known Hall’s ‘marriage’ theorem (Wilson in Introduction to Graph Theory, Longman, Harlow, 1996, p. 113). Further investigation has shown that the connection between Steinhaus’ problem and Hall’s theorem runs deeper than the use of the latter in the solution of the former. In this paper we present the results of this investigation, by the way defining a simple but seemingly new class of special matchings (ibid.) in bipartite graphs (id., p. 18).

1 Rooks: The Problem

Although Hugo Steinhaus (1887–1972) was one of the biggest names in Polish mathematics, and in Wrocław in particular (on Steinhaus and his biography see e.g. [13, pp. 11–24], [1, 15, 3, pp. 21–26, 291–298]) we do not usually associate him with graph theory. On the other hand, he was well-known for his interest in elementary and recreational mathematics ([13, pp. 14–15, 17], [11, p. 4]) on which he wrote several books (see [13, pp. 25–44] for a complete list of Steinhaus’ publications, and [7, p. 2], [8, p. 2], [9, p. 2] for those in English recommended for various school libraries). Since many problems in those branches of mathematics often involve natural numbers or other elements of discrete mathematics, no wonder that sometimes graphs or other finite, combinatorial structures pop up, even if unexpectedly, in solutions of such problems. This paper illustrates that phenomenon, as it starts with a problem from elementary mathematics, with no apparent link to graph theory, and ends with one of the ‘most famous’ theorems from finite combinatorics, viz. Hall’s ‘marriage’ theorem [16, p. 113].

The problem we are going to present and discuss here was formulated and posed by Steinhaus towards the end of the 1950s. The international reader could familiarize with it for the first time in 1963, when Steinhaus published his “One Hundred Problems in Elementary Mathematics” [12, p. 37], an English translation of his “Sto zadań” that had appeared in Poland still in 1958 [14, pp. 40–41]. There, in Chapter V “Problems on chess, volleyball and pursuit”, you could find the following problem:

79. Rooks on the chessboard

The chessboard we shall consider has as many rows as columns, but differs from the usual one in the distribution of the white and black squares, which is arbitrary with the following restrictions: every column has at least one white square, and at least one column is entirely white. We shall say that we have succeeded in placing the rooks on the chessboard (we have a sufficient number of pieces not to run short of them), if we satisfy the following conditions: (1) the rooks are placed on the white squares, (2) at least one rook is placed on the chessboard, (3) the rooks do not attack each other (i.e. they are not standing in such a way as to be able to capture each other), (4) every white squares not occupied by a rook, but attacked horizontally by a rook, is also attacked vertically by some rook. Prove that it is always possible to place the rooks according to conditions (1), (2), (3) and (4).

Then, “One Hundred Problems” proposes also a solution of this problem, a solution five pages long, four of which are solid text, while the remaining one contains six figures [11, pp. 157–161]. Thus, one may sincerely doubt that anyone (beside its author) has ever cared to read it, let alone to understand it. That was one reason why we have attempted to find another—possibly simpler and shorter—solution of the problem [4]. Another reason lies in the fact that when Steinhaus himself first published a solution of it (in Polish), he presented it with quite a different solution—short and elegant [14, pp. 179–180]. Unfortunately, that solution was as short and elegant, as it was incorrect, although we will not deal with it here (for the history—see [4]; for the critique—[5]). Instead, we will move first to presenting a new solution, then to discussing its theoretical background.

2 Rooks and Marriages: The Solution [4]

Notice that if we manage to arrange rooks on a chessboard as required by conditions (1)–(4) of the original Steinhaus’ problem above, then the board and the configuration will satisfy the following condition (*):

There exists a non-empty set of rows of the board such that each of them contains at least one white square, and all white squares contained in those rows lie in at most the same number of columns as there are rows in the set.

The necessity of that condition should be obvious—the set of rows mentioned in it consists exactly of the rows the rooks were placed on. As we will show it below, that condition is also sufficient for a board to admit a configuration of rooks as required by Steinhaus’ problem.

Suppose otherwise. Then there exists a board as described in the problem which satisfies the above condition (*), but does not admit the required configuration of rooks. Next, by the Minimum Principle, there is among those boards one with a minimum number of rows. Let’s pick one such board, and denote the number of its rows by m. Since the board is a minimal—with respect to the number of rows—counterexample to the sufficiency of the condition (*) above, it cannot have any non-empty proper subset of rows such that each of those rows contains at least one white square, and that the number of columns the white squares of the rows are in does not exceed the number of those rows. This means that (a) every proper non-empty set of rows of that board that consists of rows containing at least one white square each requires greater number of columns to cover all the white squares in that set; (b) all the white squares of all the rows of the board occupy no more than m columns, as the board satisfies the condition (*).

In particular, it follows from (a) that every set of m-1 rows requires at least m columns to cover all of its white squares. All the more, the set of all m rows requires at least the same number of columns, and by (b) this means that the white squares of all the rows lie in exactly m columns. Thus, a minimal counterexample board satisfies the assumptions of the ’rook variant’ of Hall’s ’marriage’ theorem in which we identify rows with boys, columns with girls, white squares with acquaintanceship, and rooks with marriages. Consequently, the board has a row perfect matching ([16, p. 113], where such a matching is called ’complete’), i.e. configuration of m mutually non-attacking rooks, one in every row. And as there are m columns that cover all the white squares of all the rows of the board, all those white squares are attacked vertically by those rooks. So, we have managed to place the rooks as required by Steinhaus’ problem on the board that supposedly had no such placement. This contradiction closes the proof. $\square$

If the reader abhors ’negative’ proofs by contradiction then he should be able to easily translate the above proof into a ’positive’ one by the Principle of Mathematical Induction.

Notice that in our proof of the necessity and sufficiency of the condition (*) for a chessboard to have a required configuration of rooks we have not used either of the following two assumptions:

• the board is square (“The chessboard we shall consider has as many rows as columns...”);

• one column on the board is white (“...at least one column is entirely white”).

Thus, in fact, we have proven the following theorem, more general than that contained in the original Steinhaus’ problem:

Theorem 1

(Rooks) The chessboard we shall consider is a rectangular board of rows and columns. It further differs from the usual one in the distribution of the white and black squares, which is totally arbitrary with the following restriction: there is at least one white square on the board.

Then, we will succeed in placing the rooks on the chessboard (we have a sufficient number of pieces not to run short of them), so that the placement satisfies the following conditions:

• 1. the rooks are placed on the white squares,

• 2. at least one rook is placed on the chessboard,

• 3. the rooks do not attack each other (i.e. they are not standing in such a way as to be able to capture each other),

• 4. every white squares not occupied by a rook, but attacked horizontally by a rook, is also attacked vertically by some rook

if and only if

there exists a non-empty set of rows of the chessboard such that each of them contains at least one white square, and all white squares contained in those rows lie in at most the same number of columns as there are rows in the set.

It is easy to see that if a chessboard is as in the original Steinhaus’ problem, i.e. square with at least one column entirely white, it evidently satisfies the above (necessary and) sufficient condition for the board to have the required placement of rooks. Consequently, we obtain a new solution to Steinhaus’ old problem as a corollary to the theorem above.

We close this section with another formulation of the above theorem. As in its proof we used Hall’s ‘marriage’ theorem, and in what follows we will be referring to that theorem again and again, below we present our theorem in the (biased—patriarchal, in this respect cf. [2, 6]) ‘matrimonial’ setting.

Theorem 2

(= Theorem 1 (marriages)) There is a finite set of boys, each of whom knows several girls. The individual arrangement of acquaintanceship relations is totally arbitrary with the following restriction: there is at least one pair of acquaintances.

Then, we will succeed in marrying the boys, so that the marriages satisfy the following conditions:

• 1. each husband knows his wife,

• 2. there is at least one marriage,

• 3. the marriages are monogamous and monoandrous,

• 4. all girls known to a married boy, got married too

if and only if

there exists a non-empty group of boys such that each of them knows at least one girl, and the number of girls known collectively by that group does not exceed the number of boys in it.

Notice that if the group satisfies Hall’s theorem with respect to the girls, i.e. if they all can marry the boys in such a way that each girl marries a boy she knows, then it also provides a solution to the ‘matrimonial’ version of Steinhaus’ problem, the husbands being the required set of boys. Thus, this comment indicates the existence of another connection between Steinhaus’ problem and Hall’s theorem.

3 From Rooks Towards Matchings: Transversals

Regardless of the guise of the problems above—be it chess or matrimony, the attentive reader has probably already noticed that their common mathematical background is simple binary relational systems or bipartite graphs [16, p. 18]. In the sections that follow, we are going to discuss Steinhaus’ problem in both contexts, starting with relational systems (transversals [id., p. 115]), as they offer an intuitive and easy intermediate step on the way from boards to graphs (matchings). On that way, we will see that the connection between Steinhaus’ problem and Hall’s theorem runs deeper than just the use of the latter in the solution of the former. To this end, we will employ the following terminology and definitions.

Let A and B be two (finite) non-empty sets. We will call their Cartesian product $A \times B$—a (rectangular) board. Further, we will call the sets $\{a\} \times B$, $a \in A$—columns, and $A \times \{b\}$, $b \in B$—rows, while ordered pairs $\langle a,b\rangle$—unit squares of the board. Finally, we will call the relational system $\langle A \times B; R\rangle$, where $R \subseteq A \times B$—a two-color board, with R interpreted as the set of white squares. As all boards considered further in the paper will be two-color, we will abuse the terminology and more often than not call two-color boards just boards.

With this terminology, we may proceed and introduce the following definitions:

Definition 1

We will call a board $\langle A \times B; R\rangle$Steinhaus (with respect to rows) iff it satisfies the four conditions formulated in Steinhaus’ problem, i.e. if and only if we can place rooks on the board so that

• 1. the rooks are placed on the white squares,

• 2. at least one rook is placed on the board,

• 3. the rooks do not attack each other (i.e. they are not standing in such a way as to be able to capture each other),

• 4. every white square not occupied by a rook, but attacked horizontally by a rook, is also attacked vertically by some rook;

i.e. iff there is $S \subseteq A \times B$ such that

• 1. $S \subseteq R$,

• 2. $S \ne \varnothing$,

• 3. S is a 1–1 function from $A' \subseteq A$ to B, i.e. $\langle a,b\rangle \in S$, $\langle a,d\rangle \in S \Rightarrow b = d$, and $\langle a,b\rangle \in S, \langle c,b\rangle \in S \Rightarrow a = c$, for every $a, c \in A'$ and $b, d \in B$,

• 4. $(\forall \langle a,b \rangle \in R\smallsetminus S)((\exists c \in A') \langle c,b\rangle \in S \Rightarrow (\exists d \in B) \langle a,d\rangle \in S)$.

Notice that these four conditions mean in particular that S is a non-empty transversal of the system $\mathcal {F} = \{R^{-1}[b]: b \in rngS\}$ (1–3) with the additional property that $R^{-1}[rngS] = S^{-1}[rngS]$ (4), where rngS is the range, or the set of values, of S, i.e. $rngS = \{b \in B: (\exists a \in A) \langle a,b\rangle \in S\}$. And as S is 1–1, so $S^{-1}[rngS] = domS$, where domS is the domain, or the set of arguments, of S, i.e. $domS = \{a \in A: (\exists b \in B) \langle a,b\rangle \in S\}$. Thus, the property $R^{-1}[rngS] = S^{-1}[rngS]$ means in fact that for Steinhaus boards we have $R^{-1}[rngS] = domS$.

Although it would be easy to formulate an analogous definition of Steinhaus board with respect to columns (you just need to replace condition (4) above with one saying that every white square not occupied by a rook, but attacked vertically by a rook, is also attacked horizontally by some rook), or even to introduce a notion of a symmetric (or unbiased) Steinhaus board, we will see it below that this would make things seemingly more difficult and clumsy to formulate. For the same reason, in what follows we will not consider symmetric Hall’s theorem, but use the ‘good, old’ biased, patriarchal version of it.

With the above definition of Steinhaus board, our main result from the previous section may now be stated as follows:

Theorem 3

(= Theorem 1 (transversal)) Let the system $\langle A\times B; R\rangle , R \ne \varnothing$, be a two-color board. Then $\langle A \times B; R\rangle$ is Steinhaus if and only if there exists a non-empty set $B' \subseteq B$ such that for every $b\in B', R^{-1}[b] \ne \varnothing$, and $|R^{-1}[B']| \le |B'|$.

Definition 2

Further, we will call a board $\langle A \times B; R\rangle$Hall wrt columns (biased again) iff it satisfies the conditions formulated in the following rooks-and-columns version of the marriage problem, i.e. if and only if we can place rooks on the board so that

• 1. the rooks are placed on the white squares only,

• 2. the rooks are placed in all the columns of the board,

• 3. the rooks do not attack each other,

i.e. iff there is $S \subseteq A\times B$ such that

• 1. $S \subseteq R$,

• 2. $domS = A$,

• 3. S is a 1–1 function from A to B.

Obviously, we may define in a similar manner the notions of Hall board with respect to rows, as well as unbiased Hall board, but as we won’t use them here, we leave it to the reader.

Now, we can formalize as follows the comment we made towards the end of the preceding section on the connection between Hall and Steinhaus boards.

Fact 1

If the board $\langle A\times B; R\rangle , R \ne \varnothing$, is Hall (wrt cols) then it is Steinhaus (wrt rows).

To close this section we will prove a theorem that describes yet another connection between Steinhaus and Hall boards. And as it gives a characterization of Steinhaus boards in terms of Hall ones, it perhaps reveals the connection between those boards.

Theorem 4

The board $\langle A\times B; R\rangle$, $R \ne \varnothing$, is Steinhaus (wrt rows) iff there is a non-empty set $B'\subseteq B$ such that $\langle R^{-1}[B']\times B'; R'\rangle$ is Hall (wrt cols), where $R'$ is the restriction of R to $R^{-1}[B']$, i.e. $R' = R \cap (R^{-1}[B']\times B')$.

Proof

$\Rightarrow$

Let $\langle A\times B; R\rangle$, $R \ne \varnothing$, be a two-color board, and assume it is Steinhaus (wrt rows). Then, by definition, there is $S \subseteq A\times B$ that witnesses this fact, i.e. such that $S \subseteq R$, $S \ne \varnothing$, S is a 1-1 function from $A' \subseteq A$ to B, and such that $R^{-1}[rngS] = domS$. Put $B' = rngS$ and consider $\langle R^{-1}[B']\times B'$; $R \cap (R^{-1}[B']\times B')\rangle$. Then, an easy definition check shows that this board is in fact Hall wrt cols.

$\Leftarrow$

Now, suppose that $\langle A\times B; R\rangle$, $R \ne \varnothing$, is a board with a non-empty set $B' \subseteq B$ such that $\langle R^{-1}[B']\times B'$; $R \cap (R^{-1}[B']\times B')\rangle$ is Hall (wrt cols). Again, by definition, this provides us with $S \subseteq R^{-1}[B']\times B'$ such that $S \subseteq R \cap (R^{-1}[B']\times B')$, $domS = R^{-1}[B']$, and S is a 1–1 function from $R^{-1}[B']$ to $B'$. Then, now it is even easier than before to check that S also witnesses that the board $\langle A\times B; R\rangle$ is Steinhaus (wrt rows). $\square$

Finally, notice that if a board $\langle A\times B; R\rangle$, $R \ne \varnothing$, is Steinhaus (wrt rows) and $A' \supseteq A$, then the board $\langle A'\times B; R\rangle$ is Steinhaus again. Thus, being Steinhaus is an ’upwards hereditary’ property of boards with respect to rows. This heredity suggests that minimal Steinhaus boards, i.e. Steinhaus boards without a proper Steinhaus row-subboard, might be of some particular interest for the description of the structure of Steinhaus boards. And the proof of Theorem 1 seems to indicate again yet another connection of Steinhaus boards with Hall ones in this respect.

Problem 1

Are minimal Steinhaus boards Hall, and vice versa?

4 Matchings: The Finale

As we already mentioned it at the beginning of the preceding section, the natural mathematical background for the problems we considered here seems to be simple relational systems $\langle A\times B; R\rangle$, where $R \subseteq A\times B$. Such systems have another natural and well-known mathematical interpretation that appeals quite strongly to our geometric intuition and imagination. This interpretation is bipartite graphs. Thus, we will finish the paper with a short review of its main results in this graph-theoretic context.

So, in this section we will interpret the system $\langle A\times B; R\rangle$, $R \subseteq A\times B$, $R \ne \varnothing$, as a bipartite graph in the most natural way, viz. with A and B—the separate (disjoint) sets of vertices, and R—edges between the vertices in A and B, i.e. as the graph $\langle A, B; R\rangle$.

Then, in analogy with the definitions of Hall and Steinhaus boards, we will call a graph $\langle A, B; R\rangle$Hall with respect to A (still biased) iff it has a complete (i.e. perfect) matching from A to B, i.e. iff it admits a solution to the (A-biased) marriage problem.

Next, we will call such graph Steinhaus wrt B iff it admits a solution to the original Steinhaus problem translated this time into the language of bipartite graphs. This in fact means that a graph $\langle A, B; R\rangle$ is Steinhaus wrt B if it has a non-empty matching $S \subseteq R$ from a subset $B'$ of B to A such that S covers all the A-ends of the R-edges that begin in $B'$.

Theorem 5

(= Theorem 1 (bipartite graphs)) Let the $\langle A, B; R\rangle$, $R \ne \varnothing$, be a bipartite graph. Then $\langle A, B; R\rangle$ is Steinhaus (wrt B) if and only if there exists a non-empty set $B' \subseteq B$ such that for every $b \in B', N[b] \ne \varnothing$, and $|N[B']| \le |B'|$, where $N[\cdot ]$ stands for the set of neighbors of a vertex or set of vertices.

Theorem 6

(= Theorem 4 (bipartite graphs)) The graph $\langle A, B; R\rangle$, $R \ne \varnothing$, is Steinhaus (wrt B) iff there is a non-empty set $B' \subseteq B$ such that the subgraph $\langle N[B'], B'; R'\rangle$ is Hall (wrt $N[B']$), where $R'$ is the restriction of R to $N[B']$, i.e. $R' = R \cap (N[B']\times B')$.