You are currently browsing the tag archive for the ‘graph theory’ tag.

-Incidence problems and bipartite graphs-

An important problem in combinatorial geometry is to study the number of incidences between a set of points and set of lines (or curves, surfaces, etc.). More specifically, let {P} be a finite subset of {\mathbb{R}^n} and let {L} be a finite set of lines (or curves, surfaces, etc.). We define the set of incidences between {P} and {L} by {I(P,L):=\{(p,\ell)\in P\times L\colon p\in\ell\}}. Our problem is now to study the size of {I(P,L)}. Of course we always have the trivial bound {|I(P,L)|\leq |P||L|}, but we would like to do better.

Introducing the set of incidences of {P} and {L} may just seem like good notation, but in fact it is characterizing our incidence problem in terms of graph theory: we define the incidence graph {G(P,L)} of {P} and {L} to be the graph whose vertices are points of {P} and lines of {L}, with a point {p} connected to a line {\ell} if {p\in\ell}. So the set of edges of {G(P,L)} is {I(P,L)}.

The incidence graph {G(P,L)} is a special type of graph called a bipartite graph. A bipartite graph is a graph {G} whose vertices form two disjoint sets, {A} and {B}, such that no edge joins two points of {A} and no edge joins two points of {B}; that is, the edges of {G} are of the form {\{a,b\}} with {a} in {A} and {b} in {B}. We will write {G=G(A,B)} to specify the vertex sets and we write {E(G)} or {E(A,B)} for the edges of {G}.

As with incidence graphs, we have the trivial bound {|E(A,B)|\leq |A||B|} and in general we can’t do any better. In the next section we will prove non-trivial bounds on the number of edges of a bipartite graph under certain restrictions. By geometric considerations, we’ll see that many incidence graphs satisfy these restrictions, thus giving us non-trivial bounds on {|I(P,L)|}. It turns out that these bounds are actually sharp for point-line incidences over finite fields.

-Restricted subgraph bound-

We noted above that the trivial bound {|E(A,B)|\leq |A||B|} cannot be improved in general. We call a graph that achieves equality a complete bipartite graph. That is, a complete bipartite graph is a bipartite graph with vertex sets {A} and {B} such that every vertex of {A} is connected to every vertex of {B}. If {|A|=s} and {|B|=t}, then we denote the complete bipartite graph with vertex sets {A} and {B} by {K_{s,t}}. If we consider only bipartite graphs {G(A,B)} whose edge set does not contain a copy of {K_{s,t}} for some {s\leq|A|} and {t\leq|B|}, we should be able to improve this trivial bound:

Restricted Subgraph Bound: Let {G=G(A,B)} be a bipartite graph that does not contain a {K_{s,t}} as a subgraph, where “{s}” corresponds to points of {A} and “{t}” corresponds to points of {B}. The cardinality of the set {E(G)} of edges of {G} satisfies

\displaystyle |E(G)|\leq \sqrt[s]{t-1}|A||B|^{1-1/s}+s|B|.

Before we prove the restricted subgraph bound, let’s note that a point-line incidence graph contains no {K_{2,2}}, because any two points lie on a unique line. Thus {|I(P,L)|\leq |P||L|^{1/2}+2|L|}.

Proof: For now, let’s assume that each vertex in B has degree greater than s, so that in particular s|B|\leq E(G). The general case will follow easily from this particular case.

We define the set {F} of “fans” in {G}:

\displaystyle F:=\{(a_1,\ldots,a_s,b)\colon (a_1,b),\ldots,(a_s,b)\in E(G), a_i\not=a_j\mbox{ for }i\not=j\}.

We will count |F| in two ways. First note that

\displaystyle |F|=s!\sum_{b\in B}{\deg(b)\choose s}. \ \ \ \ \ (1)

Next note any {s}-tuple {(a_1,\ldots, a_s)} contributes at most {t-1} fans {(a_1,\ldots,a_s,b_i)}, {i=1,\ldots,t-1}, to {F}. Thus

\displaystyle |F|\leq (t-1)s!{|A|\choose s}. \ \ \ \ \ (2)

Combining the counts in (1) and (2), we have

\displaystyle s!\sum_{b\in B}{\deg(b)\choose s}\leq (t-1)s!{|A|\choose s}. \ \ \ \ \ (3)

Since {{x\choose s}} is convex in {x}, the sum on the left side of (3) is minimized by the average of the degrees:

\displaystyle s!\sum_{b\in B}{\deg(b)\choose s}\geq|B|s!{|E(G)|/|B|\choose s}\geq |B|\left(\frac{|E(G)|}{|B|}-s\right)^s. \ \ \ \ \ (4)

Combining (4) with (3), we have

\displaystyle |B|\left(\frac{|E(G)|}{|B|}-s\right)^s\leq (t-1)s!{|A|\choose s}\leq (t-1)|A|^s.

Solving for {|E(G)|} yields the desired result:

\displaystyle |E(G)|\leq \sqrt[s]{t-1}|A||B|^{1-1/s}+s|B|.


By symmetry we have the bound

\displaystyle |E(G)|\leq \sqrt[t]{s-1}|A|^{1-1/t}|B|+t|A|.

Thus we may conclude that

\displaystyle |E(G)|\leq\min\{\sqrt[s]{t-1}|A||B|^{1-1/s}+s|B|, \sqrt[t]{s-1}|A|^{1-1/t}|B|+t|A|\}.


The proof I gave here is based off of Jacob Fox’s lecture notes from a combinatorics class at MIT.


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.