Joint DIMEA and FORMELA seminar

Guillermo Alberto Perez (University of Antwerp): The impatient may use limited optimism to minimize regret

Thursday 3 October, 14:00, room C417

Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the agent interacts with the environment, she may realize that, with hindsight, she could have increased her reward by playing differently: this difference in outcomes constitutes her regret value. The agent may thus elect to follow a regret-minimal strategy. In this paper, it is shown that (1) there always exist regret-minimal strategies that are admissible—a strategy being inadmissible if there is another strategy that always performs better; (2) computing the minimum possible regret or checking that a strategy is regret-minimal can be done in coNP and NP, disregarding the computational cost of numerical analysis (otherwise, this bound becomes PSPACE).

Tomáš Kaiser (UWB Pilsen): Small triangulations of projective spaces

Monday 7 October, 14:00, room C417

A triangulation of the real projective space RP^d of dimension d can be obtained by taking a barycentric subdivision of the boundary of the (d+1)-dimensional simplex and identifying antipodal points. This triangulation has exponentially many vertices in d. On the other hand, Arnoux and Marin proved in 1991 that the number of vertices of a triangulation of RP^d must be greater than d+2 choose 2. Since then, it is an open problem whether there exist such triangulations with polynomially many vertices in d. We will discuss our recent work related to this question (joint with Matej Stehlik).

Tom Kelly (University of Birmingham): On the density of critical graphs without large cliques

Monday 21 October, 14:00, room C417

A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to a possible generalization of Reed's Conjecture. Joint work with Luke Postle.

Péter Pál Pach (Budapest University of Technology and Economics): Polynomial Schur's theorem

Monday 4 November, 14:00, room C417

We consider the Ramsey problem for the equation x+y=p(z), where p is a polynomial with integer coefficients. Under the assumption that p(1)p(2) is even we show that for any 2-colouring of the positive integers the equation x+y=p(z) has infinitely many monochromatic solutions. Indeed, we show that the number of monochromatic solutions with x,y,z in {1,2,...,n} is at least n^{2/d^3-o(1)}, where d=deg(p).

On the other hand, when p(1)p(2) is odd, that is, when p attains only odd values, then there might not be any monochromatic solution, e.g., this is the case when we colour the integers according to their parity. We give a characterization of all 2-colourings avoiding monochromatic solutions to x+y=p(z).

This is a joint work with Hong Liu and Csaba Sándor.

Michał Dębski (Masaryk University): Centered colorings of bounded degree graphs

Monday 11 November, 14:00, room C417

A vertex coloring c of a graph G is p-centered if for every connected subgraph H of G there is a color that appears exactly once on H, or c uses more than p colors on H. This is related to other graph sparsity notions, i.e. a class of graphs has bounded expansion if and only if there is function f such that every graph from the class admits a p-centered coloring using at most f(p) colors.

I will show that graphs of bounded maximum degree admit a p-centered coloring using O(p) colors - this disproves a conjecture of Pilipczuk and Siebertz. The proof uses the entropy compression method.

The talk will be based on a joint paper with Stefan Felsner, Piotr Micek and Felix Schröder: https://arxiv.org/abs/1907.04586

Robert Hancock (Masaryk University): Limits of sequences of Latin squares

Monday 18 November, 14:00, room C417

We introduce a limit theory of Latin squares, paralleling the recent limit theories of dense graphs and permutations. The space of limit objects - so-called Latinons, are certain distribution-valued two variable functions. Left-convergence to these are defined via densities of k by k subpatterns. The main result is a compactness theorem stating that every sequence of Latin squares of growing orders has a Latinon as an accumulation point. Furthermore, we show (via Keevash's recent results on combinatorial designs) that the space of Latinons is minimal, that is every Latinon can be approximated by Latin squares. We also introduce an appropriate version of cut-distance and prove counterparts to the counting lemma, sampling lemma and inverse counting lemma. This is joint work with Frederik Garbe, Jan Hladký and Maryam Sharifzadeh.

Martin Koutecký (Charles University Prague): Presburger meets Cambridge Analytica

Monday 2 December, 14:00, room C417

Cambridge Analytica is an infamous and now bankrupt (but sure to survive in some other way) company which helped manipulate elections all over the world (including the Brexit and Trump campaigns) through targeted advertising on social networks. We want to analyze such tasks and events from the perspective of computational complexity, asking questions such as: what is the cheapest bribery which makes my candidate win? What if opinion diffusion happens in the underlying social network? What if manipulation happens simultaneously by multiple agents? Answering these questions is helpful not only to a potential briber, but also to observers wishing to detect bribery or have meaningful measures of the (surprisingly elusive) notion of margin of victory.

Presburger arithmetic (PrA) is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger who introduced it in 1929 and proved its decideability. While the questions posed above are hard in general, we show that when the number of voter types is small (typically when the number of candidates is small), the problems can be formulated as model checking of short PrA sentences, and already Presburger's proof gives a fixed-parameter tractable algorithm. In this talk, I will present Cooper's algorithm from the 1970's which is faster than Presburger's original procedure. Still, many interesting questions remain open.

Yanitsa Pehova (University of Warwick): Tight packings of Hamiton cycles in bipartite digraphs

Monday 16 December, 14:00, room C417

In 1981 Jackson showed that the diregular bipartite tournament (a complete bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree) contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: For every c > 1/2 and ε > 0 there exists n₀ such that every cn-regular bipartite digraph on 2n ≥ n₀ vertices contains (1-ε)cn edge-disjoint Hamilton cycles. This is joint work with Anita Liebenau (UNSW).