Hall's Theorem

In 1935, the mathematician Philip Hall discovered a criteria of a perfect matching on a bipartite graph, known as Hall’s theorem, aka marriage theorem.

Considering two sets of vertices, denoted as A=\{a_1, \cdots, a_m\} and B=\{b_1, \cdots, b_n\}. Edges are connected between a_i and b_j for some pairs of (i, j). Here, we admit multiple edges between two vertices. This graph, named as G, is called a bipartite graph. One may think the bipartite graph as a model of a marriage system. Taken set A and set B as boys and girls, an edge between a boy and a girl tells that they might be a couple. A natural question arises that whether there exists a perfect matching, that is, every boy can find his girl without conflicting with other boys. Put formally, a perfect matching is an injective map from A to B which induces a subgraph of G.

Hall’s theorem asserted that there is a perfect matching in above bipartite graph G if and on if for every subsets S of A, the cardinal number of S(number of the members in a set) does not exceed the number of the neighbors of S. Here, the neighbors of S are all vertices in B which are connected with one vertex in S.

The necessary condition apparently holds. On the other hand, the proof of the sufficient part is a little bit tricky. Challenge yourself with this problem.

Now we represent several applications of Hall’s theorem.

  • Let A=(a_{ij}) be a matrix of order n with nonnegative integers as entries, such that every row and column of A has sum l. Then A is the sum of l permutation matrices.
  • Suppose all vertices of a directed graph G have the same in-degrees and out-degrees of l, a fixed positive integer. Thus the graph can be separated as l groups of circles. Every vertex appears exactly once in each group, and each edge appears in only one circle.
  • (Birkhoff-von Neumann theorem) A doubly stochastic matrix, is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Assertion: every doubly stochastic matrix is mere a convex combination of permutation matrices.

The first two questions are equivalent with each other if one noticed the relation between a graph and its adjacent matrix. In addition, in the first problem, we construct a bipartite graph G consisting of 2n vertices, u_1, \cdots, u_n and v_1, \cdots, v_n and a_{ij} edges between each pair of vertices u_i and v_j. It can be easily verified that this graph meets the condition required in Hall’s theorem through contradictory argument. Thus we get a perfect matching in this graph, which conversely represent a permutation matrix. After Eliminating the perfect matching in this graph, it become to the situation of l-1 in-degrees and out-degrees. This allows us to use mathematical induction on the parameter l.

If the entries of the matrix are all rational in the third problem, the result is reduced to the first problem. Still, we shall cover the gap between rational numbers and reals. Denote all permutation matrix as M_1, \cdots, M_{n!}. For each matrix (a_{ij}) meets the requirement that the sum of each row or each column is 1, one can approach it by (a_{ij}^n) with rational entries which is also doubly stochastic. Thus we can decompose the rational matrix (a_{ij}^n) into a convex combination of permutation matrices with rational coefficient c_k^n, where k \in \{1, \cdots, n!\}. By finding convergent subsequence in each (c_k^n)_{n=1}^\infty, one can require that all these subsequences are convergent for the same indices, and they converge to a limit c_k. After all, the original matrix (a_{ij}) can be expressed as a convex combination of permutation matrices with coefficients c_k.



我:今天数论课,宗教授说:“我的老师是 Hlawka,他的老师是 Furstenberg,再上去就是 F. Klein 了。算下来,我也是师出名门。我认为这很重要,所以每次有同学要我写推荐信,我都告诉他们不要太在乎学校好不好,关键找一个好的导师。

室友:至少你现在修了数论课,也算是宗教授的学生了,和 Klein 也就差四代。

我:那我现在岂不是装备一把麒麟弓就能打到 Klein 了!













结果无人回应,我仔细看了一下那个教学平台,上面写着“思修 5 班”。





应院学生会学习部的邀请,今天在二教 309 做了一个小型的讲座,在我前面是邓老师和田学长,陈学长给大家讲座。我一直感觉到我讲的时候基本就没有什么可讲的了,不过还好,因为我比较偏重的是整体团队的管理和时间的管理。我想建模的具体细节应该是同学自己去体会的,只需要告诉大家几条原则就可以,而数院的同学可能会在偏重技术细节,而放松了其他方面的管理,所以我想我的这个切入点可能让更多的同学获益。这个是我讲座的演示文档:“江泽涵杯”数学建模与计算机应用竞赛讲座

为了方便大家更好的了解文章的结构和插图表格的比较好的范例,我将 2008 年“江泽涵杯”数学建模与计算机应用竞赛一等奖的论文:2009 年“江泽涵杯”数学建模与计算机应用竞赛一等奖论文和 2009 年与 2010 年美国数学建模竞赛获得 Meritorious 的论文:2009 年美国数学建模竞赛 Meritorious 论文2010 年美国数学建模竞赛 Meritorious 论文发给大家参考。