Skip to main content

Lambda calculus and the Four Colour Theorem

Noam Zeilberger ( University of Birmingham )

The enumerative study of graphs on surfaces (or "maps") began in the
1960s with the pioneering work of Bill Tutte, who figured out how to
count various families of planar maps as the initial steps of a
long-term strategy for approaching the Four Colour Problem. Tutte's
approach was ultimately side-stepped by the Appel-Haken proof of 4CT,
but enumeration of maps remains a very active area of combinatorics,
with links to wide-ranging domains such as algebraic geometry, knot
theory, mathematical physics... and apparently lambda calculus! In
this talk I will survey some of the surprisingly tight connections
that have been found over recent years between the combinatorics of
(rooted) maps and the combinatorics of (linear) lambda terms, and
place them within the context of older ties between logic and geometry
such as string diagrams for monoidal categories, and proof nets for
linear logic.  I hope to convey how these newly discovered links
suggest some fascinating questions for research in both directions,
including a tight connection between typing of lambda terms and
coloring of maps.  Only a basic background in lambda calculus will be

Share this: