Georgia Institute of Technology College of Sciences

In 1865, Sylvester posed the following problem: For a region R in the plane,let q(R) denote the probability that four points chosen at random from Rform a convex quadrilateral. What is the infimum q* of q(R) taken over allregions R? The number q* is known as Sylvester's Four Point Problem Constant(Sylvester's Constant for short). At first sight, it is hard to imagine howto find reasonable estimates for q*. Fortunately, Scheinerman and Wilf foundthat Sylvester's Constant is intimately related to another fundamentalconstant in discrete geometry. The rectilinear crossing number of rcr(K_n)the complete graph K_n is the minimum number of crossings of edges in adrawing of K_n in the plane in which every edge is a straight segment. Itis not difficult to show that the limit as n goes to infinity ofrcr(K_n)/{n\choose 4} exists; this is the rectilinear crossing numberconstant RCR. Scheinerman and Wilf proved a surprising connection betweenthese constants: q* = RCR. Finding estimates of rcr(K_n) seems like a moreapproachable task. A major breakthrough was achieved in 2003 by Lovasz,Vesztergombi, Wagner, and Welzl, and simultaneously by Abrego andFernandez-Merchant, who unveiled an intimate connection of rcr(K_n) withanother classical problem of discrete geometry, namely the number of

This is the third session in this series and a special effort will be made to make it self contained ... to the fullest extent possible.With Felsner and Li, we proved that the dimension of the adjacency poset of a graph is bounded as a function of the genus. For planar graphs, we have an upper bound of 8 and for outerplanar graphs, an upper bound of 5. For lower bounds, we have respectively 5 and 4. However, for bipartite planar graphs, we have an upper bound of 4, which is best possible. The proof of this last result uses the Brightwell/Trotter work on the dimension of thevertex/edge/face poset of a planar graph, and led to the following conjecture:For each h, there exists a constant c_h so that if P is a poset of height h and the cover graph of P is planar, then the dimension of P is at most c_h.With Stefan Felsner, we have recently resolved this conjecture in the affirmative. From below, we know from a construction of Kelly that c_h must grow linearly with h.

Slightly modifying a quote of Paul Erdos: The problem for graphs we solve this week. The corresponding problem for posets will take longer. As one example, testing a graph to determine if it is planar is linear in the number of edges. Testing an order (Hasse) diagram to determine if it is planar is NP-complete. As a second example, it is NP-complete to determine whether a graph is a cover graph. With these remarks in mind, we present some results, mostly new but some classic, regarding posets with planar cover graphs and planar diagrams. The most recent result is that for every h, there is a constant c_h so that if P is a poset of height h and the cover graph of P is planar, then the dimension of P is at most c_h.

Richter and Salazar conjectured that graphs that are critical for a fixed crossing number k have bounded bandwidth. A weaker well-known conjecture of Richter is that their maximum degree is bounded in terms of k. We disprove these conjectures for every k >170, by providing examples of k-crossing-critical graphs with arbitrarily large maximum degree, and explore the structure of such graphs.