| [home] - [up] |
Abstract: The crossing number of a graph G is the minimum number of edge crossings in a drawing of G in the plane (the edges are drawn by arbitrary arcs, not only straight segments). We discuss techniques for bounding the crossing number above and below, mainly due to Leighton and his co-workers. In particular, we explain interesting connections between the crossing number and the edge expansion of a graph. We also present results from a joint work with Petr Kolman, concerning a tantalizing problem due to Pach and Toth on the relation of the crossing number to the pair-crossing number, that is, the minimum number of pairs of edges that have to cross in a drawing of the considered graph. Few other fascinating questions will be mentioned as well.
Colloquium - 16:00
Abstract: We don't know the proofs in THE BOOK (in which God, according to Erdos, maintains the perfect proofs for mathematical theorems), but sometimes we do have the joy to learn about proofs that might well be in THE BOOK.
In this lecture, I want to share with you the excitement about a few proofs that Martin Aigner and I have newly learned about in connection with our on-going book project.
Thus we'll discuss new ways to enumerate the rationals, prove that e^4 is irrational, and count lattice points by setting up candles.