I(m,n): number of incidences of m points on n lines in the plane.
Szemeredi Trotter Thm: I(m,n) = O(m^2/3.n^2/3 + m + n)
we can see this is aymptotically tight by taking points (x,y) where 0 \le x \le k-1 and 0 \le y \le 2k^2-1 and lines y=ax + b where 0 \le a \le k-1 and 0 \le b \le k^2. Each line has at least k incidences.
Proof uses Crossing Lemma.
Let cr(G) be the minimum number of crossing in a drawing (in the plane) of a graph (with edges not necessarily line segments).
Ex1: for a vertex cover U, show that (|U|-2)cr(G) >= sum cr(G_u) where the summation runs over all u \in U, and G_u is the graph obtained by deleting u and all edges incident on it.
Ex2: determine the cr(K3,3), cr(K3,4), cr(K4,4) and cr(K3,n).
Crossing lemma: cr(G) >= e^3/ 64v^2 where e = |E(G)| and v = |V(G)|.
Proof: for any graph G with v vertices, e edges and crossing number x, x >= e - 3v.
Take a random subgraph of G by independently selecting each vertex with probability p. If x', e' and v' denote the crossings, edges and vertices in this new subgraph, then x' >= e' - 3v' and by linearity of expectation, xp^4 >= ep^2 - 3vp. Take p = 4n/e while assuming G has more than 4v edges to get the result.
Proof of szemeredi trotter using crossing lemma: Consider the graph obtained by taking the points as vertices and the line segments joining them as the edges. Then e = # of incidences - n, where n is the number of lines. v = m. and there are at most n^2 crossings as any two lines intersect at most once.
Beck's theorem: there exist constants C,K such that for any n points in the plane either at least n/C lie on a line, or there are n^2/K lines defined by the points.
Proof of Beck's theorem: wikipedia does a great job here: Beck's theorem.
here we used that: in a system of n points and some lines, if every line contains at least k points, then the number of lines is
O(n^2/k^3 + n/k).
Ex3: show that both terms in the above can be sharp.
HW: prove that the number of triangles on n points in the plane with unit area is O(n^7/3).
note that a similar method works for the following variations: bound for the number of isosceles triangles on n points, triangles containing a fixed angle alpha.
Ex4: Show that the crossing lemma is sharp i.e for every k and n integers give a graph with kn edges whose crossing number is O(k^3n).
Ex5: Guess and prove a multigraph version of crossing lemma where every edge can occur at most k times.
Ex6: Use the crossing lemma to show that the size of the largest convex set in an n by n grid is O(n^2/3). (Recall: In class Manoj showed a solution using vectors of length at most n^1/3 etc... now please try to find a proof involving crossing lemma).
Ex7 (easy!): find an upper bound for the number of incidences of m points on n lines in R^3?