The Induced Subgraph Order on Unlabelled Graphs A differential poset is a partially ordered set with raising and lowering operators U and D which satisfy the commutation relation DUUDrI for some constant r. This notion may be generalized to deal with the case in which there exist sequences of constants q_n_ngeq 0 and r_n_ngeq 0 such that for any poset element x of rank n, DU(x)  q_n UD(x)  r_nx. Here, we introduce natural raising and lowering operators such that the set of unlabelled graphs, ordered by Gleq H if and only if G is isomorphic to an induced subgraph of H, is a generalized differential poset with q_n2 and r_n  2n. This allows one to apply a number of enumerative results regarding walk enumeration to the poset of induced subgraphs.

Ordered graphs and large bicliques in intersection graphs of curves. An ordered graph G_ 0 such that every ordered graph on n vertices that does not contain a monotone path of length k as an induced subgraph has a vertex of degree at least c_kn, or its complement has a biclique of size at least c_knlog n. A similar result holds for ordered graphs containing no induced ordered subgraph isomorphic to a fixed ordered matching.  As a consequence, we give a short combinatorial proof of the following theorem of Fox and Pach. There exists a constant cu003e0 such the intersection graph G of any collection of n xmonotone curves in the plane has a biclique of size at least cnlog n or its complement contains a biclique of size at least cn. (A curve is called xmonotone if every vertical line intersects it in at most one point.) We also prove that if G has at most left(frac14 epsilonright)nchoose 2 edges for some epsilonu003e0, then overlineG contains a linear sized biclique. We show that this statement does not remain true if we replace frac14 by any larger constants.