CoSP Seminar

This summer I will be coordinating a CoSP Zoom seminar on topological combinatorics, replacing a conference on the same topic that was supposed to take place in Prague this summer 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. 

A Zoom invitation will be sent by email. Please write me ( if you wish to be added to the mailing list.


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

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)

7/30 - Pablo Soberon (Baruch College)

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.


More talks may be published soon.