Home MATH 340 Tuesday, January 14, 2014

Tuesday, January 14, 2014 CC-BY-NC
Applications of Hall's theorem

Maintainer: admin

1Regular bipartite graphs

A bipartite graph is $d$-regular if $\deg(v) = d$ for any $v \in V$ (so all the vertices have the same degree, $d$).

Theorem: a $d$-regular, bipartite graph can be decomposed into $d$ edge-disjoint perfect matchings.

Proof: by induction on $d$. In the base case, let $d=1$. Then each vertex is adjacent to exactly one edge. So if we just take all the edges, we have a perfect matching. Done.

Now, consider some arbitrary $d$-regular, bipartite graph $G$. Suppose it has a perfect matching $M$. (We'll justify this assumption later.) Then, $G \setminus M$ is a $(d-1)$-regular graph (since $M$ has a degree of 1 for each vertex). By the induction hypothesis, $G\setminus M$ can be decomposed into $d-1$ edge-disjoint perfect matchings. Then, we just take these $d-1$ matchings and throw in $M$, and we get $d$ edge-disjoint perfect matchings for $G$.

Now we just need to show that an arbitrary $d$-regular, bipartite graph has a perfect matching. We can do this by proving that Hall's condition holds. First, we need to show that $|X| = |Y|$. Well, since $G$ is bipartite, we have that

$$\sum_{x \in X} \deg(x) = \sum_{y \in Y} \deg(y) = |E| \tag{the number of edges}$$

since edge contributes once to $X$, and once to $Y$. But since $G$ is $d$-regular, all vertices have the same degree, so $d|X| = d|Y|$ and thus $|X| = |Y|$.

Next, we need to show Hall's condition. Take any subset $A \subseteq X$, and consider $|\Gamma(A)|$, i.e., the size of its neighbourhood. Now, the total number of edges leaving $A$ is $d|A|$. The same number of edges enters $\Gamma(A)$. Since all the vertices have the same degree, it must be that $|\Gamma(A)| = |A|$. Thus Hall's condition is satisfied. $\blacksquare$

2Latin rectangles and squares

A Latin rectangle is a $r \times n$ grid (with $n > r$) containing some subset of the numbers $1, \ldots, n$ such that each number only appears at most once in each row and column.

Theorem: every Latin rectangle can be extended to get a $n \times n$ Latin square.

Proof: Consider a bipartite graph with a vertex in $X$ for each column and a vertex in $Y$ for each number. We create an edge between a column and a number if the number is not in the column.

The resulting graph is bipartite and 2-regular (in general, the graph is $(n-r)$-regular). Thus, by the theorem in the previous section, it decomposes into 2 disjoint perfect matchings. We can make these matchings the new rows in the table to get our Latin square, as desired. $\blacksquare$

3Graph-colouring

An edge-colouring is a function $c: E \mapsto \mathbb N$ such that $c(e_1) \neq c(e_2)$ for any $e_1, e_2$ that share a vertex.

The edge-chromatic number $\chi^E(G)$ for a graph $G$ is the minimum number of colours needed to fully edge-colour that graph.

The edges $E_i$ of colour $i$ form a matching (not necessarily perfect).

Note that $\displaystyle \chi^E(G) \geq \max_{v\in V} \deg(v) = \Delta(G)$ (where $\Delta$ is defined as the max degree in the graph, and $\delta$ is defined as the minimum degree in the graph).

3.1In bipartite graphs

Theorem: in a bipartite graph, $\chi^E(G) = \Delta(G)$.

Proof: Add dummy edges and nodes until we get a $d$-regular graph where $d=\Delta(G)$. Then, we decompose it into $d$ perfect matchings, and we can just ignore the dummy nodes/edges.

How do we add the dummy edges? First, we repeatedly add edges between vertices of degree $< \Delta(G)$, until we get those to $\Delta(G)$. If $|X| = |Y|$, and we get to a point where every vertex in $X$ has degree $\Delta(G)$, then so does every vertex in $Y$. On the other hand, if $|X| < |Y|$, we can just add new dummy nodes in $X$ and connect the new edges to those. It's pretty straightforward, so I'm not going to formalise this. $\blacksquare$

Corollary of proof: If $|Y| > |X|$ and $|\Gamma(A)| \geq |A|$ for all $A \subseteq X$, then there exists a matching $M$ that touches every vertex in $X$.

3.2In non-bipartite graphs

Theorem (Vizing, 1964): In a non-bipartite graph, $\Delta(G) \leq \chi^E(G) \leq \Delta(G) + 1$.

The proof is outside the scope of this course, but it uses the augmenting path technique that we saw earlier in an earlier lecture.

3.3Applications

  • Assigning lectures to rooms
  • Scheduling games
  • Assigning pilots to planes
  • Assigning things to other things, in general

4Systems of distinct representatives

Suppose $Y$ is a set, and $S_1, \ldots, S_n$ are subsets of $Y$. A set $D = \{y_1, \ldots, y_n\}$ is a system of distinct representatives (SDR) if $y_i \in S_i$ for all $1 \leq i \leq n$ and $y_i \neq y_j$ for $i \neq j$. In other words, each $S_i$ is uniquely represented by one of its members, and nothing can represent more than one set.

Theorem: An SDR exists $\iff$ for all sets of size $k$ in $S_1, \ldots, S_n$, their union has size $\geq k$.

Proof: Create a bipartite graph. Let $x_i \in X$ have a neighbourhood $\Gamma(x_i) = S_i \subseteq Y$. There is an SDR if and only if $X$ is matchable. (So $Y$ is people, $X$ is groups.) There is an edge between a group and every person in that group. We need each vertex in $X$ to be matched. This occurs when $|\Gamma(A)| \geq |A|$ for all $A \subseteq X$, by Hall's condition, which is exactly when the union condition is matched. $\blacksquare$