We celebrated by the workshop the 70th birthday of our teacher Jarik Nesetril. It took place at Patejdlova hut (over Špindlerův Mlýn, 972 meters above see level) on April 13 - 16, 2016. I think I was not alone to recollect and relive during this workshop the spirit of combinatorial seminars and spring and other schools organized by Jarik for so many generations of us, his students. Jarik determined the programme "on the spot" himself. We listened to truly amazing talks.

Martin Loebl

Thursday, April 14, 2016 - morning

Hans Raj Tiwary

TBA

Jan Kynčl The hamburger theorem

We generalize the ham sandwich
theorem to $d+1$ measures on $\mathbb{R}^d$ as follows.
Let
$\mu_1, \mu_2, \dots, \mu_{d+1}$ be absolutely continuous finite Borel
measures on $\mathbb{R}^d$. Let $\omega_i=\mu_i(\mathbb{R}^d)$ for
$i\in [d+1]$, $\omega=\min\{\omega_i; i\in [d+1]\}$ and assume that
$\sum_{j=1}^{d+1} \omega_j=1$.
Assume that $\omega_i \le
1/d$
for every $i\in[d+1]$ (that is, the measures are
\emph{balanced} in $\mathbb{R}^d$).
Then there exists a
hyperplane $h$

such that each open halfspace $H$ defined by $h$ satisfies $\mu_i(H) \le (\sum_{j=1}^{d+1} \mu_j(H))/d$ for every $i \in [d+1]$ and $\sum_{j=1}^{d+1} \mu_j(H) \ge \min\{1/2, 1-d\omega\} \ge 1/(d+1)$. As a consequence we obtain that every $(d+1)$-colored set of $nd$ points in $\mathbb{R}^d$ such that no color is used for more than $n$ points can be partitioned into $n$ disjoint rainbow $(d-1)$-dimensional simplices.

Further straightforward generalization of the ham sandwich theorem to $d+2$ measures in $\mathbb{R}^d$ is not possible for $d \ge 4$. We conjecture that for $d+i$ measures balanced in $\mathbb{R}^d$, where $1\le i \le d-1$, a nontrivial balanced partition into at most $i+1$ convex parts exists. A discrete version of this conjecture would imply a conjecture by Kano and Suzuki that every $(d+i)$-colored set of $nd$ points in $\mathbb{R}^d$ such that no color is used for more than $n$ points can be partitioned into $n$ disjoint rainbow $(d-1)$-dimensional simplices.

such that each open halfspace $H$ defined by $h$ satisfies $\mu_i(H) \le (\sum_{j=1}^{d+1} \mu_j(H))/d$ for every $i \in [d+1]$ and $\sum_{j=1}^{d+1} \mu_j(H) \ge \min\{1/2, 1-d\omega\} \ge 1/(d+1)$. As a consequence we obtain that every $(d+1)$-colored set of $nd$ points in $\mathbb{R}^d$ such that no color is used for more than $n$ points can be partitioned into $n$ disjoint rainbow $(d-1)$-dimensional simplices.

Further straightforward generalization of the ham sandwich theorem to $d+2$ measures in $\mathbb{R}^d$ is not possible for $d \ge 4$. We conjecture that for $d+i$ measures balanced in $\mathbb{R}^d$, where $1\le i \le d-1$, a nontrivial balanced partition into at most $i+1$ convex parts exists. A discrete version of this conjecture would imply a conjecture by Kano and Suzuki that every $(d+i)$-colored set of $nd$ points in $\mathbb{R}^d$ such that no color is used for more than $n$ points can be partitioned into $n$ disjoint rainbow $(d-1)$-dimensional simplices.

Martin Tancer Shortest path embeddings of graphs on surfaces

(joint work with Alfredo Hubard, Vojtěch Kaluža a Arnaud de Mesmay)

The classical theorem of Fáry states
that every planar graph can be represented by an embedding in which
every edge is represented by a straight line segment. We considered
generalizations of Fáry's theorem to surfaces equipped with Riemannian
metrics. In this setting, we require that every edge is drawn as a
shortest path between its two endpoints and we call an embedding with
this property a shortest path embedding. The main question addressed is
whether given a closed surface S, there exists a Riemannian metric for
which every topologically embeddable graph admits a shortest path
embedding. This question is also motivated by various problems
regarding crossing numbers on surfaces.

During the presentation, we have mentioned that surfaces of small genus, that is, the sphere, the projective plane, the torus and the Klein bottle admit such metrics (with constant curvature). On the other hand, for surfaces of large genus, a "typical" hyperbolic metric does not have such a property.

During the presentation, we have mentioned that surfaces of small genus, that is, the sphere, the projective plane, the torus and the Klein bottle admit such metrics (with constant curvature). On the other hand, for surfaces of large genus, a "typical" hyperbolic metric does not have such a property.

Thursday, April 14, 2016 - afternoon

Michal Koucký

TBA

Jiří Fiala Cantor-Bernstein type theorem for locally constrained graph homomorphisms

In my presentation I have reviewed a
result that we have obtained with Jana Maxová that asserts the
following: If two finite graphs allow a locally injective as well as a
locally surjective homomorphisms between them, then both homomorphisms
are indeed locally bijective.

A brief summary of results stemming from this fact has also been provided.

Jiří Fiala, Jana Maxová: Cantor-Bernstein type theorem for locally constrained graph homomorphisms. Eur. J. Comb. 27(7): 1111-1116 (2006)

A brief summary of results stemming from this fact has also been provided.

Jiří Fiala, Jana Maxová: Cantor-Bernstein type theorem for locally constrained graph homomorphisms. Eur. J. Comb. 27(7): 1111-1116 (2006)

Pavel Valtr A SAT attack on the Erdős–Szekeres Conjecture

(joint work with Martin Balko)

A classical conjecture of Erdős and
Szekeres states that every set of 2^{k-2}+1 points in the plane in
general position contains k points in convex position. In 2006, Peters
and Szekeres introduced the following stronger conjecture: every
red-blue coloring of the edges of the ordered complete 3-uniform
hypergraph on 2^{k-2}+1 vertices contains an ordered k-vertex
hypergraph consisting of a red and a blue monotone path which are
vertex disjoint except for the common end-vertices.

Applying the state of art SAT solver, we refute the conjecture of Peters and Szekeres. We also apply techniques of Erdős, Tuza, and Valtr to refine the Erdős–Szekeres conjecture in order to tackle it with SAT solvers.

In our experiments we used the Glucose SAT solver.

Applying the state of art SAT solver, we refute the conjecture of Peters and Szekeres. We also apply techniques of Erdős, Tuza, and Valtr to refine the Erdős–Szekeres conjecture in order to tackle it with SAT solvers.

In our experiments we used the Glucose SAT solver.

Jan Hubička

TBA

Friday, April 15, 2016 - morning

Jiří Sgall New developments in Travelling salesman problem

We survey history and some recent
results on Travelling salesman problem (TSP), focusing on approximation
algorithms for the metric version of the problem. We point out that
some of the recent results have a strong graph-theoretic flavor, as the
recent progress on the TSP with the shortest path metric. Of particular
interest is the Asymmetric version of TSP, where the best approximation
factor is still close to log(n), but it is conjectured that there
exists an O(1)-approximation.

Petr Hliněný

TBA

Jan Kratochvíl

TBA

Friday, April 15, 2016 - afternoon

Jakub Gajarský A New Perspective on FO Model Checking of Dense Graph Classes

(based on joint work with P. Hliněný, D. Lokshtanov, J. Obdržálek and M. S. Ramanujan)

Abstract: We consider the
FO model checking problem of dense graph classes, namely those which
are FO-interpretable in some sparse graph classes. If an input dense
graph is given together with the corresponding FO interpretation in a
sparse graph, one can easily solve the model checking problem using the
existing algorithms for sparse graph classes. However, if the assumed
interpretation is not given, then the situation is markedly harder.

We give a structural
characterization of graph classes which are FO-interpretable in graph
classes of bounded degree. This characterization allows us to
efficiently compute such an interpretation for an input graph. As a
consequence, we obtain an FPT algorithm for FO model checking of graph
classes FO interpretable in graph classes of bounded degree. The
approach we use to obtain these results may also be of independent
interest.

Martin Klazar The Skolem-Mahler-Lech theorem

