Zarankiewicz’s problem for semilinear hypergraphs

Abdul Basit, Artem Chernikov, Sergei Starchenko, Chiu-Minh Tran and I have uploaded to the arXiv our paper Zarankiewicz’s problem for semilinear hypergraphs. This paper is in the spirit of a number of results in extremal graph theory in which the bounds for various graph-theoretic problems or results can be greatly improved if one makes some additional hypotheses regarding the structure of the graph, for instance by requiring that the graph be “definable” with respect to some theory with good model-theoretic properties.

A basic motivating example is the question of counting the number of incidences between points and lines (or between points and other geometric objects). Suppose one has points and lines in a space. How many incidences can there be between these points and lines? The utterly trivial bound is , but by using the basic fact that two points determine a line (or two lines intersect in at most one point), a simple application of Cauchy-Schwarz improves this bound to . In graph theoretic terms, the point is that the bipartite incidence graph between points and lines does not contain a copy of (there does not exist two points and two lines that are all incident to each other). Without any other further hypotheses, this bound is basically sharp: consider for instance the collection of points and lines in a finite plane , that has incidences (one can make the situation more symmetric by working with a projective plane rather than an affine plane). If however one considers lines in the real plane , the famous Szemerédi-Trotter theorem improves the incidence bound further from to . Thus the incidence graph between real points and lines contains more structure than merely the absence of .

More generally, bounding on the size of bipartite graphs (or multipartite hypergraphs) not containing a copy of some complete bipartite subgraph (or in the hypergraph case) is known as Zarankiewicz’s problem. We have results for all and all orders of hypergraph, but for sake of this post I will focus on the bipartite case.

In our paper we improve the bound to a near-linear bound in the case that the incidence graph is “semilinear”. A model case occurs when one considers incidences between points and axis-parallel rectangles in the plane. Now the condition is not automatic (it is of course possible for two distinct points to both lie in two distinct rectangles), so we impose this condition by fiat:

Theorem 1 Suppose one has points and axis-parallel rectangles in the plane, whose incidence graph contains no ‘s, for some large .

• (i) The total number of incidences is .
• (ii) If all the rectangles are dyadic, the bound can be improved to .
• (iii) The bound in (ii) is best possible (up to the choice of implied constant).

We don’t know whether the bound in (i) is similarly tight for non-dyadic boxes; the usual tricks for reducing the non-dyadic case to the dyadic case strangely fail to apply here. One can generalise to higher dimensions, replacing rectangles by polytopes with faces in some fixed finite set of orientations, at the cost of adding several more logarithmic factors; also, one can replace the reals by other ordered division rings, and replace polytopes by other sets of bounded “semilinear descriptive complexity”, e.g., unions of boundedly many polytopes, or which are cut out by boundedly many functions that enjoy coordinatewise monotonicity properties. For certain specific graphs we can remove the logarithmic factors entirely. We refer to the preprint for precise details.

The proof techniques are combinatorial. The proof of (i) relies primarily on the order structure of to implement a “divide and conquer” strategy in which one can efficiently control incidences between points and rectangles by incidences between approximately points and boxes. For (ii) there is additional order-theoretic structure one can work with: first there is an easy pruning device to reduce to the case when no rectangle is completely contained inside another, and then one can impose the “tile partial order” in which one dyadic rectangle is less than another if and . The point is that this order is “locally linear” in the sense that for any two dyadic rectangles , the set is linearly ordered, and this can be exploited by elementary double counting arguments to obtain a bound which eventually becomes after optimising certain parameters in the argument. The proof also suggests how to construct the counterexample in (iii), which is achieved by an elementary iterative construction.

An incidence theorem in higher dimensions

Jozsef Solymosi and I have just uploaded to the arXiv our paper “An incidence theorem in higher dimensions“, submitted to Discrete and Computational Geometry. In this paper we use the polynomial Ham Sandwich method of Guth and Katz (as discussed previously on this blog) to establish higher-dimensional versions of the Szemerédi-Trotter theorem, albeit at the cost of an epsilon loss in exponents.

