Perfection and Geometry

János Pach, Rényi Institute, Budapest

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

...and on Zoom, details on the seminar mailing list

Date and time: 6pm (New York time), Tuesday, November 15, 2022

The chromatic number of every graph is at least as large as its clique number. For perfect graphs, these two numbers coincide. Most graphs are far from perfect, but many geometrically defined graphs are "nearly perfect" in the following sense: their chromatic numbers are bounded by a function $f$ of their clique numbers. How far these graphs are from being perfect, can be measured by the growth rate of $f$. After giving a whirlwind tour of the subject, we outline the proofs of some new results related to arrangements of curves in the plane, and we mention some open problems.