# What is the probability that an expanding bipartite graph exists with the property, |V1|=|V2|?

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.

• 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/… – Yamar69 Oct 8 '19 at 14:33
• Apologies, I didn't make myself clear. Here positive is non zero, which means there is a chance of having the above event occur. – Manika Sharma Oct 8 '19 at 14:44
• @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. – eru-cs Oct 19 '19 at 0:33
• 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. – eru-cs Oct 19 '19 at 0:33