Recall that the Szemerédi-Trotter theorem asserts that given any finite set of points and lines in the plane , the number of incidences has the upper bound

Apart from the constant factor, this bound is sharp. As discussed in this previous blog post, this theorem can be proven by the polynomial method, and the strategy can be rapidly summarised as follows. Select a parameter . By the polynomial Ham Sandwich theorem, one can divide into cell interiors, each with points, and incident to lines on the average, plus a boundary set which is an algebraic curve of degree . To handle the contribution of each cell interior, one uses a more elementary incidence bound (such as the bound coming from the fact that two points determine at most one line); to handle the contribution on the cell boundary, one uses algebraic geometry tools such as Bezout’s theorem. One then combines all the bounds and optimises in to obtain the result.

As a general rule, the contribution of the cell interiors becomes easier to handle as increases, while the contribution of the cell boundaries become easier as decreases. As such, the optimal value of is often an intermediate one (in the case of Szemerédi-Trotter, the choice is typical). Among other things, this requires some control of moderately high degree algebraic sets, though in this planar case , one only needs to control algebraic curves in the plane, which are very well understood.

In higher dimensions, though, the complexity of the algebraic geometry required to control medium degree algebraic sets increases sharply; compare for instance the algebraic geometry of ruled surfaces appearing in the three-dimensional work of Guth and Katz as discussed here, compared with the algebraic geometry of curves in the two-dimensional Szemerédi-Trotter theorem discussed here.

However, Jozsef and I discovered that it is also possible to use the polynomial method with a non-optimised value of , and in particular with a bounded value of , which makes the algebraic geometry treatment of the boundary significantly easier. The drawback to this is that the cell interiors can no longer be adequately controlled by trivial incidence estimates. However, if instead one controls the cell interiors by an induction hypothesis, then it turns out that in many cases one can recover a good estimate. For instance, let us consider the two-dimensional Szemerédi-Trotter theorem in the most interesting regime, namely when the term on the RHS is dominant. If we perform the cell decomposition with some small parameter , then we obtain cells with points and lines on the average; applying the Szemerédi-Trotter theorem inductively to each of these cells, we end up with a total contribution of

for the cell interiors, and so provided that one can also control incidences on the (low degree) cell boundary, we see that we have closed the induction (up to changes in the implied constants in the notation).

Unfortunately, as is well known, the fact that the implied constants in the notation degrade when we do this prevents this induction argument from being rigorous. However, it turns out this method does work nicely to give the weaker incidence bound

for any fixed ; the point being that this extra epsilon of room in the exponents means that the induction hypothesis gains a factor of or so over the desired conclusion, allowing one to close the induction with no loss of implied constants if all the parameters are chosen properly. While this bound is weaker than the full Szemerédi-Trotter theorem, the argument is simpler in the sense that one only needs to understand bounded degree algebraic sets, rather than medium degree algebraic sets. As such, this argument is easier to extend to higher dimensions.

Indeed, as a consequence of this strategy (and also a generic projection argument to cut down the ambient dimension, as used in this previous paper with Ellenberg and Oberlin, and an induction on dimension), we obtain in our paper a higher-dimensional incidence theorem:

Theorem 1 (Higher-dimensional Szemerédi-Trotter theorem) Let , and let and be finite sets of points and -planes in , such that any two -planes in intersect in at most one point. Then we have for any .

Something like the transversality hypothesis that any two -planes in intersect in at most one point is necessary, as can be seen by considering the example in which the points are all collinear, and the -planes in all contain the common line. As one particular consequence of this result, we recover (except for an epsilon loss in exponents) the complex Szemerédi-Trotter theorem of Toth, whose proof was significantly more complicated; it also gives some matrix and quaternionic analogues, in particular giving new sum-product theorems in these rings. Note that the condition is natural, because when the ambient dimension is less than , it is not possible for two -planes to intersect in just one point. Using the generic projection trick, one can easily reduce to the critical case .

