Schedule for: 22w5009 - Extremal Combinatorics and Geometry

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

In the {\it max-min allocation problem} a set $P$ of players are to be allocated disjoint subsets of a set $R$ of indivisible resources, such that the minimum utility among all players is maximized. In the {\it restricted} variant, also known as the {\it Santa Claus problem}, each resource (``toy'') has an intrinsic positive value, and each player (``child'') covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching. Bez\'akov\'a and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than $2$, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the {\it Configuration LP} of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs. Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of $3.808$ for the general problem to $3.534$. We also address the $(1,\varepsilon)$-restricted version, in which resources can take only two values, and improve the integrality gap in most cases. This is based on joint work with Tibor Szab\'o.

A graph {\it has a pair $(m,f)$} if it has an induced subgraph on $m$ vertices and $f$ edges. We write $(n,e)\rightarrow (m,f)$ if any graph on $n$ vertices and $e$ edges has a pair $(m,f)$. Let $$S(n,m,f)=\{e: ~(n,e)\rightarrow (m,f)\} ~{\rm and}$$ $$\sigma(m,f) = \limsup_{n\rightarrow \infty}\frac{ |S(n,m,f)|}{\binom{n}{2}}.$$ These notions were first introduced and investigated by Erd\H{o}s, F\"uredi, Rothschild, and S\'os. They found five pairs $(m,f)$ with $\sigma(m,f)=1$ and showed that for all other pairs $\sigma(m,f)\leq 2/3$. We extend these results in two directions. \\ First, in a joint work with Weber, we show that not only $\sigma(m,f)$ can be zero, but also $S(n,m,f)$ could be empty for some pairs $(m,f)$ and any sufficiently large $n$. We call such pairs $(m,f)$ {\it absolutely avoidable}.\\ Second, we consider a natural analogue $\sigma_r(m,f)$ of $\sigma(m,f)$ in the setting of $r$-uniform hypergraphs. Weber showed that for any $r\geq 3$ and $m>r$, $\sigma_r(m,f)=0$ for most values of $f$. Surprisingly, it was not immediately clear whether there are nontrivial pairs $(m,f)$, $(f\neq 0$, $f\neq \binom{m}{r}$, $r\geq 3$), for which $\sigma_r(m,f)>0$. In a joint work with Balogh, Clemen, and Weber we show that $\sigma_3(6,10)>0$ and conjecture that in the $3$-uniform case $(6,10)$ is the only such pair.

In 1954 Kővári, Sós, Turán showed that every n-vertex graph not containing K_{s,t} has at most O(n^{2-1/s}) edges. We construct graphs matching this bound with t≈9s, improving on factorial-type bounds. In this talk, I will explain geometric ideas behind the construction.

I will survey some recent results in lens cutting, and how they have been used in incidence geometry and harmonic analysis. This includes joint work with Esther Ezra, Malabika Pramanik, Orit Raz, Micha Sharir, and Tongou Yang.

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 PDC front desk for a guided tour of The Banff Centre campus.

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!

If n points are drawn independently from the uniform measure over a convex set, then the expectation of the number of points on the boundary of the convex hull is around n W_{1/n}, where W_{1/n}, is the so called wet part of the convex set. I will discuss to what extent does this phenomenon depend on the assumption that the measure is uniform over a convex set. It turns out, that this is closely related to a epsilon-nets. I will further discuss epsilon nets for relatively large epsilon in the context of bounded degree polynomials.

For a set P of n points in R^d, for any d ≥ 2, a hyperplane h is called k-rich with respect to P if it contains at least k points of P. We show that if the number of k-rich hyperplanes in R^d, d ≥ 3, is 'large', then there exists a (d−2)-flat that contains 'many' points of P. We also present upper bound constructions that give instances in which is our result tight. An extension of our analysis yields similar lower bounds for k-rich spheres. Based on joint work with Micha Sharir.

Many classic results in combinatorial geometry and topological combinatorics have colorful versions. In this talk, we will discuss how to obtain sparse generalizations of such results. We will focus sparse colorful versions of Helly’s theorem, Caratheodory’s theorem, and the Knaster-Kuratowski-Mazurkiewicz theorem, and the key ideas behind their proofs.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

