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 {G(A,B)} be a bipartite graph. Let {B'} be the set of vertices in {B} with {degree\geq\mu}, where {\mu\geq 0}. Then the cardinality of the set of edges from {A} to {B'} satisfies

\displaystyle |E(A,B')|\geq |E(A,B)|-\mu|B|.

We can generalize slightly: if {\rho} is a constant such that {|E(A,B)|\geq\rho|B|}, then

\displaystyle |E(A,B')|\geq (\rho-\mu)|B|.

The first version can be recovered by setting {\rho =|E(A,B)|/|B|}, which is the average degree of a vertex in {B}. From this point of view, the bound is only useful when {\mu} is smaller than the average degree. In particular, if {\mu=c\rho}, where {0<c<1} and {\rho} is the average density of a vertex in {B}, then

\displaystyle |E(A,B')|\geq (1-c)|E(A,B)|.

Proof: We may divide the vertices of {B} into vertices with degree at least {\mu} and vertices with degree less than {\mu}: {B=B'\cup B\backslash B'}. Summing degrees over the vertices of {B} yields

\displaystyle |E(A,B)|=\sum_{b\in B}\deg(b)= |E(A,B')|+\sum_{b\in B\backslash B'}\deg(b).

Since each vertex in {B\backslash B'} has degree less than {\mu}, we have

\displaystyle \sum_{b\in B\backslash B'}\deg(b)\leq \mu|B'|\leq \mu|B|.

Since {|E(A,B)|\geq\rho|B|}, we have

\displaystyle \rho|B|\leq |E(A,B')|+\mu|B|.

Rearranging yields the desired result. \Box

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.

Advertisements