Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a bipartite graph $G=(X \cup Y, E)$ with both sides of equal size; we let $n$ denote $|X|=|Y|$

We are also given an integer $d\ge 3$ and we wish each vertex in $X$ to be adjacent to at most $d$ neighbors in $Y$. For any, it is easy to construct arbitrarily large bipartite graphs with this property. It is not as easy to make a graph which also has the following expansion properties:

$P_1$: for each $S \subseteq X$ with $|X|\le\dfrac{n}{3d}$ we have $|N(S)|\ge\dfrac{|S|d}4$

$P_2$: for each $S \subseteq X$ with $\dfrac{n}{3d} < |S|\le\dfrac{n}2$ we have $|N(S)|\ge |S| + \dfrac{n}{3d}$

Consider the following experiment. For each $v\in X$, choose $d$ vertices in $Y$ independently at random, and make these vertices adjacent to $v$. Let $G'$ be the resulting random graph. Prove that (if $n$ is sufficiently large with respect to $d$), then with probability greater than $0.75$, Property $P_1$ holds for $G'$.

Deduce that there exist infinitely many bipartite graphs with these expansion properties.

share|cite|improve this question
Which part are you having trouble with? – Tara B Apr 3 '13 at 18:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.