Title: Extremal questions about matchstick graphs and penny graphs

Speaker: Konrad Swanepoel, London School of Economics

Date and time: 2pm (New York time), Tuesday, April 4, 2023

Place: On Zoom (details provided on the seminar mailing list)

A penny graph is the intersection graph of a packing of circles of diameter 1. These graphs, also called minimum-distance graphs, were introduced by Erdös in 1946, who asked for the maximum possible number of edges in a penny graph with $n$ vertices. This problem was fully solved by Harborth in 1974, who in turn introduced the more general notion of a matchstick graph. A matchstick graph is a plane graph drawn with straight-line segments of unit length. Harborth conjectured in 1986 that the same maximum number of edges occurs for matchstick graphs as for penny graphs. I will discuss this conjecture, recently solved, and a number of related unsolved extremal problems.

Joint work with Jérémy Lavollée.