Schedule for: 18w5058 - Extremal Problems in Combinatorial Geometry

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

The Sylvester-Gallai theorem states that if a finite set of points in the real plane is not contained in a line, then it spans at least one ordinary line, i.e. a line containing exactly two of the points. In fact, such a set always spans a linear number of ordinary lines, and that is best possible because there are point sets on cubic curves that determine only a linear number of ordinary lines. One can consider the same question in three-dimensional space. By projection, the results in the plane hold word-for-word in space. But note that the known constructions with a linear number of ordinary lines are contained in a plane. I will show that if one assumes that the point set does not have too many points on a plane, then it spans a quadratic number of ordinary lines. More precisely, for any a<1 there is a c>0 such that if we have n points in space with at most an points on a plane, then there are at least cn^2 ordinary lines. The proof uses projection, Beck’s theorem, and a variant of the Sylvester-Gallai theorem.

Pach showed that every d+1 sets of points Q_1,..,Q_{d+1} in R^d contain linearly-sized subsets P_i in Q_i such that all the transversal simplices that they span intersect. We show, by means of an example, that a topological extension of Pach's theorem does not hold with subsets of size C(log n)^{1/(d-1)}. We show that this is tight in dimension 2, for all surfaces other than S^2. Surprisingly, the optimal bound for S^2 is (log n)^{1/2}. This improves upon results of Barany, Meshulam, Nevo, Tancer. Joint work with Alfredo Hubard.

A {\em convex geometric hypergraph} or {\em cgh} is a hypergraph whose vertices form a convex polygon in the plane. It will be convenient to place the vertices in clockwise order on the vertices of a regular polygon $\vb{\gamma}_n$ (for $n \ge 3$), and to write $v_1 < v_2 < \dots < v_n < v_1$ to denote that the clockwise ordering of the vertices $\vb{\gamma}_n$ is $(v_1,v_2,\dots,v_n,v_1)$. We write cgg (cgh, cg $r$-graph) as abbreviation for convex geometric graph (convex geometric hypergraph, convex geometric $r$-graph), Given an $r$-uniform cgh $F$, let $\ex_{\circlearrowright}(n,F)$ be the maximum number of edges in an $r$-uniform cgh on $n$ vertices that does not contain $F$. In the case of graphs, this problem has a rich history with applications to a variety of problems in combinatorial geometry. Extremal questions for convex geometric graphs and hypergraphs are connected to a variety of topics in discrete geometry (see for instance Bra{\ss}, Rote, and Swanepoel~2001, %\cite{Brass-Rote-Swanepoel}, Pach and Pinchasi~2013, %\cite{Pach-Pinchasi}) and questions around the triangle removal problem (see Section 4.3 in Aronov, Dujmovi\v{c}, Morin, Ooms and da Silveira~2017, %\cite{Aronov}, Gowers and Long~2016 %\cite{Gowers-Long} and Loh~2016). %\cite{Loh}) We focus on the case that $F$ is a certain type of embedding of a tight path or matching. We obtain in many cases asymptotically sharp estimates for $\ex_{\circlearrowright}(n,F)$, generalizing classical results of Kupitz and Perles. As a consequence, we show that the number of edges in an $n$-vertex $r$-graph containing no tight $k$-edge path is at most $$\frac{(k-1)(r - 1)}{r}{n \choose r - 1}.$$ The case $r = 2$ is the Erd\H{o}s-Gallai Theorem. For $r \geq 3$, this is the first non-trivial upper bound on the extremal number for tight paths in $r$-graphs which applies for all $k \ge 3$, and marks progress towards Kalai's tight tree conjecture.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

The crossing number $cr(G)$ of a graph $G$ is the minimum number of crossings over all possible drawings of $G$ on the plane. According to the Crossing Lemma, for any simple graph $G$ with $n$ vertices and $e\ge 4n$ edges, $cr(G)\ge {1\over 64}{e^3\over n^2}$. Clearly, this result does not hold for multigraphs (graphs with parallel edges or loops). We find natural conditions that imply the analogue of the Crossing Lemma for multigraphs.

I will discuss a recent improvement to the unit distance problem in three dimensions. A key step is a new method for cutting circles in R^3 into pseudo-segments, which leads to improved incidence bounds for points and circles.

The plan is to review some better or less known results about incidences of sufficiently small noncollinear point sets with straight lines. The two best known and in some sense sharp results are the theorem on distinct directions proved in the 90s by T. Szonyi and the recent Szemeredi–Trotter type incidence theorem by S. Stevens and F. de Zeeuw. Can further progress be expected to come reasonably soon?

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

In 2000, Elekes and R\’onyai proved the following statement. Let $f$ be a real bivariate polynomial. Then one of the following holds: Either, for every pair of set $A,B$, each of $n$ real numbers, $|f(A\times B)|=\omega(n)$, with constant of proportionality that depends only on the degree of $f$, or, otherwise, $f$ must be of one of the special forms $f(x,y)=h(p(x)+q(y))$, or $f(x,y)=h(p(x)\cdot q(y))$, for some univariate polynomials $p,q,h$ over $\R$. Their result was later sharpened (by Raz, Sharir, and Solymosi), and generalized to the case of polynomials of three variables (by Raz, Sharir, and De Zeeuw). In the talk I will present (and sketch the proof of) an analogous statement for $d$-variate polynomial functions. The talk is based on a joint work with Zvi Shemtov.

