Dear all,
I am forwarding Martin Loebl's invitation to the UNFINISHED workshop happening next week at Malá Strana, please see below.
Furthermore, there will be a noon lecture next Thursday, 9 Nov; I will send out an announcement on Monday. This week, as I wrote, there is no noon lecture.
Best regards, MT
CoSP Workshop UNFINISHEDm November 6-8, MFF UK Malostranské nám 25 Prague 1 Czechia
CoSP is the H2020-MSCA-RISE project number 823748 funded by the European Union. This workshop aims at highlighting extensively studied but still open conjectures falling into the project's domain.
Programme: each day 4PM- 6PM two lectures, one remote and one presently in Malá Strana, mornings devoted to discussions with the invited speakers
Monday Nov 6 S1 (discrete math) Sophie Spirkl (zoom talk) and Nicolas Trotignon Tuesday Nov 7 S1 (physics and geometry) Marta Pavelka (zoom talk) and Bergfinnur Durhuis Wednesday Nov 8 S7 (theoretical computer science) Michal Koucky (zoom talk) and Ron Holzman
Zoom meeting (please do not post in web)
Join Zoom Meeting https://cesnet.zoom.us/j/99700372845?pwd=a0pSaWlIVUd3UzhtSHg3TVJaNlZYZz09
Meeting ID: 997 0037 2845 Passcode: 034058
Abstracts:
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.
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 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.
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.
Bergfinnur Durhuis, 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.
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.
Ron Holzman, Technion Israel: Fair Division via Quantile Shares
Joint work with Yakov Babichenko, Michal Feldman and Vishnu V. Narayan. 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. Specifically, we show that if the rainbow version of the Erdos Matching Conjecture is true, then the 1/(2e)-quantile share is feasible with respect to all monotone valuations, and this result is tight up to a factor of 2; that is, the q-quantile share is infeasible for q > 1/e. In addition, we provide unconditional feasibility results for special cases. Specifically, we show that every profile of additive (respectively, unit-demand or matroid-rank) valuations admits a q-quantile fair allocation for q = 0.14/e (respectively, for q = 1/e).