A binary code of positive rate is a subset of {0,1}^n with size exponentially large in n. In any such code, one can find two codewords sharing the same majority bit and thus a common subsequence of length at least n/2. Surprisingly, whether this trivial constant 1/2 could be improved was a longstanding open problem in coding theory, and we solve it in a strengthened form. That is, we show that there exist A, c > 0 such that among any 2^{(log n)^A} bitstrings of length n, some two have a common subsequence of length at least (1/2 + c)n. In the language of coding theory, this means that the zero-rate threshold for coding against adversarial bit deletion is strictly less than 1/2. The main idea of the proof is to develop a classification system for bitstrings according to their "local oscillation frequencies," very roughly analogous to Fourier phases; one key ingredient of this classification is a new variant of the string regularity lemma of Axenovitch, Person, and Puzynina. Joint work with Venkatesan Guruswami and Ray Li.

Suppose n runners are running on a circular track of circumference 1, with all runners starting at the same time and place. Each runner proceeds at their own constant speed. We say that a runner is lonely at some point in time if the distance around the track to the nearest other runner is at least 1/n at that point in time. For example, if there two runners then there will come a moment when they are at anitpodal points on the track, and at this moment both runners are lonely. The lonely runner conjecture asserts that every runner is lonely at some point in time. A coprime matching of two sets of integers is a matching that pairs every element of one set with a coprime element of the other set. We present a recent partial result on the lonely runner conjecture. Coprime matchings of intervals of integers play an central role in the proof of this result. Joint work with Fei Peng

In the first part of the talk, I will describe the main ideas behind the recent resolution of the Kahn-Kalai conjecture, which relates thresholds of increasing properties to expectation thresholds. In particular, I will introduce the notion of “minimal fragments” and the key lemma in the proof (which also underlines the proof of Talagrand’s conjecture on selector processes). This is based on joint works with Jinyoung Park. I will then explain how to use these ideas to improve a result of Fox, Pach and Suk on sunflowers in systems of k-sets with bounded VC-dimension. The same ideas can be used to improve or simplify proofs of several previous results on thresholds and sunflowers.

It is known that the edge set of every cubic graph can be partitioned into two linear forests where each path is short (of constant size). A conjecture of Wormald from 80's asks for such a partition where the two forests are isomorphic (we no longer insist on having short paths, although that is also an open question). Note that this also can be phrased as an edge-colouring question. Is it possible to colour the edge set of a cubic graph by red and blue such that the two monochromatic components induce isomorphic linear forests? Recently we proved this for all connected graphs on sufficiently large number of vertices. This is joint work with Gal Kronenberg, Shoham Letzter and Alexey Pokrovskiy.

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

A celebrated theorem of Spencer states that for every set system $S_1,\dots,S_m \subseteq [n]$, there exists a coloring of the ground set with $\{\pm 1\}$ with discrepancy $O(\sqrt{n\log(m/n+2)})$. Algorithms for finding such colorings in polynomial time were designed nearly 25 years later, starting with a breakthrough work of Bansal. I will discuss recent work, joint with Ashwin Sah and Mehtaab Sawhney, in which we provide an algorithm for finding such a coloring in nearly input-sparsity time $\tilde{O}(n+\sum_{i=1}^{m}|S_i|)$.

An ordered graph is a graph equipped with a total order on the vertices. By analogy to the well-known Gyárfás-Sumner conjecture, we can ask for what ordered graphs H is the class of H-free ordered graphs (i.e., ordered graphs excluding H as an induced ordered subgraph) χ-bounded. In a joint work with Marcin Briański and James Davies, we prove that the class of M-free ordered graphs is χ-bounded for every ordered matching M. This confirms a conjecture by István Tomon. We also review what is known on coloring ordered graphs with excluded (induced) ordered subgraphs, which is still a relatively little explored area.

We prove that given a finite collection of cylinders in R^3 with the property that any two of them intersect, there is a line intersecting an alpha-fraction of the cylinders where alpha=1/14. This is a special case of an interesting conjecture.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

I will speak about some (perhaps less well known) open problems in arithmetic combinatorics of a geometric flavour.

In 1973, Erdős conjectured the existence of high girth (n,3,2)-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős' conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth (n,q,r)-Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of submatchings (which we view as a hypergraph H where V(H)=E(G)). Our first main result is a common generalization of the classical theorems of Pippenger (for finding an almost perfect matching) and Ajtai, Komlós, Pintz, Spencer, and Szemerédi (for finding an independent set in girth five hypergraphs). More generally, we prove this for coloring and even list coloring, and also generalize this further to when H is a hypergraph with small codegrees (for which high girth designs is a specific instance). A number of applications in various areas follow from our main results including: Latin squares, high dimensional permutations, and rainbow matchings. This is joint work with Luke Postle.