Caratheodory's classic result says that if a point $p$ lies in the convex hull of a set $P \subset R^d$, then it lies in the convex hull of a subset $Q \subset P$ of size at most $d+1$. What happens if we want a subset $Q$ of size $k < d+1$ such that $p \in conv Q$? In general, this is impossible as $conv Q$ is too low dimensional. We offer some remedy: $p$ is close, in an appropriate sense, to $conv Q$ for some subset $Q$ of size $k$. Similar results hold for Tverberg's theorem as well. This is joint work with Nabil Mustafa.

In patrolling problems, several mobile agents with predefined speeds move in the given terrain and try to ensure that every point is (perpetually) visited at least once in any time period of unit length. Problems of this kind are studied with various motivations and in various forms: the agents may have the same or different speeds; the terrain may be a line, a cycle, a tree, or more general graphs; the points to be visited frequently may be all of the terrain or its subset. Finding an optimal patrolling schedule is not straightforward, even in the simplest settings. I will introduce some recent results and open questions about properties, bounds, and algorithms for optimal patrolling. Partly based on joint work with Yusuke Kobayashi, Hideaki Noshiro, and Makoto Soejima.

Adapting the framework of Bourgain-Chang, we (in a joint work with Brandon Hanson and Dmitry Zhelezov) present a new sum-product type estimate over the rationals which exhibits unbounded growth. As an application, it follows that if a point set is a direct product AxA for a set of rationals A, and A has a small product set, then we get a better incidence bound for such a point set than the one given by the Szemeredi-Trotter.

We present several results about coloring geometric hypergraphs that are defined by pseudo-disk arrangements. In particular, we prove that the intersection hypergraph of a finite family of pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with 4 colors. Along the way we prove that the corresponding Delaunay-graph is planar. Our results serve as a common generalization and strengthening of many earlier results, including ones about coloring points with respect to pseudo-disks, coloring pseudo-disks with respect to points and coloring disks with respect to disks.

We study several problems concerning convex polygons whose vertices lie on a Cartesian product of two sets of $n$ real numbers. First, we prove that every such Cartesian product contains a convex polygon with $\Omega(\log n)$ vertices and that this bound is asymptotically tight; the upper bound construction generalizes to $d$-dimensions and yields an upper bound of $O(\log^{d-1}n)$. Second, we present polynomial-time algorithms for computing the largest convex polygon that contains no two points of the same $x$- or $y$-coordinate. These algorithms give a constant approximation ratio for the general case. Finally, we present exponential bounds on the maximum number of convex polygons in these grids that are tight up to polynomial factors. (Joint work with Jean-Lou De Carufel, Wouter Meulemans, Tim Ophelders, Claire Pennarun, and Sander Verdonschot.)

We show that for any set $P$ of $n$ points in the plane and $\eps>0$ there exists a set of $o\left(\frac{1}{\eps^{1.7}}\right)$ points in the plane that pierce every convex set $K$ with $|K\cap P|\geq \eps |P|$. This is the first improvement of the 1992 upper bound $O\left(\frac{1}{\eps^2}\right)$ of Alon, Bárány, Füredi, and Kleitman.

Suppose we are sending out k robots from 0 to search the real line at a constant speed (with turns) to find a target at an unknown location; f of the robots are faulty, meaning that they fail to report the target although visiting its location. The goal is to find the target in time at most lambda |d|, if the target is located at d, |d|>1, for lambda as small as possible. In this work, we find a tight lower bound for lambda. This is joint work with Emo Welzl.

In a seminal paper Kalai (1983) extended the notion of a tree to higher dimensions. Formally, an n-vertex d-dimensional hypertee is a Q-acyclic simplicial complex with a full (d-1) dimensional skeleton and {n-1 \choose d} d-dimensional faces. We will use instead an equivalent intuitive definition that relies only on elementary linear algebra. In this talk I will try to give a flavor of these exciting concepts. I will discuss several of the many open problems that arise here and describe some of our new discoveries. My coauthors in the relevant papers are: R. Meshulam, Y. Peled, M. Rosenthal, I. Newman and Y. Rabinovich.

The topological KKMS Theorem is a powerful extension of Brouwer's Fixed-Point Theorem, which was proved by Shapley in 1973 in the context of game theory. We prove a colorful and polytopal generalization of the KKMS Theorem, and show that our theorem implies some seemingly unrelated results in discrete geometry and combinatorics involving colorful settings. For example, we apply our theorem to provide a new proof of the Colorful Caratheodory Theorem due to Barany, and also to obtain an upper bound on the piercing numbers in colorful d-interval families, extending results of Tardos, Kaiser and Alon for the non-colored case. We further apply our theorem to questions regarding envy-free fair division of goods among a set of players. Joint with Florian Frick.

