Combinatorics Seminar External Ical Atom

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.)

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.

Let $F = (F_1, \ldots, F_m)$ be a collection of (not neccessarily distinct) sets. A (partial) rainbow set for $F$ is a set of the form $R = {x_{i_1}, \ldots, x_{i_k}}$ of distinct elements, where $1 \leq i_1 < \cdots < i_k \leq m$ and $x_{i_j}$ is an element of $F_{i_j}$. We are interested in the following question: given sufficiently many independent sets of size $a$ in a graph belonging to a certain class, there exists a rainbow independent set of size $b$. In this talk, I will present our recent results on this question, mainly regarding $H$-(induced) free graphs and graphs of bounded maximum degree. This is joint work with Ron Aharoni, Joseph Briggs and Jinha Kim.

A Hamiltonian decomposition of $\Gamma$ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph $K_n$ on an odd number of vertices $n$ has a Hamiltonian decomposition. This result was recently greatly extended by Kuhn and Osthus. They proved that every $r$-regular $n$-vertex graph $\Gamma$ with even degree $r=cn$ for some fixed $c>1/2$ has a Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In this talk we address the natural question of estimating $H(\Gamma)$, the number of such decompositions of $\Gamma$. The main result is that $H(\Gamma)=r^{(1+o(1))nr/2}$. In particular, the number of Hamiltonian decompositions of $K_n$ is $n^{(1+o(1))n^2/2}$.

Joint work with Zur Luria and Benny Sudakov.