A&W assignment 2

T2.1 Choosing Seminars

a) We model this problem into a bipartite graph $G=(A+B,E)$ Let each student be a vertex in set $A$, and each seminar be a vertex in set $B$ we now make a new graph $G=(A+B^{\prime },E)$ where $B^{\prime }$ contains 13 copies of $B$ (each seminar appears 13 times in $B^{\prime }$) There is an edge between $a\in A$ and $b\in B^{\prime }$ if and only if student $a$ applied for that seminar. Now the problem becomes “Can we find a matching in graph $G^{\prime }$ with size $|A|$” The Hall’s Theorem tells us there is such matching if and only if $\forall X\subseteq A:|X|\le |N(X)|$ under graph $G^{\prime }$ $⟺\forall X\subseteq A:|X|\le 13|N(X)|$ under graph $G$ (since any $|N(X)|$ in $G^{\prime }$ contains $\frac{|N(X)|}{13}$ seminars) Now we prove this claim under graph $G$. For any subset $X\subseteq A$, there are exactly $3|X|$ outgoing edges. for any $|N(X)|$ we will have at most $40+40+39(|N(X)|-2)=39|N(X)|+2$ edges So we must have $3|X|\le 39|N(X)|+2$ $⟹|X|\le 13|N(X)|+\frac{2}{3}$ Since we cannot have fractional number of edges, we get $⟹|X|\le 13|N(X)|$ This proves our claim. Therefore, there must exists such an matching, which gives a possible valid assignment.

b) With at most 12 student each seminar it is impossible to always find an assignment. Counterexample: suppose we have $4$ seminars ($a$,$b$,$c$,$d$) and $4\ast 12+1=49$ students 21 students apply for $a,b,c$ 10 students apply for $a,b,d$ 9 students apply for $a,c,d$ 9 students apply for $b,c,d$ then we have $a=21+10+9=40$, $b=21+10+9=40$, $c=21+9+9=39$, $d=10+9+9=28$ This is a valid situation. However, if we choose the entire student set as $X$ then we have $|X|=49>48=12|N(X)|$. By using Hall’s theorem, we’ve shown that there is no matching of size $|A|$ (meaning a valid assignment is not possible)

T2.2 Augmenting path of length k

a)