- Stirling's approximation is that (n choose k) is at most (en/k)^k (where e is 2.71) and at least (n/k)^k
- what is the probability that there exists an S subseteq L with |S|=i and |N(S)| < (1+eps)|S|?
- (Then use union bounds on the possible sizes of S.)
- Note that you only have to show that the randomly chosen graph is an expander with some constant (>0) probability.
- If it makes it easier to allow multiple edges, then by all means do so.