A drawing of a graph on a surface is independently even if every pair of independent edges in the drawing crosses an even number of times. The $\mathbb{Z}_2$-genus of a graph $G$ is the minimum $g$ such that $G$ has an independently even drawing on the orientable surface of genus $g$. An unpublished result by Robertson and Seymour implies that for every $t$, every graph of sufficiently large genus contains as a minor a projective $t\times t$ grid or one of the following so-called $t$-Kuratowski graphs: $K_{3,t}$, or $t$ copies of $K_5$ or $K_{3,3}$ sharing at most $2$ common vertices. We show that the $\mathbb{Z}_2$-genus of graphs in these families is unbounded in $t$; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its $\mathbb{Z}_2$-genus, solving a problem posed by Schaefer and \v{S}tefankovi\v{c}, and giving an approximate version of the Hanani-Tutte theorem on surfaces. Joint work with J. Kyncl.

Nandakumar raised several interesting questions on plane tilings. Among them is the problem if the plane can be tiled with pairwise noncongruent triangles that are both equal area and equal perimeter. We prove that this is not possible and survey related results on plane tilings including relaxed versions of this problem. The results in the talk are joint with Andrey Kupavskii and Janos Pach.

It was shown by Raz-Sharir-De Zeeuw (2016) that the number of coplanar quadruples among n points on an algebraic curve in complex 3-space not containing a planar component or a component of degree 4, is O(n^{8/3}). We complement their result by characterizing the degree 4 space curves in which n points on the curve always have a subcubic number of coplanar quadruples. This also gives a characterization of the plane curves of degree 3 and 4 in which n points on the curve always have a subcubic number of concyclic quadruples. We use the 4-dimensional Elekes-Szabo theorem of Raz-Sharir-De Zeeuw and some old results from classical invariant theory. Simeon Ball (2016) showed that a set spanning real 3-space, no 3 collinear, with only Kn^2 ordinary planes, lies on the intersection of two quadrics, up to O(K) points. His proof is based on results of Green and Tao, and also generalizes their proof to 3-space. We find a significant simplification of his proof that avoids 3-dimensional dual configurations, using Bezout's theorem and the above-mentioned results from classical invariant theory. This is joint work with Aaron Lin.

Suppose we have a finite family of convex sets in R^d such that no more than m of them have a point in common (m>d). What is the maximum number of intersecting (d+1)-tuples of sets from the family? The (precise) answer is known due to Gil Kalai and Jürgen Eckhoff. For d=2 and m=3 we show that the convexity assumption can be weakened. In fact, to get a quadratic upper bound on the number of intersecting triples of sets, it is enough to assume that the intersection of every two sets from the family as well as the intersection of every three sets from the family is either empty, or open with bounded number of connected components. Moreover, the Euclidean plane can be replaced by any 2-dim connected manifold.

A recent extension of Guth (2015) to the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial, for a given set of $k$-dimensional varieties in ${\reals}^d$, which subdivides space into open cells each of which meeting only a small fraction of the total number of varieties. For most instances, it is unknown how to obtain an explicit representation of such a partitioning polynomial (and how to construct it efficiently). This, in particular, applies to the (simple) case of lines in 3-space. In this work we present an efficient algorithmic (but somewhat suboptimal) construction for this setting, under the assumption that the lines are non-vertical and pairwise disjoint. We then revisit the problem of eliminating depth cycles among $n$ non-vertical pairwise disjoint triangles in $3$-space, recently been studied by Aronov etal. (2017) and de Berg (2017). Our main result is an algorithmic $O(n^{5/3+\eps})$ bound, for any $\eps > 0$, on the number of pieces one needs to cut the triangles such that the depth relation they induce does not contain cycles. Joint work with Boris Aronov.

Pawlik et al. (2013) proved that a particular family of triangle-free graphs with chromatic number $\Theta(\log\log n)$ (where $n$ is the number of vertices) can be represented as intersection graphs of L-figures in the plane. I will sketch a proof of the matching upper bound: all triangle-free intersection graphs of L-figures have chromatic number $O(\log\log n)$. This improves the previous bound of $O(\log n)$ (McGuinness, 1996) and is a little step towards obtaining analogous improvements for more general and better known classes of geometric intersection graphs, such as segment graphs and general string graphs.

A {\em string graph} is the intersection graph of a family of continuous arcs in the plane. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of {\em almost all} string graphs on $n$ vertices can be partitioned into {\em five} cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). As a corollary, we obtain that {\em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets. This is a joint work with Janos Pach and Bruce Reed.

Let d and k be integers with 1 <= k <= d-1. Let Lambda be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in the intersection of Lambda with K. In particular, our results imply that the minimum number of kdimensional linear subspaces needed to cover the d-dimensional n * ... * n$ grid is at least Omega(n^(d(d-k)/(d-1)-epsilon)) and at most O(n^(d(d-k)/(d-1))), where epsilon > 0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book of Brass, Moser, and Pach. We use these new results to improve the best known lower bound for the maximum number of point-hyperplane incidences by Brass and Knauer. This is a joint work with Josef Cibulka and Pavel Valtr.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.