## Matching in an inclusion graph

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.

The maximal matching of the graph $$G_{n,a,b}$$ has $$\min\{\binom{n}{a},\binom{n}{b}\}$$ edges.  