Two permutations are intersecting if they both map some $i$ to the same point, equivalently, permutations $\sigma$ and $\pi$ are intersecting if and only if $\pi^{-1}\sigma$ has a fixed point. A set of permutations is called intersecting if any two permutations in the set are intersecting. For any transitive group the stabilizer of a point is an intersecting set. The {\bf intersection density} of a permutation group is the ratio of the size of the largest intersecting set in the group, to the size of the stabilizer of a point. If the intersection density of a group is 1, then the stabilizer of a point is an intersecting set of maximum size. Such groups are said to have the {\bf Erd\H{o}s-Ko-Rado property}. One effective way to determine the intersection density of a group is build a graph whose vertices are the elements of the group and the edges are defined so that the cocliques (or the independent sets) in the graph are exactly the intersecting sets in the group. This graph is called the {\bf derangement graph} for the group. The eigenvalues of these graphs can be found using the representation theory of the group, and using tools from algebraic graph theory these eigenvalues can be used to bound the size of a coclique. In this talk I will show that this method can be used to show that large families of subgroups have the Erd\H{o}s-Ko-Rado property. Time permitting I will also give examples of groups that have a large intersection density, and are very far from having the Erd\H{o}s-Ko-Rado property. I will also give a general upper bound on the intersection density of a group and show some extremal examples.

Let $G = (V,E)$ be a graph on $n$ vertices and let $c : E \to \mathbb{N}$ be a coloring of the edges of $G$. The color degree $d^c(v)$ of a vertex $v \in V$ is the number of distinct colors that appear on the edges incident to $v$. We let $\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}$ be the minimum color degree of $G$. In 2013, H.\ Li proved that if $\delta^c(G) \ge (n+1)/2$, then $G$ contains a rainbow triangle and this is tight as witnessed by a properly edge-colored balanced bipartite graph. In this talk, we will explore generalizations and extensions of this result. In particular, for $\ell \ge 4$, we will discuss the minimum color degree threshold for the existence of a rainbow $\ell$-clique. This is joint work with Andrzej Czygrinow and Brendan Nagle.

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

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

Given a set $S$ of $n$ points in the plane and a parameter $\varepsilon)>0$, a Euclidean $(1+\varepsilon))$-spanner is a geometric graph $G=(S,E)$ that contains a path of weight at most $(1+\varepsilon))\|pq\|_2$ for all $p,q\in S$. We show that the minimum weight of a Euclidean $(1+\varepsilon))$-spanner for $n$ points in the unit square $[0,1]^2$ is $O(\varepsilon)^{-3/2}\,\sqrt{n})$, and this bound is the best possible. The upper bound is based on a new spanner algorithm that sparsifies Yao-graphs. It improves upon the baseline $O(\varepsilon)^{-2}\sqrt{n})$, obtained by combining a tight bound for the weight of an MST and a tight bound for the lightness of Euclidean $(1+\varepsilon))$-spanners, which is the ratio of the spanner weight to the weight of the MST. The result generalizes to $d$-space for all $d\in \N$: The minimum weight of a Euclidean $(1+\varepsilon))$-spanner for $n$ points in the unit cube $[0,1]^d$ is $O_d(\varepsilon)^{(1-d^2)/d}n^{(d-1)/d})$, and this bound is the best possible. For the $n\times n$ section of the integer lattice, we show that the minimum weight of a Euclidean $(1+\varepsilon))$-spanner is between $\Omega(\varepsilon)^{-3/4}n^2)$ and $O(\varepsilon)^{-1}\log(\varepsilon)^{-1})\, n^2)$. These bounds become $\Omega(\varepsilon)^{-3/4}\sqrt{n})$ and $O(\varepsilon)^{-1}\log (\varepsilon)^{-1})\sqrt{n})$ when scaled to a grid of $n$ points in $[0,1]^2$.

For the graph Turan problem, it follows from the well-known Erdos--Stone--Simonovits theorem that every extremal graph is close to a Turan graph in edit distance. We are interested in the structure of extremal constructions for hypergraph Turan problems, and we will talk about some results of this problem.

An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n-vertex graph is O(nlog n) and that there are n-vertex graphs whose obstacle number is Ω(n/(loglog n)^2). We improve this lower bound to Ω(n/loglog n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. Our bounds are asymptotically tight in several instances. This is a joint work with Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff.

Joint work with Daniel Di Benedetto and J´ozsef Solymosi. An interval is a line segment with positive finite length. We consider sets of intervals such that many pairs of intervals possess an interesting geometric property. Properties we will discuss include pairs forming trapezoids, orthodiagonal quadrilaterals, or cyclic quadrilaterals. We find necessary and sufficient conditions for pairs of intervals to have any one of these properties. The most general structure will be that the endpoints of many intervals lie on a conic (for trapezoids) or a bicircular quartic (cyclic quadrilaterals).

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

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.