1
$\begingroup$

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.

I know one way to prove the threshold of a perfect matching is to look at Halls theorem, but could we do it using first and second moment methods?

To clarify what I mean. We can work out using Halls theorem a value for the probability $p$ that the graph contains a perfect matching by showing w.h.p $|N(S)|\geq S$ for all subsets $S \subseteq V$.

Can we do the same thing but just by counting sets of independent edges of size $n$ (here both vertex classes have size $n$)? So what I mean here is if I counted all possible sets of $n$ independent edges, and then let $X$ be the random variable representing the number of sets of $n$ independent edges present. Could I obtain this value of $p$ by working out what it needs to be to ensure $X>0$ using first and second moment methods?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ provide more details here, please... $\endgroup$
    – Dima Pasechnik
    Commented Jan 5, 2015 at 19:02
  • 6
    $\begingroup$ What do you mean by "proving the threshold" and by the "threshold of a perfect matching"? $\endgroup$
    – Seva
    Commented Jan 5, 2015 at 19:16
  • 1
    $\begingroup$ The question at mathoverflow.net/questions/60075/… , though addressing a different graph property, has a similar flavor. $\endgroup$
    – Kevin P. Costello
    Commented Jan 6, 2015 at 23:41
  • $\begingroup$ Imagine adding edges at random until the moment there is a perfect matching. This is purely a guess, but I suspect that the last edge needed takes an isolated vertex any gives it a neighbor (and a forced edge.) At this stage the vast majority, or at least an appreciable fraction of of vertices might have degree 3 or more and there will likely be exponentially many matchings. $\endgroup$
    – Aaron Meyerowitz
    Commented Jan 7, 2015 at 10:02

1 Answer 1

Reset to default
3
$\begingroup$

As I see it, you won't be able to do it for the correct threshold (maybe for a much larger p). The problem in the second moment here is that if you take two random perfect matchings, then in expectation they will share edges (just think about fixed points in a random permutation). Therefore, in calculating the second moment you will have too many summands in calculating the VAR. You can look at the following paper http://www.math.cmu.edu/~af1p/Texfiles/hypertight.pdf, they explain quite nice why does it work/fail for graphs/hypergraph.

Improve this answer
$\endgroup$

Your Answer

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

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