Lena Yuditsky (BGU)

Tuesday, November 27, 2018, 15:45 – 16:45, 201

Please Note the Unusual Time and Place!


A string graph is the intersection graph of a family of continuous arcs in the plane. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on $n$ vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). As a corollary, we obtain that almost all string graphs on $n$ vertices are intersection graphs of plane convex sets.

This is a joint work with Janos Pach and Bruce Reed.