1
$\begingroup$

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem

Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ bipartite graph in which edges occur randomly with probability $p(n)$, i want to find the size of the largest matching w.h.p for certain values of $p$.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Using $\log n$ instead of $n$ adds nothing to the problem except a change of notation. Define $N=\log n$ and consult the literature such as arxiv.org/abs/0910.5535 . $\endgroup$
    – Brendan McKay
    Dec 4, 2014 at 22:50
  • $\begingroup$ Ok, i thought perhaps the fact that one tends to $\infinity$ may make a difference, thanks for the reference! Also in your problem the number of neighbors selected is a constant $d$ will that make much of a difference. $\endgroup$
    – Pavan Sangha
    Dec 5, 2014 at 11:37

0

Reset to default

Your Answer

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