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