Dense arrangements are locally very dense I.

József SolymosiDepartment of Mathematics, University of British Columbia, Vancouver, BC, Canada V6T 1Z2, Email: solymosi@math.ubc.ca The research was supported by OTKA and NSERC grants.

November 27, 2006

Abstract
The Szemerédi-Trotter theorem [18] gives a bound on the maximum number of incidences between points and lines on the Euclidean plane. In particular it says that n   lines and n   points determine O ( n 4 / 3 )   incidences. Let us suppose that an arrangement of n   lines and n   points defines c n 4 / 3   incidences, for a given positive c .   It is widely believed that such arrangements have special structure, but no results are known in this direction. Here we show that for any natural number, k ,   one can find k   points of the arrangement in general position such that any pair of them is incident to a line from the arrangement, provided by n ≥ n 0 ( k ) .   In a subsequent paper we will establish similar statement to hyperplanes.

1 Introduction

The celebrated Szemerédi-Trotter Theorem [18] states that for n   points on the plane, the number of m   -rich lines cannot exceed
O ( n 2 / m 3 + n / m ) , (1)
and this bound is tight in the worst case. This result has numerous applications not only in geometry [16, 19] , but also in number theory [13] . The Szemerédi-Trotter theorem has various proofs, the most elegant is Székely's [19] . However the proofs provide very limited insight view of the structure of extremal arrangements. It is widely believed that a point-line arrangement which defines many incidences has a special, somehow rigid structure. For example let us mention here a question of Elekes. Is it true that for every c > 0   there is a c ′ > 0   such that if a set of n   points on the plane contains at least c n 2   collinear triples then at least c ′ n   points are along an algebraic curve of degree d ,   where d   is an universal constant.
The main purpose of this paper is to show that any arrangement with close to the maximum number of incidences is locally a collection of complete geometric graphs. For the sake of simplicity we state the theorem for the balanced case, when the number of lines equals to the number of points, but it is quite straightforward to see the similar statement for unbalanced cases as well.
Recent work of Gowers [20] and Nagle, Rödl, Schacht, and Skokan [2, 3, 4] has established a hypergraph removal lemma, which in turn implies similar results to hyperplanes, however a slightly different approach is needed, mainly because the higher dimensional extensions of the Szemerédi-Trotter theorem are not as well defined as the planar case. To obtain sharp bounds one needs certain restrictions on the arrangements. Therefore the corresponding structure theorems will appear in subsequent paper.
A pointset or a set of lines is in general position if no three of the elements are collinear or concurrent.
Theorem 1 For every natural number k   and real c > 0   there is a threshold n 0 = n 0 ( k , c )   such that if an arrangement of n ≥ n 0   lines and n   points defines at least c n 4 / 3   incidences, then one can always find k   points of the arrangement in general position, such that any pair of them is incident to a line from the arrangement.
As we will see it from the proof, the complete k   -tuple is ”local” in a sense that for any pair of points, p 1   and p 2 ,   the number of points from the arrangement, incident to the line segment ( p 1 , p 2 )   is less than k .  

2 Proof of Theorem 1

