-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 be a finite subset of and let be a finite set of lines (or curves, surfaces, etc.). We define the set of incidences between and by . Our problem is now to study the size of . Of course we always have the trivial bound , but we would like to do better.
Introducing the set of incidences of and 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 of and to be the graph whose vertices are points of and lines of , with a point connected to a line if . So the set of edges of is .
The incidence graph is a special type of graph called a bipartite graph. A bipartite graph is a graph whose vertices form two disjoint sets, and , such that no edge joins two points of and no edge joins two points of ; that is, the edges of are of the form with in and in . We will write to specify the vertex sets and we write or for the edges of .
As with incidence graphs, we have the trivial bound 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 . 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 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 and such that every vertex of is connected to every vertex of . If and , then we denote the complete bipartite graph with vertex sets and by . If we consider only bipartite graphs whose edge set does not contain a copy of for some and , we should be able to improve this trivial bound:
Restricted Subgraph Bound: Let be a bipartite graph that does not contain a as a subgraph, where “” corresponds to points of and “” corresponds to points of . The cardinality of the set of edges of satisfies
Before we prove the restricted subgraph bound, let’s note that a point-line incidence graph contains no , because any two points lie on a unique line. Thus .
Proof: For now, let’s assume that each vertex in has degree greater than , so that in particular . The general case will follow easily from this particular case.
We define the set of “fans” in :
Since is convex in , the sum on the left side of (3) is minimized by the average of the degrees:
Solving for yields the desired result:
By symmetry we have the bound
Thus we may conclude that
The proof I gave here is based off of Jacob Fox’s lecture notes from a combinatorics class at MIT.