Martin Loebl: Perfect matchings in double-torus grids

It is known that the number of the perfect matchings of each finite double-torus grid is a linear combination of 16 determinants. It is predicted by the Quantum field theory (Alvarez-Gaume, Vaffa) that exactly 6 of these determinants go to zero when the size of the grid grows. I will introduce the rich world around this claim.

Temperley bijection – koster nxn mřížky a párování 2n+1 x 2n+1 mřížky.

Zdenek Dvorak: Baker game and approximation algorithms on proper minor-closed classes

Inspired by the Splitter game for nowhere-dense classes and Baker’s approach to design of approximation algorithms, we propose a new game, show a strategy winning this game in a constant number of rounds on proper minor-closed classes of graphs (without using the structure theorem), and argue that the existence of such a strategy implies existence of polynomial-time approximation schemes for a number of optimization problems.

Martin Balko: Ramsey numbers and monotone colorings

For positive integers N and r >= 2, an r-monotone coloring of r-tuples from [N] is a 2-coloring by -1 and +1 that is monotone on the lexicographically ordered sequence of r-tuples of every (r+1)-tuple from [N]. Let ORS(n;r) be the minimum N such that every r-monotone coloring of r tuples from [N] contains n elements with all r-tuples of the same color.

For every r >= 3, it is known that ORS(n;r) is bounded from above by a tower function of height r-2 with O(n) on the top. The Erdős–Szekeres Lemma and the Erdős–Szekeres Theorem imply ORS(n;2)=(n-1)^2+1 and ORS(n;3) = ((2n-4) choose (n-2))+1, respectively. It follows from a result of Eliáš and Matoušek that ORS(n;4) grows as o tower of height 2.

We show that ORS(n;r) grows at least as a tower of height r-2 for every r >= 3. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ORS(n;r) and two Ramsey-type problems that have been recently considered by several researchers. We also prove asymptotically tight estimate on the number of r- monotone colorings of on [N].

Pierre Simon: Towards a classification of geometric homogeneous structures

We call a homogeneous structure geometric (or NIP) if it has polynomially many types over finite sets, or equivalently at most exponential growth of the number of finite substructures. Such structures are usually order-like or tree-like. I will present the first step in the classification of the order-like case. As an example, the classification of primitive homogeneous multi-orders, as well as of their reducts, follows at once from it. I will end with a few open problems.

Dusan Knop Integer Programming in Parameterized Complexity: Three Miniatures

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra’s algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools.

Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Sum Coloring by modeling it as a convex program in fixed dimension, n-fold integer programs, and as ILP with bounded dual treewidth and graver complexity.

Andreas E. Feldmann: The Parameterized Hardness of the k-Center Problem in Transportation Networks

Máme graf na kterém chceme rychle počítat k-center problem; ukazuje se, že obecně nelze zalézt pod 2-aproximaci, ovšem s přístupem parametrizovaném pomocí hubů se dostaneme na (1+eps)-aproximaci.

We study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph $G=(V,E)$ and an integer $k$ are given and a center set $C\subseteq V$ needs to be chosen such that $|C|\leq k$. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers $k$, the highway dimension $h$, and even the treewidth $t$. Moreover, under the Exponential Time Hypothesis there is no $f(k,t,h)\cdot n^{o(t+\sqrt{k+h})}$ time algorithm for any computable function $f$. Thus it is unlikely that the optimum solution to k-Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! (Joint work with Dániel Marx.)

Pavel Hubáček: On Constant-Round Statistical Zero-Knowledge

I will show how to overcome technical challenges when designing constant-round statistical zero-knowledge proofs. Specifically, I will describe an unconditional transformation from any honest-verifier statistical zero-knowledge protocol to a protocol where the statistical zero-knowledge property holds against arbitrary verifiers.

Zaniar Ghadernezhad: Amenable automorphism groups and convex Ramsey matrices

Něco s Fraisse class grafy.

Lluis Vena: Chromatic number of subgraphs of the kneser graph

José Aliste: Rooted U-polynomials

U polynom grafu je: vezmeme podmnožíny hran a spočteme velikosti komponent, x_4 je pro komponentu velikosti 4 atp., ty se pro jednu podmnožinu hran pronásobí a mezi různými podmnožinami hran se sečte. Tj pro S_3 máme x_4+3x_3x_1+3x_2x_1^2+x_1^4.

The U polynomial was introduced by Noble and Welsh in 1999 and it generalizes the chromatic symmetric function of Stanley. It is an open question whether there exist non-isomorphic trees with the same U-polynomial. In this talk, we truncate the U-polynomial and for each k, we find pairs of non-isomorphic trees with the same truncation of the U-polynomial. To construct these trees we introduce and study the rooted U-polynomial for rooted trees and prove several algebraic formulas that allow for simple computations of rooted polynomials, which can later be used to deduce properties of the non-rooted versions U-polynomials of the trees involved.

Dragan Mašulović: Finite big Ramsey degrees in universal structures

Pro strukturu můžeme definovat (small/big) Ramsey degree – něco ve smyslu, že se objevuje k-barevná podstruktura, kde k je konstranta.

Let F be a countable ultrahomogeneous relational structure. A positive integer n is a big Ramsey degree of a finite structure A in Age(F) if n is the least integer such that for every k > 1 and every coloring of copies of A in F with k colors there is a copy F’ of F sitting inside F such that at most n colors are used to color the copies of A that fall within F’. If such an integer exists we say that A has finite big Ramsey degree in F.

For example, Devlin proved in 1979 that finite chains have finite big Ramsey degrees in Q, Sauer proved in 2006 that finite graphs have finite big Ramsey degrees in the Rado graph, and Dobrinen has just recently proved that finite triangle-free graphs have finite big Ramsey degrees in the Henson graph H_3.

In this talk we consider the context where F is a countable structure universal for a class of finite structures, but not necessarily a Fraisse limit. For each of the following classes of structures: acyclic digraphs, finite permutations, a special class of finite posets with a linear order extending the poset relation, and a special class of metric spaces we show that there exists a countably infinite universal structure S such that every finite structure from the class has finite big Ramsey degree in S.