Actually, for inductive reasons, we prove a more general result than Theorem 1, in which the -planes are replaced instead by -dimensional real algebraic varieties. The transversality condition is now that whenever a point is incident to two such varieties , that the tangent cones of and at only intersect at . (Also for technical reasons, it is convenient to consider a partial subset of incidences in , rather than the full set of incidences. Indeed, it seems most natural to consider the triplet

as a single diagram, rather than to consider just the sets and .)

The reason for working in this greater level of generality is that it becomes much easier to use an induction hypothesis to deal with the cell boundary; one simply intersects each variety in with the cell boundary, which usually lowers the dimension of the variety by one. (There are some exceptional cases in which is completely trapped inside the boundary, but due to the transversality hypothesis, this cannot contribute many incidences if the ambient dimension is (so the cell boundary is only dimensional).)

As one application of this more general incidence result, we almost extend a classic result of Spencer, Szemerédi, and Trotter asserting that points in the plane determine unit distances from to , at the cost of degrading to .

Recent progress on the Kakeya conjecture

Below the fold is a version of my talk “Recent progress on the Kakeya conjecture” that I gave at the Fefferman conference.

The crossing number inequality

Today I’d like to discuss a beautiful inequality in graph theory, namely the crossing number inequality. This inequality gives a useful bound on how far a given graph is from being planar, and has a number of applications, for instance to sum-product estimates. Its proof is also an excellent example of the amplification trick in action; here the main source of amplification is the freedom to pass to subobjects, which is a freedom which I didn’t touch upon in the previous post on amplification. The crossing number inequality (and its proof) is well known among graph theorists but perhaps not among the wider mathematical community, so I thought I would publicise it here.

In this post, when I talk about a graph, I mean an abstract collection of vertices V, together with some abstract edges E joining pairs of vertices together. We will assume that the graph is undirected (the edges do not have a preferred orientation), loop-free (an edge cannot begin and start at the same vertex), and multiplicity-free (any pair of vertices is joined by at most one edge). More formally, we can model all this by viewing E as a subset of , the set of 2-element subsets of V, and we view the graph G as an ordered pair G = (V,E). (The notation is set up so that .)

Now one of the great features of graphs, as opposed to some other abstract maths concepts, is that they are easy to draw: the abstract vertices become dots on a plane, while the edges become line segments or curves connecting these dots. [To avoid some technicalities we do not allow these curves to pass through the dots, except if the curve is terminating at that dot.] Let us informally refer to such a concrete representation D of a graph G as a drawing of that graph. Clearly, any non-trivial graph is going to have an infinite number of possible drawings. In some of these drawings, a pair of edges might cross each other; in other drawings, all edges might be disjoint (except of course at the vertices, where edges with a common endpoint are obliged to meet). If G has a drawing D of the latter type, we say that the graph G is planar.

Given an abstract graph G, or a drawing thereof, it is not always obvious as to whether that graph is planar; just because the drawing that you currently possess of G contains crossings, does not necessarily mean that all drawings of G do. The wonderful little web game “Planarity” illustrates this point excellently. Nevertheless, there are definitely graphs which are not planar; in particular the complete graph on five vertices, and the complete bipartite graph on two sets of three vertices, are non-planar.

There is in fact a famous theorem of Kuratowski that says that these two graphs are the only “source” of non-planarity, in the sense that any non-planar graph contains (a subdivision of) one of these graphs as a subgraph. (There is of course the even more famous four-colour theorem that asserts that every planar graphs is four-colourable, but this is not the topic of my post today.)

Intuitively, if we fix the number of vertices |V|, and increase the number of edges |E|, then the graph should become “increasingly non-planar”; conversely, if we keep the same number of edges |E| but spread them amongst a greater number of vertices |V|, then the graph should become “increasingly planar”. Is there a quantitative way to measure the “non-planarity” of a graph, and to formalise the above intuition as some sort of inequality?