CoSP Annual Workshop with the title UNFINISHED will take place November 6-8 2023 in Prague. This workshop aims at highlighting extensively studied but still open conjectures falling into the project's domain.
Here is the poster CoSP workshop 2023 final.pdf
Place: MFF UK Malostranské nám 25, Prague 1, Czechia
Programme: each day 4PM- 6PM, mornings devoted to discussions with the invited speakers
Monday Nov 6, 4th floor, room S1 (discrete mathematics): Sophie Spirkl (zoom talk) and Nicolas Trotignon
Tuesday Nov 7, 4th floor, room S1 (physics and geometry): Marta Pavelka (zoom talk) and Bergfinnur Durhuus
Wednesday Nov 8, 2nd floor, room S7 (theoretical computer science): Michal Koucky (zoom talk) and Ron Holzman
Abstracts:
1. Sophie Spirkl, U. Waterloo, Canada: 2-colouring tournaments
Colouring a tournament means partitioning its vertex set into transitive subsets. Unlike for graphs, even 2-colouring is NP-complete for tournaments. In the graph setting, much progress has been made on determining the complexity of 3-colouring graphs with a forbidden induced subgraph. In the tournament setting, we don't even have a sensible conjecture for which tournaments make 2-colouring easy when excluded.
Jointly left unfinished with Alvaro Carbonero, Sepehr Hajebi and Yanjia Li.
2. Nicolas Trotignon, CNRS, LIP, ENS de Lyon, France: Is there a minimal non-chi-bounded hereditary class?
The "unfinished question" proposed for the workshop is all in the title, except maybe for some needed definitions that are given now, followed by some motivation.
A class of graphs is hereditary if it's closed under taking induced subgraphs. A hereditary class of graph is chi-bounded if there exists a function f such that all graphs in the class satisfy chi(G) <= f(omega(G)). Therefore, a hereditary class C is non-chi-bounded if there exists an integer k such that for all integer l, there exists a graph G in C satisfying omega(G) = k and chi(G) >= l. A non-chi-bounded hereditary class C is minimal if all its proper hereditary subclasses are chi-bounded. Equivalently, C is minimal if for all H in C, the class of H-free graphs from C is chi-bounded (a graph is H-free if it does not contain H as an induced subgraph).
Seemingly, no minimal hereditary non-chi-bounded class is known. It might be that none exists, and proving this would yield a beautiful and general theorem. While it would be interesting for some that some minimal non-chi-bounded class exists, because each such class would be a kind of best-possible source of counter-examples to conjectures stating that a class is chi-bounded.
The talk will present a recent work by Édouard Bonnet, Romain Bourneuf, Julien Duron, Stéphan Thomassé and the speaker, showing that the classical Zykov's construction of triangle-free graphs of high chromatic number is far from being minimal. It contains graphs of high chromatic number with several structural restrictions: low connectivity or presence of twins, and high odd girth.
3. Marta Pavelka, Cornegie Mellon University U.S.A.: On triangulations of 3-spheres
The question ``How many triangulations of the 3-sphere with a given number of tetrahedra are there?'' has been around for a while. It was proposed by Bergfinnur Durhuus and Thordur Jonsson in 1995 in the context of the quantum gravity model and its convergence. Five years later, Mikhael Gromov listed it as one of the fundamental questions of topology. More specifically, it remains an open problem whether there are exponentially many of these triangulations in terms of the number of facets or if there are more. In this talk, we will see the current progress and directions researchers are taking to tackle this question. Moreover, we will look at classes of 3-spheres (or even d-spheres) that are proven to have an exponential size, including the 2-locally constructible spheres.
4. Bergfinnur Durhuus, Copenhagen University, Danemark: Combinatorial Questions in Quantum Gravity
In attempts to formulate a regularized model of quantum gravity one encounters interesting combinatorial problems related to counting certain geometric objects, like combinatorial manifolds, subject to certain (topological) constraints. This lecture will serve to formulate some such questions and to present a few details on their background as well as to discuss some partial results.
5. Michal Koucky, IUUK MFF UK Prague Czech Republic: Locally consistent decomposition of strings with applications to edit distance sketching
In this talk I will present a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness and ignoring poly-log factors). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ.
This decomposition has applications to edit distance sketching and streaming approximate pattern matching algorithms.
Joint work with Sudatta Bhattacharya.
6. Ron Holzman, Technion Israel: Fair Division via Quantile Shares
We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with valuations over bundles of goods. To capture fairness, we adopt the notion of shares, by which every agent has a fair share, according to some definition, and an allocation is considered fair if the value of every agent for her bundle (weakly) exceeds her fair share. We introduce a new notion of shares in which an agent deems a bundle fair or unfair based on how it compares to her value in a uniform allocation of the goods. Specifically, for every q in [0,1], a bundle is q-quantile fair if the probability of getting a (weakly) worse bundle in a uniform allocation is at least q. The question that drives us in this work is the feasibility of q-quantile shares. Namely, for what values of q, every profile of (monotone) valuations admits a q-quantile fair allocation.
Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdos Matching Conjecture.
This is joint work with Yakov Babichenko, Michal Feldman and Vishnu V. Narayan.
Posted on 2023-10-11