1
$\begingroup$

Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum matching w.r.t. the edge probability $p$? That is, given $p_1 < p_2$, can we show that $$\mathbb{E}[\text{size of a maximum matching}|p = p_1] + \mathbb{E}[\text{size of a maximum matching}|p = p_2] \leq 2\mathbb{E}\left[\text{size of a maximum matching}|p = \frac{p_1+p_2}{2}\right]?$$

Here "size of a maximum matching" refers to the number of edges contained in a maximum cardinality matching.

P.S. It seems that there are abundant results that show the sharp threshold of $p$ that leads to a perfect matching w.h.p., but I am surprised to find no result for the expected size of a maximum matching for a given $p$ below that threshold.

$\endgroup$
4
  • $\begingroup$ What do you mean by a number of matches? $\endgroup$ Sep 24, 2022 at 19:27
  • $\begingroup$ Thanks for the question! Here "number of matches" means the number of edges in a maximum cardinality matching. I've also clarified that in the question :) $\endgroup$
    – messi22
    Sep 24, 2022 at 20:37
  • $\begingroup$ It is not hard to prove the following: if $M$ is a matroid on the ground set $E$, and $X_p\subset E$ is a random subset with each element taken with probability $p$, then $p\to \mathbb{E}\, (\mathrm{rank}\,X_p)$ is a concave function. Unfortunately, matchings are not independent sets of a matroid, and the proof I have in mind does not work. $\endgroup$ Sep 25, 2022 at 5:17
  • $\begingroup$ Yes I think the dependence of sets makes things complicated - thanks though! $\endgroup$
    – messi22
    Sep 26, 2022 at 1:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.