Csaba D. Tóth
Instructor in Applied Mathematics
Massachusetts Institute of Technology
77 Massachusetts Ave., Room 2-336
Cambridge, MA 02139
+1 (617) 253-6584
toth ♠ math.mit.edu

---

Manuscripts:

• Minimum weight convex Steiner partitions,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • manuscript, 2007.
    
• A bipartite strengthening of the Crossing Lemma,
  • by Jacob Fox, János Pach, and Csaba D. Tóth,
  • submitted, 2007.
    
  • (abstract) The celebrated Crossing Lemma states that, in every drawing of a graph with n vertices and m ≥ 4n edges there are at least &Omega(m³/n²) crossing edges; or equivalently, there is an edge that crosses &Omega(m²/n²) other edges. We strengthen the Crossing Lemma for drawings in which no two edges intersect in more than a constant number of points. We prove for every integer k that every graph G=(V,E) with n vertices and m ≥ 3n edges drawn in the plane such that any two edges intersect in at most k points has two disjoint subsets E₁,E₂ ⊂ E, each of size &Omega(m²/n²), such that every edge in E₁ crosses every edge in E₂. We also show that this result does not remain true if we drop the assumption that no pair of edges intersect in more than a constant number of points.
• Intersection patterns of curves,
  • by Jacob Fox, János Pach, and Csaba D. Tóth,
  • submitted, 2007.
    
  • (abstract) We prove that there are constants c >0 and c_k >0 for every k∈N such that if a set C of n >1 curves in the plane, any two of which intersects in at most k points, contains at most ε n² intersecting pairs of curves, then there are two disjoint subsets A,B⊂ C, each of size at least c_kε^c n, with the property that every curve in A intersects every curve in B. It follows that there is a constant c'_k >0 so that the intersection graph G of C or its complement G contains a balanced complete bipartite graph K_t,t with t≥ c'_k n, where c'_k >0 depends on k only; in other words, the family of intersection graphs of k-intersecting curves in the plane satisfy the strong Erdős-Hajnal property.
• Turán-type results for partial orders and intersection graphs of convex sets,
  • by Jacob Fox, János Pach, and Csaba D. Tóth,
  • submitted, 2007.
  • (abstract) We prove several Ramsey-type results for intersection graphs of arrangements geometric shapes in the plane. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c>0 such that if n∈ N, n>2, and S is a family of convex bodies in the plane, then the intersection graph of S or its complement contains a complete bipartite graph with cn vertices in either of its vertex classes. There is a constant c>0 such that if n∈ N, n>2, and S is a family of x-monotone curves in the plane, then the intersection graph G of S contains a complete bipartite graph with cn/logn vertices in each of its vertex classes or the complement of G contains a complete bipartite graph with cn vertices in each of its vertex classes. Similar results were previously known for semialgebraic sets only, we show that algebraic properties are not necessary.
• Extremal problems on triangle areas in the plane and three-space,
  • by Adrian Dumitrescu, Micha Sharir, and Csaba D. Tóth,
  • submitted, 2007.
  • (abstract) In the plane we prove: (i) The number of unit area triangles in the plane is O(n^44/19) =O(n^2.3158). The best previous bound, O(n^7/3), is due to Pach and Sharir from 1992. (ii) For points in convex position, there exist n-element point sets that span Ω(n log n) triangles of unit area. (iii) The number of triangles of minimum (nonzero) area determined by $n$ points is at most (2/3)(n²-n); there exist n-element point sets that span (6/π²-o(1))n²$ minimum area triangles. (iv) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (v) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (vi) If no three points are allowed to be collinear, there exist n-element point sets that span Ω(n log n) minimum area triangles. In three-space we prove: (i) The number of unit area triangles spanned by n points is at most O(n^17/7β(n)), where β(n) is an extremely slowly growing function. (ii) A set of n points, not all on a line, determines at least Ω(n^2/3/β(n)) triangles of distinct areas that share a common side (here β(n) is an extremely slowly growing function). (iii) The number of minimum area triangles is O(n²); this is asymptotically tight. (iv) There exist n-element point sets that span Ω(n^4/3) triangles of maximum area.
• Note on a question of Bourgain about geometric incidences,
  • by József Solymosi and Csaba D. Tóth,
  • submitted, 2007.
  • (abstract) Given a set of s points and a set of n² lines in three-dimensional Euclidean space such that each line is incident to n points but no n lines are coplanar, then we have s=Ω(n^11/4). This is the first nontrivial answer to a question recently posed by Jean Bourgain.

---

Publications