The main tool of the proof is Szemerédi's Regularity Lemma [9, 10] . We will use it's counting lemma form, because it is easier to extend to hypergraphs which we will need for the higher dimensional extensions. Let us prove first the simplest case, to show that there is always a triangle. This ”simplest case” is interesting in it's own right, the statement of Lemma 2 implies Roth's theorem [5] about arithmetic progressions on dense subsets of integers. For the details we refer to [7, 8] .
Lemma 2 For every c > 0   there is a threshold n 0 = n 0 ( c )   and a positive δ = δ ( c )   such that, for any set of n ≥ n 0   lines L   and any set of m ≥ c n 2   points P   , if every point is incident to three lines, then there are at least δ n 3   triangles in the arrangement. (A triangle is a set of three distinct points from P   such that any two are incident to a line from L .   )
This lemma follows from the following theorem of Ruzsa and Szemerédi [6] , which is also called as the triangle removal lemma or the counting lemma for triangles.
Theorem 3 [6] Let G   be a graph on n   vertices. If G   is the union of c n 2   edge-disjoint triangles, then G   contains at least δ n 3   triangles, where δ   depends on c   only.
The same theorem from a different angle is the following.
Theorem 4 Let G   be a graph on n   vertices. If G   contains o ( n 3 )   triangles, then one can remove o ( n 2 )   edges to make G   triangle-free.
To prove Lemma 2, let us construct a graph where L   is the vertex set, and two vertices are adjacent if and only if the corresponding lines cross at a point of P   . This graph is the union of c n 2   disjoint triangles, every point of P   defines a unique triangle, so we can apply Theorem 3.
To determine the number of triangles in any arrangement of lines and points seems to be a hard task. A related conjecture of de Caen and Székely [21] is that n   points and m   lines can not determine more than n m   triangles.
One can repeat the same argument, now with k   instead of 3. The corresponding counting lemma can be proven using Szemerédi's Regularity Lemma. The proof is analogous to the Ruzsa-Szemerédi Theorem. There are slightly different ways to state the Regularity Lemma, for our purposes the so called degree form is convenient. For the notations and proofs we refer to the survey paper of Komlós and Simonovits [1] .
Theorem 5 (Regularity Lemma) For every ε > 0   there is an M = M ( ε )   such that if G = ( V , E )   is any graph and d ∈ ( 0 , 1 ]   is any real number, then there is a partition of the vertex-set V   into k + 1   clusters V 0 , V 1 , … , V k ,   and there is a subgraph G ′ ⊂ G   with the following properties:
  • ∙ k ≤ M ,  
  • ∙ | V 0 | ≤ ε | V | ,  
  • ∙ all clusters V i ,   i ≥ 1 ,   are of the same size m ≤ ⌈ ε | V | ⌉ ,  
  • ∙ deg G ′ ( v ) > deg G ( v ) − ( d + ε ) | V |   for all v ∈ V ,  
  • ∙ e ( G ′ ( V i ) ) = 0   for each i ≥ 1 ,  
  • ∙ all pairs G ′ ( V i , V j )   ( 1 ≤ i < j ≤ k )   are ε −   regular, each with a density either 0 or greater than d   .
