#8 Matching and Hall's Theorem Intro

Any two edges of the star share the centre, so a matching cannot contain two edges. One edge can be chosen. The answer is \(1\).

Matching edges have no common endpoints. Therefore the \(a\) covered left vertices are joined to \(a\) distinct vertices of the right part. Hence the right part has at least \(a\) vertices.

Each vertex of \(S\) is covered by its matching edge. These edges go to distinct vertices of the right part, and all these vertices lie in \(N(S)\). Therefore \(N(S)\) has at least \(|S|\) vertices.

For example, choose \(1\in A_1\), \(2\in A_2\), and \(3\in A_3\). All representatives are distinct, so this is a system of distinct representatives.

If two uncovered vertices are adjacent, that edge has no common endpoint with any chosen edge. It can be added to the matching, a contradiction.

For one club there are \(2\) options. For any two clubs, the union of lists contains all three names or at least two names. For all three clubs, the union is \(\{a,b,c\}\), of size \(3\). Hall's condition holds, so an SDR exists. For example, \(A_1\to a\), \(A_2\to b\), \(A_3\to c\).

Take any \(S\) in the left part. At least \(3|S|\) edges leave \(S\). All enter \(N(S)\), and each vertex of \(N(S)\) receives at most \(3\) such edges. Thus \(3|S|\le3|N(S)|\), so \(|N(S)|\ge |S|\).

Hall's condition holds, hence there is a matching covering the left part.

For any left-side set \(S\), exactly \(d|S|\) edges leave it. All enter \(N(S)\), and each vertex of \(N(S)\) has degree \(d\), so it receives at most \(d\) of these edges. Hence \(d|S|\le d|N(S)|\), so \(|N(S)|\ge |S|\). By Hall's theorem, the desired matching exists.

Delete an arbitrary element \(x\). Take any \(k\) sets. Before deletion, their union had size at least \(k+1\). After deleting \(x\), the union size decreases by at most \(1\), so at least \(k\) elements remain.

Hall's condition holds for the new family, so an SDR exists.

Remove from the matching the chosen edges of this path and add the unchosen edges of the path. Since the path alternates, the newly chosen edges still have no common endpoints.

The path starts and ends at uncovered vertices, so it has one more unchosen edge than chosen edges. Therefore the matching size increases by \(1\).

Build a bipartite graph: talks on the left, days on the right, and an edge means the talk may be scheduled on that day. The condition says that for every set \(S\) of talks, the neighbour set of days has size at least \(|S|\). By Hall's theorem, there is a matching covering all talks. It gives the schedule.

If representatives are chosen, then any \(k\) sections have \(k\) distinct representatives, all lying in the union of these sections. Therefore the union contains at least \(k\) students.

Conversely, the condition on unions is Hall's condition for the student sets corresponding to the sections. By Hall's theorem, an SDR exists.

Delete two right-side vertices. For any nonempty \(S\subseteq A\), its neighbour set loses at most two vertices. Hence the new neighbour set size is at least \(|S|+2-2=|S|\).

Hall's condition remains true, so there is a matching covering the left part.

For any left-side set \(S\), at least \(5|S|\) edges leave it. All enter \(N(S)\), and each right-side vertex receives at most \(4\) such edges. Thus \(5|S|\le4|N(S)|\), so \(|N(S)|\ge \frac54|S|\ge |S|\).

By Hall's theorem, there is a matching covering the left part.

Let the parts be \(A\) and \(B\). Counting edges by parts gives \(d|A|=d|B|\), hence \(|A|=|B|\).

By the regular bipartite graph argument, there is a matching covering \(A\). Since the parts are equal, it also covers \(B\). Therefore the matching is perfect.

Build a bipartite graph: an exam is joined to a day if it may be held on that day. We check Hall's condition.

For one exam, at least \(n-1\) days are available, and for \(n\ge2\) this is at least \(1\). If \(k\ge2\) exams are chosen, then every day is available to at least one of them: a day can be forbidden for at most one exam. Hence the union of available days is all \(n\) days, and \(n\ge k\).

Hall's condition holds for every set of exams. Therefore a schedule with distinct days exists.

By definition, an augmenting path starts and ends at uncovered vertices and its edges alternate. Switching the status of edges along the path preserves the matching property and adds one more edge than it removes. Thus the matching size increases by \(1\). Hence the original matching was not maximum in size.

If an augmenting path exists, switching along it increases the matching size, so the matching is not maximum.

Conversely, suppose there is a matching \(M'\) larger than \(M\). Consider the graph consisting of edges that belong to exactly one of \(M\) and \(M'\). In this graph, all degrees are at most \(2\), so its components are paths and cycles with edges from \(M\) and \(M'\) alternating.

Since \(|M'|>|M|\), in some component there are more edges from \(M'\) than from \(M\). A cycle has equal numbers of both types, so this component is a path. It starts and ends with edges from \(M'\), and its endpoints are uncovered by \(M\). Therefore it is an augmenting path with respect to \(M\). This contradicts the absence of augmenting paths.

A \(d\)-regular bipartite graph has a perfect matching. Remove its edges. Every vertex degree decreases by \(1\), so the remaining graph is \((d-1)\)-regular and bipartite.

Repeat the argument: find a perfect matching and remove it. After \(d\) steps all edges are removed, and the found matchings are pairwise disjoint and cover all edges.

Take any \(k\) sets. They contain at least \(rk\) element occurrences in total, because each set has size at least \(r\). Each element in their union can be counted at most \(r\) times, since it belongs to at most \(r\) sets overall.

If the union size is \(u\), then \(rk\le ru\), so \(u\ge k\). Hall's condition holds for any \(k\) sets. Therefore an SDR exists.