July 22--July 26 in Prague
organised by Ron Aharoni and Martin Loebl
in the School of Informatics, Malostranske nam 25, Prague 1, Czech Republic.
During the workshop the 1st Management Committee Meeting of CoSP takes place.
The school on topological methods is a part of this workshop. It takes place on Tuesday July 23 featuring the presentations:
Ron Aharoni: The colorful world of rainbow sets
A two hour talk, that combines an introduction to topological methods in combinatorics with applications to rainbow sets (synonymous with “choice functions”).
Penny Haxell: Topological Connectedness and Independent Sets in Graphs
We describe a link between the topological connectedness of the independence complex of a graph and various other important graph parameters to do with colouring and partitioning. When the graph represents some other combinatorial structure, for example when it is the line graph of a hypergraph H, this link can be exploited to obtain information such as lower bounds on the matching number of H. Since its discovery there have been various applications of this phenomenon to other combinatorial problems. We also outline some of these applications.
INVITED SPEAKERS AND THEIR PRESENTATIONS:
Meysam Alishahi: The chromatic number of random Kneser hypergraphs
Kupavskii (2016) investigated the chromatic number of random Kneser graphs KGn,k(ρ) and proved that, in many cases, the chromatic number of the random Kneser graph KGn,k(ρ) and the Kneser graph KGn,k are almost surely closed and marked the studying of the chromatic number of random Kneser hypergraphs KGrn,k(ρ) as an interesting problem. With the help ofZp-Tucker lemma, a combinatorial generalization of the Borsuk-Ulam theorem, we generalize Kupavskii’s result to random general Kneser hypergraphs by introducing an almost surely lower bound for the chromatic number of them. Joint work with Hossein Hajiabolhassan
Joseph Briggs: Rainbows in Fractional Matroid Polytopes
Theorem, in a more general setting, can be stated as follows. Any 2n − 1 different-coloured matchings of size n in a bipartite graph contain a rainbow matching of size n, that is, n edges with distinct colours. Other results on matroid polytopes are given. This is joint work with Minki Kim.
Kai Fong Ernest Chong: Flag complexes and homology
Let ∆ be a (d − 1)-dimensional flag complex (e.g. the independence complex of a graph with independence number d). If we know the value of the (d − 1)-th reduced Betti number of ∆ over Q, then what can we say about the number of k-dimensional faces of ∆, in terms of a, for all k ≥ 0? This is joint work with Eran Nevo.
Andereas Holmsen: Problems surrounding Fractonial Helly
The Fractional Helly theorem due to Katchalski and Liu is an important generalization of Helly’s theorem which plays a crucial role in the celebrated proof of Alon and Kleitman’s (p, q) theorem. About a decade ago, Kalai and Meshulam formulated several problems and conjec- tures concerning Fractional Helly Properties which are also related to Gy ́arf ́as-type problems in structural graph and hypergraph theory. In this talk I will survey some recent progress in this area, in particular fractional Helly theorems in abstract convexity spaces and in certain topological settings.
Tomas Kaiser, Matej Stehlik: Colouring projective quadrangulations
These are two back-to-back talks. We shall review the definitions and main results related to the notion of quadrangulation of a projective space. We will start with the result of Youngs that every nonbipartite quadrangulation of the projective plane is 4-chromatic, and generalise it to higher dimensions. We will then show that the Mycielski graphs can be realised as projective quadrangulations in the appropriate dimension, and obtain the Lov ́asz–Kneser theorem as a corollary. Focusing on Schrijver graphs, we will outline a construction showing that SG(n,k) contains a spanning subgraph that is a quadrangulation of the projective space of dimension n − 2k. We will conclude with a discussion of the close relation between the coindex of the box complex of a graph G and homomorphisms from projective quadrangulations to G.
Jinha Kim: Collapsibility of non-cover complex of graphs
Given a graph G, the non-cover complex of G is the combinatorial Alexander dual of the independence complex of G. Aharoni asked if the non-cover complex of a graph G is (|V (G)| −iγ(G)−1)-collapsible where iγ(G) denotes the independent domination number of G. We prove that the answer to the question is yes for all graphs. This is joint work with Ilkyoo Choi and Boram Park.
Minki Kim: Rainbow independent sets in graphs
Given a graph class G, let fG(n) be the minimum positive integer k such that for every graph G' ∈ G, any collection of k independent sets of size n has a rainbow independent set of size n. In this talk, I will present some results on fG(n) for certain graph classes. Based on joint work with Ron Aharoni, Joseph Briggs, and Jinha Kim, and on work with Alan Lew.
Alan Lew: Collapsibility of simplicial complexes of hypergraphs
Let X be a simplicial complex. Given a simplex σ ∈ X of dimension at most d − 1 that is contained in a unique maximal face of X, the operation of removing σ and all the simplices that contain it from X is called an elementary d-collapse. We say that X is d-collapsible if it can be reduced to the void complex by performing a sequence of elementary d-collapses. The collapsibility of X is the minimal d such that X is d-collapsible. We present tight upper bounds on the collapsibility of different simplicial complexes associated to an r-uniform hypergraph H.
Seunghun Lee: Leray property of the complex of graphs with no matchings of size k
Let NM_k(H) be the complex consisting of subgraphs of H with matching number less than k. We show that NMk(H) is near-(3k − 4)-Leray. As a corollary, via Holmsen’s topological generalization of the colorful Caratheodory theorem, we show that there exists a rainbow matching of size k for given edge sets E1, . . . , E(3k−2), when the condition ν(Ei ∪ Ej) ≥ k is satisfied for every I different from j. The proof follows and extends the previous argument by Linusson, Shareshian, and Welker, and depends on the discrete Morse theory and the Gallai-Edmonds decomposition.Joint work with Andreas Holmsen.
Frederic Meunier: A mutilabeled version of Fan’s lemma
Ky Fan’s lemma is a classical result of combinatorial topology that has several applications in combinatorics and which provides an elementary constructive proof of the Borsuk-Ulam theorem. Given a symmetric triangulation of a sphere and an antisymmetric labeling of its vertices with integers, this lemma guarantees the existence of a simplex with a special pattern. This talk aims at introducing a multilabeled version of Ky Fan’s lemma, which does not involve a single labeling, but a whole collection of labelings. Applications in graph theory, combinatorial topology, and fair division will be presented. Joint work with Francis E. Su.
Zuzana Patakova: Bounding Radon’s number via Betti numbers
Radon’s theorem is one of the cornerstones of convex geometry. It implies many of the key results in the area such as Helly’s theorem and, as recently shown by Andreas Holmsen and Dong-Gyu Lee, also its more robust version, fractional Helly’s theorem together with a colorful strengthening of Helly’s theorem. Consequently, this yields an existence of weak epsilon nets and a (p, q)-theorem. We show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. Moreover, using a recent result of the speaker and Gil Kalai, we manage to bring the fractional Helly number for open sets in the plane or on a surface down to three. This also settles a conjecture of Andreas Holmsen, Minki Kim, and Seunghun Lee about an existence of a (p, q)-theorem for open subsets of a surface.
Yuval Peled: On the threshold for simple connectivity in random 2-complexes
Let Y = Y2(n, p) be a random 2-dimensional simplicial complex in which each 2-face is chosen independently with probability p = p(n). Babson, Hoffman and Kahle proved that, with high probability, Y is not simply connected provided that p ≪ n^(−1/2). We show that Y is simply connected with high probability if p > (cn)^(−1/2( where the constant c = 44/33, and conjecture that this bound is sharp. In fact, we prove that (cn)^(−1/2) is a sharp threshold for the stronger property that every cycle of length 3 is the boundary of a triangulated disk that is contained in Y . The proof uses a classical result of Tutte on the enumeration of planar triangulations. Joint work with Zur Luria.
Gabor Simonyi: Shannon capacity and the categorical product
The categorical product F ×G of two graphs F and G is the graph on vertex set V(F)×V(G) in which vertices (f,g) and (f′,g′) are adjacent if and only if both ff′ and gg′ form edges in F and G, respectively. Since F × G admits a graph homomorphism into both F and G, any homomorphism monotone (increasing) graph invariant p, i.e., one for which the existence of a homomorphism from graph G to graph H implies p(G) ≤ p(H), satisfies p(F × G) ≤min{p(F),p(G)} and one can ask whether equality holds. The most famous question of that type is Hedetniemi’s conjecture from 1966 that stated equality for the chromatic number and has been refuted very recently by Shitov. Equality trivially holds for the clique number, but there are rather non-trivial examples, too. For example, we always have equality for the fractional chromatic number by a celebrated result of Zhu and also for the Lov ́asz theta number of the complementary graph by a more recent result by Godsil, Roberson, Sˇamal, and Severini. In the talk we elaborate on the possibility of such an equality to hold for another homomorphism monotone graph parameter, the Shannon OR-capacity (which is just the more usual Shannon (AND)-capacity of the complementary graph).
Martin Tancer: Even maps, the Colin de Verdi`ere number and representations of graphs
Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdiere graph parameter μ for small values. However, the definition of σ is much more geometric/topological, directly reflecting embeddability properties of the graph. They proved that μ(G) ≤ σ(G) + 2 and conjectured that μ(G) ≤ sigma(G) for any graph G. In the talk we sketch the main steps for a proof of this conjecture. As far as we know, this is the first topological upper bound on μ(G) which is, in general, tight. Based on a joint work with Vojtech Kaluza.
Gabor Tardos: Controlling Lipschitz functions
How sparsely can you place points in the plane such that they get arbitrary close to every line? This particular problem of L ́aszlo Fejes Toth was solved some 40 years ago by Erd ̋os and Pach. We ask a similar question with the graphs of Lipschitz functions in place of lines. Given a sequence of points xi ∈ R^m, can one find a sequence of points yi ∈ R^d such that no graph of a Lipschitz function from R^m to R^d has positive distance from the collection of points (xi,yi)? The following simple criterion is necessary and for m = 1 also sufficient: |{i | |xi| < n}|/n^d is unbounded. The sufficiency is conjectured for all m ≤ d, but we could only establish a slightly weaker sufficiency result based on Brouwer’s fixed point theorem. Joint work with Andrey Kupavskii and Janos Pach.
Shira Zerbib: Tuza’s conjecture - a generalization and the random case
A famous conjecture of Tuza is that the minimal number of edges needed to cover all triangles in a graph is at most twice the maximal size of a set of edge-disjoint triangles. We show that Tuza’s conjecture holds in the random graph G = G(n, m), when m ≤ 0.24n3/2 or m ≥ 2.13n3/2. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs. We also propose a wider setting for Tuza’s conjecture for k-uniform hypergraphs, and show that most known bounds in Tuza’s conjecture carry over to this general setting. Finally, we consider the fractional and k-partite version of our conjecture. Joint works with Ron Aharoni, Patrick Bennett, and Andrzej Dudek.
Zilin Jiang: Colored B ́ar ́anys Theorem
In this talk, we are concerned with a colored variant of the point selection problem. Let P0,...,Pd be d + 1 disjoint finite sets in R^d. A colorful simplex is the convex hull of d + 1 points each of which comes from a distinct Pi. For the colored point selection problem, we are concerned with the point(s) contained in many colorful simplices. We discuss Karasev’s topological proof for the colored variant and our slight improvement on the bound.
You can download the poster:
Posted on 2019-03-22