Armed with the Regularity Lemma we are ready to prove the following statement which is crucial in the proof of Theorem 1.
Lemma 6 For every c > 0   there is a threshold n 0 = n 0 ( c )   and a positive δ = δ ( c )   such that, for any set of n ≥ n 0   lines L   and any set of m ≥ c n 2   points P   , if every point is incident to k   lines, then there are at least δ n k   complete k −   tuples in the arrangement. (A complete k −   tuple is a set of k   distinct lines in general position from L   such that any two intersect in a point from P .   )
Proof. To avoid having too many degenerate k −   tuples, we remove some points from P   which have many lines incident to them. P ′ ,   which is the subset of P ,   consists of points incident to at most 100 / c   lines from L .   We can apply (1) to see that P ′   is a large subset of P   , say 2 | P ′ | > | P | .   Let us construct a graph G   where L   is the vertex set, and two vertices are adjacent if and only if the corresponding lines cross at a point of P ′   . This graph, G ,   is the union of at least c 2 n 2   edge-disjoint K k −   s. Find a subgraph, G ′ ,   provided by Theorem 5 with ε ≪ c .   In G ′   we still have some complete K k −   s. Along the edges of such a complete graph we have a k −   tuple of V i −   s such that the bipartite graphs between them are dense and regular. This already implies the existence of many complete subgraphs, as the following lemma, quoted from [1] , shows.
Lemma 7 Given d > ε > 0 ,   a graph R   on n   vertices, and a positive integer m ,   let us construct a graph G   by replacing every vertex of R   by m   vertices, and replacing the edges of R   with ε −   regular pairs of density at least d .   Then G   has at least α m n   copies of R ,   where α   depends on ε , d ,   and n ,   but not on m .  
Most of the complete k −   vertex subgraphs of graph G ′   define a complete k −   tuple in the arrangement, i.e. the corresponding lines are in general position. To see this, let us count the ”degenerate” k −   tuples, the k −   element line-sets, where at least one triple is concurrent. The number of concurrent triples is at most c n 2 ( 100 / c 3 ) ≤ c ′ n 2 .   For every concurrent triple one can select k − 3   lines to get a degenerate k −   tuple. The expression, c ′ n k − 1 ,   is clearly an upper bound on the degenerate k −   tuples, therefore most of the complete graphs on k   vertices in G ′   are complete k −   tuples if n   is large enough, n ≥ n 0 = n 0 ( c ) .  
The final step of the proof of Theorem 1 is to show that arrangements with many incidences always have a substructure where one use Lemma 2.
We divide the arrangement into smaller parts where we apply the dual of Lemma 2. The common technique to do that is the so called cutting, which was introduced by Chazelle, see in [11] , about 20 years ago. Here we use a more general result, a theorem of Matousek [15] .
Lemma 8 Let P   be a pointset, P ⊂ R d , | P | = n ,   and let r   be a parameter, 1 ≪ r ≪ n .   Then the set P   can be partitioned into t   sets Δ 1 , Δ 2 , … , Δ t ,   in such a way that n / r ≤ | Δ i | ≤ 2 n / r   for all i ,   and any hyperplane crosses no more than O ( r 1 − 1 / d )   sets, where t = O ( r ) .  
Here we use the d = 2   case and we choose the value r = β k n 2 / 3 ,   where β k   is a constant, depends on k ,   which we will specify later. Let us count the number of incidences along the lines of L ,   according to the partition of P .   For a given line ξ ∈ L ,   we count the sum ∑ i = 1 t ⌊ | Δ i ∩ ξ | / k ⌋ ,   which is not much smaller than the number of incidences on ξ   over k   if ξ   is rich of incidences, say, incident to much more than r 1 / 2 k   points of P .   From the condition of Theorem 1 and the properties of the partition we have the following inequality.
c k n 4 / 3 ≤ ∑ ξ ∈ L ∑ i = 1 t ⌊ | Δ i ∩ ξ | k ⌋ + | L | r 1 / 2  
Choosing β k = c 2 k ,   the inequality becomes
c n 4 / 3 2 k = c k n 4 3 ≤ ∑ ξ ∈ L ∑ i = 1 t ⌊ | Δ i ∩ ξ | k ⌋ = ∑ i = 1 t ∑ ξ ∈ L ⌊ | Δ i ∩ ξ | k ⌋ .  
Therefore there is an index i   , such that
c k n 2 / 3 ≤ ∑ ξ ∈ L ⌊ | Δ i ∩ ξ | k ⌋ .  
If s = ⌊ | Δ i ∩ ξ | k ⌋   then we can partition the points incident to ξ   into r   consecutive k −   tuples. We can break the line into r   k −   rich line segments and consider them as separate lines. Our combinatorial argument in Lemma 6 is robust enough to allow such modifications. Then we have some c ′ n 2 / 3   k −   rich lines on | Δ i | = c ” n 1 / 3   points. (Another possible way to show that there are at least c ′ n 2 / 3   k −   rich lines, is to apply the Szemerédi-Trotter theorem, (1), to show that most of the lines are not ”very rich”.) To complete the proof of Theorem 1, we apply the dual statement of Lemma 6.
References

  1. J. Komlós, M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, in: Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
  2. B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, to appear, Random Structures and Algorithms.
  3. V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, to appear, Random Structures and Algorithms.
  4. V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint.
  5. K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 245–252.
  6. I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. J. Bolyai 18 (1978), 939-945.
  7. J. Solymosi, Note on a generalization of Roth's theorem, in: Discrete and computational geometry, 825-827, Algorithms Combin. 25, Springer Verlag, 2003.
  8. J. Solymosi, A note on a question of Erdős and Graham, Combinatorics, Probability and Computing 13 (2004), 263-267.
  9. E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89-104.
  10. E. Szemerédi, Regular partitions of graphs, in ”Problem'es Combinatoires et Th'eorie des Graphes, Proc. Colloque Inter. CNRS,” (Bermond, Fournier, Las Vergnas, Sotteau, eds.), CNRS Paris, 1978, 399-401.
  11. B. Chazelle. The Discrepancy Method. Cambridge University Press, 2000.
  12. K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), 99–160.
  13. Gy. Elekes, Sums versus products in Number Theory, Algebra and Erdős Geometry, vol 11 of Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 2002, pp. 241–290.
  14. Gy. Elekes and Cs. D. Tóth, Incidences of not-too-degenerate hyperplanes, in Proc. 21st ACM Sympos. Comput. Geom. (Pisa, 2005), ACM Press, to appear.
  15. J. Matoušek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), 315–334.
  16. J. Pach and M. Sharir, Geometric incidences, in Towards a Theory of Geometric Graphs, vol. 342 of Contemporary Mathematics, Amer. Math. Soc., Providence, RI, 2004, pp. 185–223.
  17. J. Solymosi and Cs. D. Tóth, Distinct distances in the plane, Discrete Comput. Geom. 25 (2001), 629–634.
  18. E. Szemerédi and W. T. Trotter Jr., Extremal problems in Discrete Geometry, Combinatorica 3 (3–4) (1983), 381–392.
  19. L. A. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability & Computing 6 (3) (1997), 353–358.
  20. W.T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, preprint.
  21. D. de Caen and L. A. Székely, On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar pointline systems, J. Combin. Theory Ser. A. 77 (1997), 268–278.