This theorem, proved in
complete generality by Lech in 1953, characterizes the zero set Z(f) =
{n | f(n) = 0} of a linear recurrence sequence f(n) = a_1f(n-1) + ... +
a_kf(n-k) with values in a field K of characteristic 0 (a_i are constants in K)
- Z(f) is a union of a finite set and finitely many infinite arithmetic
progressions. In my short talk I explained the theorem, mentioned
Lech's counterexample to it in positive characteristic p (f(n) = (x +
1)^n - x^n - 1 is a LRS of order 3 in the field F_p(x) and it vanishes
exactly at the powers Z(f) = {1, p, p^2, ...} of the prime p), and I
stated some open problems in this area, namely the Skolem problem (it
is not known if the problem "f is an integral LRS, is Z(f) empty?" is
algorithmicly decidable) and possible extension of the SML theorem to
holonomic sequences (where the coefficients a_i = a_i(n) in the
recurrence are not constant any more and are rational functions in n).

Vít Jelínek The Beer index and the convexity ratio

The Beer index and the
convexity ratio of a planar set A are two measures that quantify how
close A is to being convex. The convexity ratio c(A) is defined as the
supremum of m(K)/m(A) over all convex subsets K of A, where m(.) is the
Lebesgue measure. The Beer index b(A) is the probability that two
points x and y chosen independently randomly in A "see each other",
i.e., the segment xy is contained in A. More generally, the k-Beer
index b_k(A) is the probability that for a (k+1)-tuple x_1,...,x_{k+1}
of points chosen independently randomly in A, their convex hull is
contained in A.

The main problem is to find lower bounds on c(A) in terms of the indices b_k(A). Several such results were recently proven in my joint work with Balko, Valtr and Walczak. Specifically, we have shown that there is a constant q>0 such that any simply connected set A in the plane satisfies b(A) < q*c(A), provided b(A) and c(A) are defined. We have also shown that for any dimension d>0 there is a constant r_d>0 such that any set A in R^d satisfies b_d(A) < r_d*c(A), provided b_d(A) and c(A) are defined.

Here are two examples of open problems in this area:

*) For a set A in R^d satisfying suitable topological assumptions (e.g. A being homeomorphic to an open ball), is there a nontrivial lower bound for c(A) in terms of b_{d-1}(A) only? For d=2, such a bound is given by the first result mentioned above.

*) Suppose that A is a set of unit measure in R^d and b_k(A) is positive. Does this imply that we can find a d-dimensional simplex whose measure is "large" (in terms of b_k(A)) and whose every k-dimensional face is contained in A?

The main problem is to find lower bounds on c(A) in terms of the indices b_k(A). Several such results were recently proven in my joint work with Balko, Valtr and Walczak. Specifically, we have shown that there is a constant q>0 such that any simply connected set A in the plane satisfies b(A) < q*c(A), provided b(A) and c(A) are defined. We have also shown that for any dimension d>0 there is a constant r_d>0 such that any set A in R^d satisfies b_d(A) < r_d*c(A), provided b_d(A) and c(A) are defined.

Here are two examples of open problems in this area:

*) For a set A in R^d satisfying suitable topological assumptions (e.g. A being homeomorphic to an open ball), is there a nontrivial lower bound for c(A) in terms of b_{d-1}(A) only? For d=2, such a bound is given by the first result mentioned above.

*) Suppose that A is a set of unit measure in R^d and b_k(A) is positive. Does this imply that we can find a d-dimensional simplex whose measure is "large" (in terms of b_k(A)) and whose every k-dimensional face is contained in A?

Zdeněk Dvořák Tw-fragility and some related questions

A class C of graphs is tw-fragile if
for every positive integer k, there exists an integer r as follows: for
every graph G from C, there exist k disjoint subsets of its vertices,
such that removing any of them from G decreases its treewidth to at
most r. As an example, all proper minor-closed classes of graphs
are known to have this property.

Characterizing tw-fragile classes is a tough problem, in particular due to existence of classes (such as 3-dimensional grids) whose non-tw-fragility is only established using surprisingly involved arguments. However, a fractional version of the property seems easier to handle. The talk considered the question whether all hereditary classes with strongly sublinear separators are fractionally tw-fragile, and presented some results supporting this conjecture.

Characterizing tw-fragile classes is a tough problem, in particular due to existence of classes (such as 3-dimensional grids) whose non-tw-fragility is only established using surprisingly involved arguments. However, a fractional version of the property seems easier to handle. The talk considered the question whether all hereditary classes with strongly sublinear separators are fractionally tw-fragile, and presented some results supporting this conjecture.

Patrice Ossona de Mendez

TBA