Matching problem in bipartite graphs between persons and clubs

Question

I have to solve a problem using bipartite graphs and matchings. The way I modeled it is to have a graph $G=(A \cup B, E)$, and have the vertices in $A$ represent persons and the vertices in $B$ representing clubs. Then, the edges represent club membership.

How can I find the smallest possible value of $K$ that guarantees there is an assignment that satisfies the following conditions?
1. A person can be member of at most 50 clubs
2. Each club must have a president (which is a member of the club)
3. A person can be president of at most 5 clubs
4 Each club must have at least $K$ members

Here is a reformulation I made of the problem in mathematical terms: What value of $K$ ensures that $G$ has a $B$-covering matching $M$ knowing:
1. $ \forall v \in A, deg(v) \leq 50$
2. $\forall v \in A, v$ is incident to at most 5 edges in $M$
3.$ \forall v \in B, deg(v) \geq K$

I know we need to find a matching (to model the presidency relation) in $G$ that contains every vertex from $B$ but I am unsure how to find the value of $K$ that ensures that such a matching can in fact be obtained. Any edge in the matching can be incident to no more than 5 vertices in A. How should I approach the next step of the problem? Thanks

Answer 1

Given a specific bipartite graph with edges representing club membership, the way you find the presidency matching is:

1. Replace $A$ by a set $A'$ which includes $5$ copies of every vertex of $A$ (that is, every person is duplicated $5$ times).
2. Find a $B$-covering matching (of the ordinary kind) in the bipartite graph $(A',B)$.

So the condition for when the presidential matching exists is given by applying Hall's theorem to $(A',B)$.

Now consider any subset $S \subseteq B$. There are at least $K|S|$ edges out of $S$ in the original bipartite graph $(A,B)$ and so there are at least $5K|S|$ edges out of $S$ in the modifed bipartite graph $(A',B)$. On the other hand, every vertex of $A'$ has degree at most $50$, so these $5K|S|$ edges cannot go to fewer than $\frac{5K|S|}{50} = \frac{K|S|}{10}$ different vertices.

So if we set $K=10$ (and require that every club has at least $10$ members) then $|N(S)| \ge \frac{K|S|}{10} = |S|$, so Hall's condition is satisfied, and there is a perfect matching in $(A',B)$, which gives us a $5$-to-$1$ matching in $(A,B)$.

(Note that in particular, this implies that $|B| \le 5|A|$: there are at most $50|A|$ edges out of $|A|$, so the average club has at most $\frac{50|A|}{|B|}$ members. But if we require every club to have at least $10$ members, then $\frac{50|A|}{|B|} \ge 10 \implies 5|A| \ge |B|$.)