During summer 2020 I coordinated a CoSP Zoom seminar on topological combinatorics, replacing a conference on the same topic that was supposed to take place in Prague and was cancelled due to COVID-19:
The talks will be given on Tuesdays and Thursdays at 8:00am (CDT), as of June 30, 2020.
Click here to join the meetings. Please write me (zerbib@iastate.edu) if you wish to be added to the mailing list.
Schedule:
6/30 - Andreas Holmsen (KAIST)
Title: The Fractional Helly property and topological complexity
Abstract: The fractional Helly theorem is a simple yet remarkable generalization of Helly’s classical theorem on the intersection of convex sets, and it is of considerable interest to extend the fractional Helly theorem beyond the setting of convexity. In this talk I will discuss a recent result which shows that the fractional Helly theorem holds for families of subsets of R^d which satisfy only very weak topological assumptions. This is joint work with Xavier Goaoc and Zuzana Patáková.
7/2 - Florian Frick (Carnegie Mellon University)
Title: The topological Tverberg problem beyond prime powers
Abstract: Given d and q the topological Tverberg problem asks for the minimal n such that any continuous map from the n-dimensional simplex to R^d identifies q points from pairwise disjoint faces. For q a prime power n is (q-1)(d+1). The lower bound follows from a general position argument, the upper bound from equivariant topological methods. It was shown recently that for q with at least two distinct prime divisors the lower bound may be improved. For those q non-trivial upper bounds had been elusive. I will show that n is at most q(d+1)-1 for all q. I had previously conjectured this to be optimal unless q is a prime power. This is joint work with Pablo Soberón.
7/7 - Minki Kim (Technion)
Title: Complexes of graphs with bounded independence number
Abstract: Let G be a graph on V and n a positive integer. Let I_n(G) be the simplicial complex whose faces are the subsets of V that do not contain an independent set of size n in G. We study the collapsibility numbers of the complexes I_n(G) for various classes of graphs, focusing on the class of graphs with bounded maximum degree. As an application, we obtain the following result: Let G be a claw-free graph with maximum degree at most k. Then every collection of (k/2 +1)(n-1)+1 independent sets of size n in G has a rainbow independent set of size n. This is joint work with Alan Lew.
7/9 - Zilin Jiang (MIT)
Title: Rainbow odd cycles
Abstract: The classical colorful Carathéodory theorem says that for every family of d+1 point sets in R^d, if each point set contains 0 in its convex hull, then there is a rainbow set with the same property. Here, if we drop the critical cardinality of the family to d, generically, such a rainbow set does not exist. However we start to see that rainbow problems in more combinatorial settings present stability. For example, Drisko’s theorem on matchings in a bipartite graph still holds for 2n-2 matchings of size n unless their union is a cycle of length 2n. In this talk, I will illustrate a similar phenomenon for cycles with or without parity constraints on their lengths. Joint work with Ron Aharoni, Joseph Briggs and Ron Holzman.
7/14 - Gabor Simonyi (Renyi Institute)
Title: Color-critical edges in Schrijver graphs
Abstract: Schrijver graphs are vertex-color critical induced subgraphs of Kneser graphs. In general they are not edge-color-critical. We give necessary conditions and sufficient conditions for their individual edges to be color-critical. Our work started with investigating 4-chromatic Schrijver graphs more thoroughly and for those our results give a complete characterization of the color-critical edges. We also show that 4-chromatic Schrijver graphs contain spanning subgraphs that quadrangulate the Klein bottle and (apart from two cases of small parameters) these spanning subgraphs are edge-color-critical. (Analogous results for spanning subgraphs quadrangulating the projective plane follow from work by Kaiser-Stehlík and Gimbel-Thomassen.) The work presented in this talk is joint with Gábor Tardos.
7/16 - Jinha Kim (Technion)
Title: Domination numbers and noncover complexes of hypergraphs
Abstract: Let H be a hypergraph on a finite set V. A cover of H is a set of vertices that meets all edges of H. If W is not a cover of H, then W is said to be a noncover of H. The noncover complex of H is the abstract simplicial complex whose faces are the noncovers of H. In this talk, I will present about some homological properties of noncover complexes of hypergraphs. In particular, we obtain an upper bound on their Leray numbers in terms of domination numbers. This is joint work with Minki Kim.
7/21 - Tomas Kaiser (University of West Bohemia) & Matej Stehlik (Universite Grenoble Alpes) - double talk (45x2 minutes)
Title: Edge-critical subgraphs of Schrijver graphs
Abstract: We give a simple combinatorial description of an (n-2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of [J. Combin. Theory Ser. B 144 (2020) 191-196] to all values of k, and sharpens the classical results of Lovász and Schrijver from the 1970s.
7/23 - Amzi Jeffs (University of Washington)
Title: Open and closed convex codes and their embedding dimensions
Abstract: Given a collection of open convex sets in Euclidean space, one can write down a combinatorial code that records how the sets intersect and overlap one another. One can try to reverse this process: given a combinatorial code, can you find a collection of convex open sets that gives rise to it? The smallest dimension in which one can find this collection is called the open embedding dimension of the code. Analogously, the closed embedding dimension is the smallest dimension in which one can find a collection of closed convex sets giving rise to the code. We will use a new Helly-style theorem to show that these two numbers exhibit surprisingly different behavior. In particular, the gap between the two may be exponentially large compared to the number of convex sets.
7/28 - Martin Loebl (Charles University)
Title: Some aspects of winter road maintenance
Abstract: I will describe some combinatorial and algorithmic features of a model of winter road maintenance, including a relation to necklace splitting. (joint work with Jirka Fink, Petra Pelikanova)
7/30 - Pablo Soberon (Baruch College)
Title: Variations of equipartitions of measures with convex sets
Abstract: Given d measures in R^d and an integer k, there exists a partition of R^d into k convex pieces of the same size in each measure. During this talk we will talk about two extensions of this result. In the first one we are given more than d measures, and would still like each piece to be large for sufficiently many measures. In the second one, we are given sets of lines in R^2 instead of sets of points, and we show similar equipartition results. The first part is joint work with Blagojevic, Palic, and Ziegler, the second part is joint work with Xue.
8/4 - Joe Briggs (Technion)
Title: Making Rainbow Matchings Together
Abstract: Aharoni-Berger-Chudnovsky-Howard-Seymour proved 3n-2 matchings of size n span a rainbow matching of size n. Remarkably, Holmsen-Lee showed topologically that it suffices to take any 3n-2 edge sets each of whose pairwise unions contain a matching of size n. We reprove their cooperative version using a purely combinatorial method, and offer a corresponding result for bipartite graphs. In this talk I will give an overview of these proofs while showing we still have more questions than answers. This is based on joint works with Ron Aharoni, Minho Cho, Jinha Kim, and Minki Kim.
9/17 - Denys Bulavka (Charles University)
Title: Optimal bounds for the colorful fractional Helly theorem
Abstract: The well known fractional Helly theorem and colorful Helly theorem can be merged into so called colorful fractional Helly theorem. It states: For every alpha in (0, 1] and every non-negative integer d, there is beta = beta(alpha, d) in (0, 1] with the following property. Let F_1, ..., F_{d+1} be finite nonempty families of convex sets in R^d of sizes n_1, ..., n_{d+1} respectively. If at least alpha n_1 n_2 ... n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i in [d+1] such that F_i contains a subfamily of size at least b n_i. (A colorful (d+1)-tuple is a (d+1)-tuple (C_1,...,C_{d+1}) such that C_i belongs to F_i for every i.)
The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with beta = alpha/(d+1).
In 2017 Kim proved the theorem with better function beta, which in particular tends to 1 when alpha tends to 1. Kim also conjectured what is the optimal bound for beta(alpha, d) and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984.
We prove Kim's conjecture by extending Kalai's approach to the colorful scenario. Moreover, we obtain bounds for other collections of sets, not just colorful (d+1)-tuples.
This is a joint work with Afshin Goodarzi and Martin Tancer.
More talks may be published soon.