Noam Zeilberger: Connections between lambda calculus and graphs on surfaces

Datum objave: 14. 12. 2015
Seminar za temelje matematike in teoretično računalništvo
Torek, 15. 12. 2015, od 12:30 do 14:00, Plemljev seminar, Jadranska 19

[Pozor: dobimo se ob 12:30, da damo kolegom iz seminarja za diskretno matematiko čas za kosilo.] 

Abstract: I would like to talk about some recent, somewhat unexpected connections between lambda calculus and the theory of embedded graphs that were discovered via combinatorics. After a quick survey of these connections, I will focus on the relatively simple case of the bijection between linear lambda terms and rooted trivalent maps on oriented surfaces, and try to work slowly to explain that correspondence while presenting enough background to remain accessible to both logicians and combinatorists. If time permits, I will also discuss the application of this correspondence to the enumeration of bridgeless trivalent maps.