The seminar meets on Tuesdays, 10:45-11:45, in -101

2018–19–B meetings

Jan 15 Polygonizations for Disjoint Line Segments Csaba Toth (CSUN)

Given a planar straight-line graph $G=(V,E)$ in $\mathbb{R}^2$, a circumscribing polygon of $G$ is a simple polygon $P$ whose vertex set is $V$, and every edge in $E$ is either an edge or an internal diagonal of $P$. A circumscribing polygon is a \emph{polygonization} for $G$ if every edge in $E$ is an edge of $P$.

We prove that every arrangement of $n$ disjoint line segments in the plane (i.e., a geometric perfect matching) has a subset of size $\Omega(\sqrt{n})$ that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to $\mathbb{R}^3$.

We show that it is NP-complete to decide whether a given graph $G$ admits a circumscribing polygon, even if $G$ is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization. (Joint work with Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, and Diane L. Souvaine.)

Jan 15, 14:15–15:15 Simple juntas for shifted families Andrey Kupavskii (Oxford)

We say that a family F of k-element sets is a j-junta if there is a set J of size j such that, for any set, its presence in F depends on its intersection with J only. Approximating arbitrary families by j-juntas with small j is a recent powerful technique in extremal set theory. The weak point of all known approximation by juntas results is that they work in the range n>Ck, where C is an extremely fast growing function of the input parameters. In this talk, we present a simple and essentially best possible junta approximation result for an important class of families, called shifted. As an application, we present some progress in the question of Aharoni and Howard on families with no cross-matching. Joint work with Peter Frankl.

Recurring Seminar run by Dr. Charles Wolf