You are currently browsing the monthly archive for June 2012.

-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|.$

$\Box$

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|\}.$

-Acknowledgements-

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 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.