1
$\begingroup$

I am trying to prove the following statement (from book, page 317):

Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of matchings of size $k\le n$, be $m_k$. If $|E|>k$ then there exists an edge $e$, such that $\frac{m_{ne}}{m_k} \ge \frac{1}{n}$, where $m_{ne}$ is the number of matchings of size $k$, that do not include/contain edge $e$.

The book gives a hint to use pigeonhole principle. But I am only able to get a weaker result.
Each matching of size $k$, contributes towards a matching of size $k$ not containing an edge, for $|E|-k$ edges. Thus as there are in total $m_k$ matchings, it can be seen as distributing $(|E|-k)m_k$ balls in $|E|$ bins. Thus by pigeonhole principle there is a bin (an edge) with at least $\frac{(|E|-k)\cdot m_k}{|E|}$ matchings which do not contain it. That is there is an edge $e$ such that $$m_{ne} \ge \frac{(|E|-k)\cdot m_k}{|E|}$$ $$\frac{m_{ne}}{m_k} \ge \frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2}$$

How can I prove that the lower bound is at least $\frac{1}{n}$ for some edge ?

$\endgroup$
1
$\begingroup$

Your approach has been working well all along, only to miss the promising transformation at the last step.

Instead of $$\frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2},$$ we can proceed as $$\frac{|E|-k}{|E|} =1 - \frac{k}{|E|} \ge1- \frac k{k+1}=\frac1{k+1}.$$

Since $k\le n$, i.e., $\dfrac1{k+1}\ge\dfrac1{n+1}$, we are not far from the goal $\dfrac1n$.

It takes a bit more effort to reach the goal. I will leave it to you to complete.



Here is a slightly easier proof. It shows, except possibly for graphs where all edges are separated, we can increase $1/n$ to $1/2$.

Consider whether there are incident edges in $G$.

  • There are incident edges. Say, edge $e_1$ and $e_2$ are incident. Every matching (of size $k$) can contain at most one of them. So either at least 1/2 of the matching of size $k$ does not contain $e_1$ or at least 1/2 of the matching of size $k$ does not contain $e_2$. Note that $$1/2\ge 1/n.$$
  • There are no incident edges. Then there are at most $n$ edges. Since each matching does not contain at least one of the $|E|$ edges, we have , if $e$ is the edge that is absent from the most matchings of size $k$,$$\frac{m_{ne}}{m_k}\ge \frac{1}{|E|} \ge \frac{1}{n}.$$

$\checkmark$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.