Activities This Week

Krieger’s generator theorem shows that any free invertible ergodic measure preserving action $(Y,\mu, S)$ can be modelled by $A^Z$ (equipped with the shift action) provided the natural entropy constraint is satisfied; we call such systems (here it is $A^Z$) universal. Along with Tom Meyerovitch, we establish general specification like conditions under which $Z^d$-dynamical systems are universal. These conditions are general enough to prove that

1) A self-homeomorphism with almost weak specification on a compact metric space (answering a question by Quas and Soo and recovering recent results by David Burguet) 2) Proper colourings of the $Z^d$ lattice with more than two colours and the domino tilings of the $Z^2$ lattice (answering a question by Şahin and Robinson) are universal. Our results also extend to the almost Borel category giving partial answers to some questions by Gao and Jackson.

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.