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.

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by a number of matches? $\endgroup$
    – Fedor Petrov
    Commented 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
    Commented 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$
    – Fedor Petrov
    Commented Sep 25, 2022 at 5:17
  • $\begingroup$ Yes I think the dependence of sets makes things complicated - thanks though! $\endgroup$
    – messi22
    Commented Sep 26, 2022 at 1:28

0

Reset to default

You must log in to answer this question.