Matching in an inclusion graph
Task number: 4004
Grapg \(G_{n,a,b}\) for positive integers \(a, b \leq n\), \(a \neq b\) is defined as:
\(\displaystyle V(G_{n,a,b}) = \{X : X \subseteq \{1{,}2, …, n\}, |X| \in \{a,b\}\}, \)
\(\displaystyle E(G_{n,a,b}) = \{XY: X \subset Y\}. \)
In dependence on \(a\), \(b\) and \(n\) determine the size of the maximum matching in this graph.
Solution
The graph \(G_{n,a,b}\) is bipartite, with classes \(A\), \(B\), where the vertices of \(A\) correspond to the \(a\)-element sets prvkovým, and analogously vertices of \(B\) correspond \(b\)-element ones.
All vertices of \(A\) have the same degree and also all vertices of \( B \). In such graphs, the maximum matching contains all the vertices of the smaller set, because:
If without loss of generality \( |A| \le | B | \), and the vertices of \( A \) have the degree \( d \), then the vertices of \( B \) have the same or smaller degree. With any \( I \subseteq A \) exactly \( d | I | \) edges are incident, i.e. \( |N(I)| \ge \frac{d|I|}d \), and therefore the Hall condition is satisfied.
Answer
The maximal matching of the graph \(G_{n,a,b}\) has \(\min\{\binom{n}{a},\binom{n}{b}\}\) edges.
