7
$\begingroup$

This problem is tagged as difficult in my course notes and I am not sure how to start. How should I start proving it?

Problem:

Let $G$ be a bipartite graph with bi-partition $A$, $B$, where $|A|$ = $|B|$ = $n$, and suppose that every vertex of G has degree at least $\delta$ < n. Prove that $G$ has a matching of size at least the minimum of $n$ and ($q$ - $\delta^2$)/($n$ - $\delta$).

  • 0
    What does the variable $q$ represent?2011-07-23
  • 0
    @Autstin Oops its edges2011-07-23
  • 0
    @Mark: Please do not repost this question; we don't want unnecessary duplicates. What you can do instead is make a trivial edit to the body of the question, which will bump the question to the front page again. Note that after 10 edits, the question becomes [Community Wiki](http://meta.stackexchange.com/questions/11740/what-are-community-wiki-posts), which means that you won't get reputation from it. You can also put a [bounty on your question](http://math.stackexchange.com/faq#bounty) to attract potential answerers.2011-08-07
  • 0
    @Zev Chonoles: how do I add a bounty?2011-08-07
  • 0
    There appears to be some trick to solve this problem...2011-08-07
  • 0
    @Mark: That's explained in the link I put in my above comment. [Here it is again](http://math.stackexchange.com/faq#bounty), though, and here also is a [meta.SO explanation](http://meta.stackexchange.com/questions/16065/how-does-the-bounty-system-work/16067#16067).2011-08-07
  • 0
    @Zev: oops sorry I didn't see the link...2011-08-07
  • 0
    @Mark: You've added an answer as part of the question. Unless you're asking a question about this answer (which you don't seem to be doing), it would be preferable to add it as an answer (which it is).2011-08-08
  • 0
    @joriki: Ok I will do that2011-08-08

3 Answers 3

13

Update: There was an error in this proof – sorry about that. I've fixed it, and now the bound comes out as stated in the question. (The erroneous version had claimed a tighter bound.)


Let a bipartite graph $G$ be given. Choose some maximum matching of size $r$ and split $A$ and $B$ as $A_+\cup A_-$ and $B_+\cup B_-$, where $A_+$ contains the vertices in $A$ that partake of the matching and $A_-$ contains those that don't, and likewise for $B$. Let $k_A$ be the number of edges in the matching whose vertices in $A_+$ have edges to $B_-$ and $k_B$ the number of edges in the matching whose vertices in $B_+$ have edges to $A_-$. For any given edge in the matching, it cannot be the case that both its vertex in $A_+$ has an edge to $B_-$ and its vertex in $B_+$ has an edge to $A_-$, since otherwise we could replace the edge by these two edges and obtain a larger matching. Thus $k_A+k_B\le r$. Further, if a vertex $a_1\in A_+$ has an edge to a vertex $b_- \in B_-$, its partner $b_1$ in the matching can't have an edge to the partner $a_2$ of a vertex $b_2\in B_+$ that has an edge to a vertex $a_-\in A_-$, since otherwise we could replace the two edges $(a_1,b_1)$ and $(a_2,b_2)$ in the matching by the three edges $(a_1,b_-)$, $(b_1,a_2)$ and $(b_2,a_-)$ and obtain a larger matching. (If you haven't drawn a diagram yet, now might be a good time.)

We can now count the maximal number $q$ of edges: The $n-r$ edges in $A_-$ can have edges only to $k_B$ vertices in $B_+$, and the $n-r$ edges in $B_-$ can have edges only to $k_A$ vertices in $A_+$. The $r$ vertices in $A_+$ and the $r$ vertices in $B_+$ can have up to $r^2$ edges between them, except for $k_Ak_B$ edges between the partners of the vertices connected to $A_-$ and $B_-$. [This is where the error was; I'd subtracted another $k_Ak_B$ edges between those vertices themselves, not just their partners, but those edges can't be used to enlarge the matching.] Putting it all together, we have

$$ \begin{eqnarray} q &\le& (n-r)k_B+(n-r)k_A+r^2-k_Ak_B \\ &=& (n-r)(k_A+k_B)+r^2-k_Ak_B \\ &\le& (n-r)r+r^2-k_Ak_B \\ &=& nr-k_Ak_B\;. \end{eqnarray} $$

Enter $\delta$. All vertices in $A_-$ and $B_-$ must have at least $\delta$ edges, and they can only have edges to the $k_B$ vertices in $B_+$ connected to $A_-$ and the $k_A$ vertices in $A_+$ connected to $B_-$, respectively. Thus, either $A_-$ and $B_-$ are empty, in which case we have a perfect matching of size $n$, or we must have $k_A\ge\delta$ and $k_B\ge\delta$. Under these constraints, together with $k_A+k_B\le r$, we get the least possible value of $k_Ak_B$, and thus the largest possible value of $q$, for $k_A=\delta$ and $k_B=r-\delta$ or vice versa. Thus, unless there is a perfect matching,

$$ \begin{eqnarray} q&\le&nr-\delta(r-\delta)\;,\\ r&\ge&\frac{q-\delta^2}{n-\delta}\;. \end{eqnarray} $$

  • 0
    thanks for the detailed solution, I am going to need some time to read through this. Also, your tigher bound is the correct one, because the original copy of the question was wrong it should be your tigher bound.2011-08-08
  • 0
    @Mark: I don't understand. You write that it should be my tighter bound, but in your edit to the question, you've changed the bound to be even less tight than before, by subtracting $\delta^2$ in the numerator instead of just $\delta$. Which one is it?2011-08-08
  • 0
    So sorry it was $(q - δ^2)/(n - δ)$ according to the corrected version of the question. But isn't your bound $(q−2δ^2)/(n−2δ)$ similar? Should the technique be similar?2011-08-08
  • 0
    @Mark: No, that corrected bound is even weaker than the original bound, which was weaker than my bound. It's easiest to compare them in the forms with $n-\delta$ in the denominator, since then they differ only in the numerator, which is $q$, $q-\delta$ or $q-\delta^2$. The form you cite has $n-2\delta$ in the denominator and isn't similar to your corrected bound at all; consider what happens as $\delta$ goes to $n/2$. Regarding the technique: are you looking for a proof that "directly" gives your weaker bound? If not, you can just take my proof and then subtract $\delta^2$ to weaken the bound.2011-08-08
  • 1
    Would it be much easier to prove this even weaker bound ?2011-08-08
  • 0
    @Mark: Yes, a bit easier -- this is the bound you get if you don't make the more complicated argument about replacing two edges by three and only use the simpler argument about replacing one edge by two. Then you only subtract $k_Ak_B$ instead of $2k_Ak_B$, and when you then solve for $r$ you get this bound.2011-08-08
  • 0
    According to my notes there is a latter problem that says the bound $(q−δ^2)/(n−δ)$ can not be increased. Here is the statement: "Construct a bipartite graph with bipartition A, B, where |A| = |B| = 8, and having minimum degree 2, for which the size of a maximum matching is less than (q-3)/6. (This shows tht the value $(q−δ^2)/(n−δ)$ in the previous exercise, cannot be increased.)" Accordingly $(q−δ)/(n−δ)$ can not be true since $(q−δ)/(n−δ)$ > $(q−δ^2)/(n−δ)$... So does that mean your bound is not correct? I might be misunderstanding again.2011-08-08
  • 0
    @Mark: I guess it would mean that, yes. Have you found such a graph?2011-08-08
  • 0
    I can't use the example above, since I think it's not suppose to be greater than 82011-08-08
  • 0
    @Mark: I don't understand. What's not supposed to be greater than 8? Your notes seem to be implying that there is a graph with $n=8$, $\delta=2$ and $r<(q-3)/6$ -- either the notes are wrong or my proof is wrong. What do you mean by "I can't use the example above"?2011-08-08
  • 0
    I was referring to an incorrect graph in the comments which I have deleted. But I think this graph works: Consider a graph where in $A$ the first $6$ vertexes are degree $6$ (joined to first $6$ vertexes of $B$), $7$th vertex is degree $8$ and last vertex is degree $2$ (joined to the $6$th and $7$th vertex of $B$). So this graph has a maximum matching of size $7$ since minimum cover is $7$. now $n$ is 8 and $(46-3)/ 6$ $> 7$ which is not suppose to be true for the problem.2011-08-08
  • 0
    @Mark: The 8th vertex of $B$ only has one edge, so this has $\delta=1$ and $46/(8-1)<49/7=7$.2011-08-08
  • 0
    Looks like I am going to have to refer to the professor for the construction, but I am pretty sure the notes are correct since it has been used and edited for several semesters. Sorry about that.2011-08-08
  • 0
    What if I just join the last vertex of $B$ to $A$? would that produce a minimum cover of size 7?2011-08-08
  • 0
    @Mark: Actually, even the graph as you've specified it (with $\delta=1$) has a perfect matching: The first six vertices can be matched to each other, the 7th to the 8th and the 8th to the 7th. Regarding the notes: Yes, would be interesting to hear from the professor. It wouldn't be the first time that something that's been used and edited for several semesters contains an error :-) But it also wouldn't be the first time that I wrote a faulty proof; so we'll just have to see... You might want to send the professor a link to this page?2011-08-08
  • 0
    Hi joriki I have posted the proof from my professor. I will upload the counterexample as soon as I figure out what is going on.2011-08-08
  • 0
    @Mark: You (and your notes) were right; there was an error in the proof. I've fixed it and now the bound comes out right. I'm sorry to have wasted your time with that.2011-08-09
  • 0
    I think maximal and maximum are different. Maximal is your cant add one more edge. But maximum is no augmenting path. I think you refer to maximum instead of maximal.2011-12-10
  • 0
    @FiniteA: You're quite right -- thanks, I've corrected it.2011-12-11
1

Some discrete mathematics or combinatorics about maximal matchings in bipartite graphs would likely get you started:

  • Augmenting path algorithm for bipartite graph. An augmenting path in a bipartite graph can imply a matching.
  • Max-flow min-cut theorem
  • Perfect matchings in bipartite graphs

I hope that studying the above concepts can help you.

  • 0
    I know about 2 of the 3 theorems above, however I hit a brick wall when trying to apply them. Do you know how I could use the above to solve my problem? because I think I need to know some more techniques to solve the problem.2011-07-23
  • 0
    I can't solve the problem either, but I would have searched for matchings with the aforementioned algorithms for matching (if I remember correctly you have a matching if you have an augmenting path, so you need to show the size of the matching) using that the sets A and B have the same cardinality where maybe it's "obvious" that δ < n and minimum matching is n, so we need to find where the number (q - δ)/(n - δ) comes from. I would have inspected the algorithms for matchings and looked at maximal matchings and perfect matchings to get a notion for the minimal matching.2011-07-25
0

I got this proof from my professor during office hours:

enter image description here

Let $C$ be a minimum cover, and let

$$C_1 = |C\cap A|$$

and

$$C_2 = |C\cap B|\;.$$

So since the size of a maximum matching is equal to $|C|$, suppose by contradiction that

$$|C| < \min(n, (q - \delta^2)/(n- \delta))\;.$$

Then

$$C_1 + C_2 < n$$

and

$$C_2 \geq \delta, C_1 \geq \delta\;.$$

As there can't be any edges between $A\setminus C$ and $B\setminus C$, we can bound the number $q$ of edges by adding up all possible edges between $A\cap C$ and $B\setminus C$, between $A\setminus C$ and $B\cap C$ and between $A\cap C$ and $B\cap C$:

$$ q \leq C_1(n - C_2) + C_2(n - C_1) + C_1C_2\;.$$

He said this next step is the crucial move with a little wishful thinking. Basically he said he wants to turn

$$ q \leq C_1(n - C_2) + C_2(n - C_1) + C_1C_2$$

into

$$ q \leq C_1(n - \delta) + C_2(n - \delta) + \delta^2\;.$$

But we can't just replace $C_1C_2$ by $\delta^2$ since $\delta^2\leq C_1C_2$, so he used the fact that

$$ (C_1 - \delta)(C_2 - \delta) \geq 0$$

since $C_2 \geq \delta, C_1 \geq \delta$. So

$$ \begin{eqnarray} q &\leq& C_1(n - C_2) + C_2(n - C_1) + C_1C_2 \\ &=& C_1n+C_2n-C_1C_2 \\ &=& (C_1 + C_2)n - (C_1 + C_2)\delta + \delta^2 - (C_1C_2 - C_1\delta - C_2\delta + \delta^2) \\ &=& |C| (n - \delta) + \delta^2 - (C_1 - \delta)(C_2 - \delta) \\ &\leq& |C| (n - \delta) + \delta^2\;, \end{eqnarray} $$

and thus

$$|C| \geq (q-\delta^2) / (n - \delta)\;,$$

which contradicts our assumption that $|C| < \min(n, (q - \delta^2)/(n- \delta))$.

(He said this proof is not very constructive but somehow it works)


As for the example,

consider a graph where the first two vertexes in $A$ and $B$ has degree $8$. The rest of the six vertexes from $A$ join the 2 vertexes in $B$ and vice versa (so the minimum degree for each of the six vertexes is $2$). This graph has maximum match of size $4$ because the initial four vertexes from $A$ and $B$ are the minimum cover.

this is roughly the graph (if you don't mind the bad drawing):

enter image description here

So $q$ = $2 \times 6 + 2 \times 8 = 28$ edges.

So applying the bound $(28 - 4) / (8 - 2) = 4$ which holds since $|M| = 4$, but the tighter bound is $(28 - 8) / (8 - 4) = 5$.

  • 0
    Where you say "I am not sure how he derived this", he uses the fact that there can't be edges between the lower (non-shaded) parts of the diagram, since then $C$ wouldn't be a cover; the three terms correspond to the possible numbers of edges between the upper/lower, lower/upper and upper/upper parts, respectively. What I don't understand is what happens where you write "so he added this". What did he add to what? And how did this allow him to get around what you rightly pointed out, that $\delta^2\le C_1C_2$ and thus we can't get from the inequality with $C_1C_2$ to the one with $\delta^2$?2011-08-08
  • 0
    @joriki: I will double check with him again.2011-08-08
  • 0
    @joriki: I walked by his office and he is busy, I will try to get clarification tomorrow. Sorry for the wait.2011-08-08
  • 0
    @joriki: I have updated again. Please see if I need more clarifications.2011-08-08
  • 0
    @joriki: it seems he didn't need to get around it because $q \leq C_1(n - \delta) + C_2(n - \delta) + C_1C_2$ just needed some algebra to prove the bound.2011-08-09
  • 0
    Thanks for the counterexample, which is obviously correct. I found the error in my proof and have corrected it. I'm sorry to have wasted your time with this. I see how this proof works now, but part of how you've written it down is wrong: The equalities below "expanding below will get above" don't hold; what you're actually using is that $C_1(n - C_2) + C_2(n - C_1) + C_1C_2=|C| (n - \delta) + \delta^2 - (C_1 - \delta)(C_2 - \delta)$.2011-08-09
  • 0
    @joriki: I must have made an error copying it down. Anyways I have learned alot thanks for being so patient.2011-08-09
  • 0
    Your edit fixed the first equality after "expanding below will get above", but the third one is still wrong, and the flow of the argument doesn't really make sense -- if you agree, I'll fix it?2011-08-09
  • 0
    @joriki: please do2011-08-09
  • 0
    OK, I've fixed the equalities and also rearranged things a bit so that they make more sense to me -- obviously, feel free to change things back if you don't agree...2011-08-10
  • 0
    @joriki: I haven't noticed any change. The history of change didn't show you. Is there a bug or delay?2011-08-10
  • 0
    Sorry, I don't know how that happened; I guess I must have forgotten to click "Save Edits". I'll do it again...2011-08-10
  • 0
    OK, done. I think I did forget to save edits the last time around, because I can't remember thinking about what to put in the edit summary :-)2011-08-10
  • 0
    @joriki: awesome, thanks a lot, I have learned a great deal from you !2011-08-10