The popularity lemma is simple lemma about refining the vertices of a bipartite graph by degree. Since it gives you a lower bound on the number of edges that remain after refining, it can be used to show that not too many edges are lost by refining.

**Popularity Lemma:** *Let be a bipartite graph. Let be the set of vertices in with , where . Then the cardinality of the set of edges from to satisfies*

We can generalize slightly: if is a constant such that , then

The first version can be recovered by setting , which is the average degree of a vertex in . From this point of view, the bound is only useful when is smaller than the average degree. In particular, if , where and is the average density of a vertex in , then

*Proof:* We may divide the vertices of into vertices with degree at least and vertices with degree less than : . Summing degrees over the vertices of yields

Since each vertex in has degree less than , we have

Since , we have

Rearranging yields the desired result.

Although I’m sure this is an old result, I first saw this lemma in Guth and Katz’s 2008 paper on the joints problem.

### Like this:

Like Loading...

## Leave a comment

Comments feed for this article