### Cetin Kaya Koc

Shared publicly -I'm on the editorial board of Combinatorica. Whether I should be is another matter, since it is a journal owned by Springer, one of the big commercial publishers. But I am, and as a result I have a free subscription to the journal. Today I found the latest issue in my pigeonhole, and the last paper in the issue was a paper by Csaba Tóth, entitled, "The Szemerédi-Trotter theorem in the complex plane."

This paper is remarkable for two reasons. One, which provokes this post, is that at the beginning of the paper it says, "Received December 1999, Revised May 16 2014." So the paper is coming out over 15 years after it was submitted. Doubtless this isn't a record, but it's still a pretty big gap. I noticed it because my first reaction on seeing the title was, "But I thought this had been done a long time ago."

The other reason is the result itself. The Szemerédi-Trotter theorem states that if you have n points and m lines in the plane, then the number of incidences (that is, pairs (P,L) where P is a point in your collection, L is a line in your collection, and P is a point in L) is at most C(n + m + n^{2/3}m^{2/3}). This slightly curious looking bound is best possible up to the constant C and is more natural than it looks.

The known proofs of the theorem relied heavily on the topological properties of the plane, which meant that it was far from straightforward to generalize the result to lines and points in the complex plane (by which I mean C^2 and not C). Indeed, it was an open problem to do so, and that was what Tóth solved.

If you're feeling ambitious, there is also a lovely conjecture in the paper. Define a d-flat in R^{2d} to be an affine subspace of dimension d. Suppose now that you have n points and m d-flats with the property that no two of the d-flats intersect in more than a point. Is it the case that the number of incidences is at most C(n + m + n^{2/3}m^{2/3})? The constant C is allowed to depend on the dimension d but not on anything else. Note that even for d=2 this would be a new result, since Tóth's theorem is the special case where the d-flats are complex lines.

I should say that I haven't checked whether there has been any progress on this conjecture, so I don't guarantee that it is open. If anyone knows about its status, it would be great if you could comment below.

#spnetwork DOI: 10.1007/s00493-014-2686-2

This paper is remarkable for two reasons. One, which provokes this post, is that at the beginning of the paper it says, "Received December 1999, Revised May 16 2014." So the paper is coming out over 15 years after it was submitted. Doubtless this isn't a record, but it's still a pretty big gap. I noticed it because my first reaction on seeing the title was, "But I thought this had been done a long time ago."

The other reason is the result itself. The Szemerédi-Trotter theorem states that if you have n points and m lines in the plane, then the number of incidences (that is, pairs (P,L) where P is a point in your collection, L is a line in your collection, and P is a point in L) is at most C(n + m + n^{2/3}m^{2/3}). This slightly curious looking bound is best possible up to the constant C and is more natural than it looks.

The known proofs of the theorem relied heavily on the topological properties of the plane, which meant that it was far from straightforward to generalize the result to lines and points in the complex plane (by which I mean C^2 and not C). Indeed, it was an open problem to do so, and that was what Tóth solved.

If you're feeling ambitious, there is also a lovely conjecture in the paper. Define a d-flat in R^{2d} to be an affine subspace of dimension d. Suppose now that you have n points and m d-flats with the property that no two of the d-flats intersect in more than a point. Is it the case that the number of incidences is at most C(n + m + n^{2/3}m^{2/3})? The constant C is allowed to depend on the dimension d but not on anything else. Note that even for d=2 this would be a new result, since Tóth's theorem is the special case where the d-flats are complex lines.

I should say that I haven't checked whether there has been any progress on this conjecture, so I don't guarantee that it is open. If anyone knows about its status, it would be great if you could comment below.

#spnetwork DOI: 10.1007/s00493-014-2686-2

1

Add a comment...