Combinatorics Seminar - Spring '22

When: Sunday, February 27, 10am

Where: Schreiber 309

Speaker: Rom Pinchasi, Technion

Title: Covering the Edges of a Complete Geometric Graph with Convex Polygons


Given a set $P$ of $n \geq 3$ points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in $P$ such that the edges of all these polygons contain all the ${n \choose 2}$ straight line segments determined by the points of $P$. We show that if $n$ is odd, the answer is $\frac{n^2-1}{8}$ regardless of the choice of $P$. The answer in the case where $n$ is even depends on the choice of $P$ and not only on $n$. The talk, that is meant to be enjoyable, will focus on presenting the various aspects of the problem and the proof as well as their combinatorial context.

Joint work with Oren Yerushalmi.