Feb 14, 3:30pm, Wean 8220

Jacob Fox, MIT

Arrangements of curves and partially ordered sets

Jacob Fox, MIT

Arrangements of curves and partially ordered sets

Abstract:

A string graph is a graph that can be obtained as the intersection
graph of curves (strings) in the plane. Despite much attention over the
past half century, the structure of string graphs is poorly understood.
The incomparability graph of a partially ordered set (P,<) has vertex
set P and two elements of P are adjacent if and only if they are
incomparable. It is known that every incomparability graph is a string
graph, and that the converse is not true. Nevertheless, we demonstrate
an intimate relationship between these two types of graphs: we prove
that for every collection C of curves in the plane whose intersection
graph is dense, we can pick for each curve s in C a subcurve s' such
that the intersection graph of the collection of curves s' is a dense
incomparability graph. It follows that every dense string graph has a
dense subgraph which is an incomparability graph. Utilizing this
connection between arrangements of curves and partially ordered sets,
we make progress on several extremal problems for string graphs and
crossing edge patterns in graphs drawn in the plane. Joint work with
Janos Pach.