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.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email