0
$\begingroup$

I want to find a bound on the above problem, and show that a random graph has a positive probability of being an expanding bipartite with the property, |V1|=|V2|. I am not getting, where should I start.

Apologies for not writing my understanding, I am very much stuck.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What do you mean by positive probability? probability cant be nagative...except in quantum mechanics (complex amplitudes). Anyway, i suggest you take a look at this question: math.stackexchange.com/questions/3051954/… $\endgroup$ – Yamar69 Oct 8 '19 at 14:33
  • $\begingroup$ Apologies, I didn't make myself clear. Here positive is non zero, which means there is a chance of having the above event occur. $\endgroup$ – Manika Sharma Oct 8 '19 at 14:44
  • $\begingroup$ @ManikaSharma Am I correct in assuming your problem is the following: you want to prove the existence of a bipartite expander for which $|V_1|=|V_2|$, and you want to do this by using a (non-constructive) probabilistic argument? I.e. you want to take a random bipartite graph and show that the probability it is an expander is non-zero/positive (which proves there exists such a graph). The problem is your question is ill-defined as the complete bipartite graph $K_{n,n}$ is an expander. $\endgroup$ – eru-cs Oct 19 '19 at 0:33
  • $\begingroup$ If you ask that the graph be $d$-regular for some constant $d$, then the question becomes more interesting (see for instance theory.epfl.ch/courses/topicstcs/Lecture3.pdf, tcs.tifr.res.in/~prahladh/teaching/05spring/lectures/lec2.pdf) If this is indeed what you want I can write an actual answer, but you first need to clarify a bit. $\endgroup$ – eru-cs Oct 19 '19 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.