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).
Ex3: 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).
Show that both terms in the above can be sharp.
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?