Vyuka - Martin Klazar

Tento workshop oslavil 70. narozeniny našeho učitele Jarika Nešetřila. Konal se na Patejdlově boudě (nad Špindlerovým Mlýnem ve výšce 972 metrů nad mořem) 13. - 16. dubna 2016. Myslím, že nejen mně se během workshopu zhmotnil duch kombinatorických seminářů a jarních a jiných škol, které Jarik pořádá již pro tolik generací nás, jeho studentů. Program si Jarik určoval "na místě" sám. Slyšeli jsme vskutku skvělé přednášky.

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

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.

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.

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 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.

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.

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.

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).

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?

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.

Horizonty kombinatoriky 2016 - Jarik is 70