Program at Spring school 2014

This year the scientific program at the spring school will consist of several thematic series and also some "stand-alone" presentations.


In our (carefully selected :-)) series the speakers will have opportunity to present a topic somewhat deeper than is possible in one talk. Typical series will consist of four 90-minutes talks: (Of course, variation to this scheme will probably occur.) Every series has its coordinator, ask him about details. It is expected that speker in each series will discuss his presentation with the coordinator -- well before the spring school. This includes actual "rehearsal" of the talk. We believe that both the speaker and the audience will benefit from this. Because of this it is better suited towards participants from Prague. Of course, if you feel mesmerized by one of the suggested topics, you may inquire, we will see what can be done.

List of the series

If you want to participate in a series, please contact both us and the coordinator.
Ramsey theory (coordinator Martin Balko)
The underlying philosophy of Ramsey-type statements is that every sufficiently large system contains a well-organized subsystem. This theory contains many beautiful and famous results, for example Ramsey´s Theorem for hypergraphs, Theorem of Erdös and Szekeres about convex subsets of plane or Van der Waerden Theorem for arithmetic progressions.

In this section we would like to introduce some other results from Ramsey theory (it could be Rado´s Theorem, Ramsey numbers for graphs with a bounded degree, chromatic number of plane, induced Ramsey Theorems, for example) and used techniques (Stepping-Up Lemma, probabilistic methods, topological dynamics) which are usually omitted in the lectures. We can also focus on the recent results in this area (monochromatic monotone paths and their connection to integer partitions, homogeneous point-sets in R^d, results about semialgebraic predicates). For reporting basic combinatorial knowledge are sufficient.

Kolmogorov complexity and its applications (coordinator Tomáš Gavenčiak)

Kolmogorov complexity is, in many senses, a universal measure of the complexity of combinatorial and other discrete objects. To put it simply, Kolmogorov complexity $C(x)$ of an object (string, graph, etc.) $x$ is the bit-length of a shortest program in some universal language that generates $x$ as its output. It might be surprising, but the Kolmogorov complexity does not depend on the language selected under some reasonable constraints (be it C, assembly language or English) up to an additive constant $O(1)$ depending on the language.

The miniseries will consist of a brief introduction to Kolmogorov complexity and its basic properties, some applications (e.g. a purely combinatorial weak bound on the number of prime numbers below $n$), an exercise session and 2-3 papers with slightly advanced results and applications.

The main source of information is the book An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitanyi. Michal Koucký's A Brief Introduction to Kolmogorov Complexity [PDF] is available online.

The papers to be presented will be decided with your participation; if you are interested in joining the series let us know right now! An inspirational list of papers and topics follows.

Among all normalized/admissible distance metrics on strings (and indirectly also other combinatorial objects), the Kolmogrov information distance derived from relative Kolmogorov complexity is always the least (up to the usual additive $O(1)$). Described in Li and Vitanyi book in sections 8.3 and 8.4 (3rd ed). A talk on this topics would likely also contain some extension or application of this principle to be selected.

It is incomputable to find the shortest program for given string, but it is possible to generate few programs one of which will be close to the shortest one, as presented in Short lists with short programs in short time by Bauwens et el. [arXiv] and Linear list-approximation for short programs (or the power of a few random bits) by Bauwens et al. [arXiv].

A closer look at Kolmogorov random (incompressible) strings and the same notion with limited "decompression" time. While it is undecidable which strings are K-random, the characteristic vector of the set of all K-random strings is itself not K-random. Surprisingly it becomes K-random when we limit the time the "decompression" program may use. Derandomizing from random strings by Buhrman et al. [PDF].

If we choose $n$ points in the unit square randomly, the expected area of the smallest triangle defined by these points is $\Theta(n^{-3})$ (even almost surely), the paper Kolmogorov Complexity and a Triangle Problem of the Heilbronn Type by Jiang et al. [PDF] and an older, similar paper The Average-Case Area of Heilbronn-Type Triangles by the same authors [PDF].

PCP theorem and approximation (coordinator Dušan Knop)
Understanding of what PCP theorem is all about (no proof though) and how it can be used for approximation algorithms -- or rather, for bounding their efficiency.
Algorithmic game theory (coordinator Tomáš Valla)

Algorithmic game theory is an area in the intersection of game theory and algorithm design: there is a game framework with many players, each of them optimizes its own payout. The usual object of interest is how the equilibria of such games look like, these may be considered an output of the computational model.

This session aims to give an introduction to the basic concepts, followed by several talks on more advanced topics. The session will be composed from the book by Nisan and Roughgarden: Algorithmic Game Theory.

The participants interested in the AGT topic are encouraged to contact Tomá by email at the addres valla at the domain We will then meet and decide which parts of the book will be selected, and who will take each part.

Stand-alone presentations

If you have a good paper to present, tell us and we will consider it. The following is offered by us. If you have any opportunity at all to discuss your presentation with someone before the spring school, please do so. (If you are from Prague, you may try one of the senior organizors -- or anybody willing to listen.) Keep in mind, it is not important to go over all the lemmas and statements in the paper -- it is important to explain the main ideas and as many details as is useful to educate your audience.
Matthias Kriesell -- Packing Steiner trees on four terminals
When does a graph contain $k$ disjoint trees (not necessarily spanning), each of which contains a given $4$-element set? Nice classical graph theory, not too hard.
Carsten Thomassen -- Group flow, complex flow, unit vector flow, and the $(2 + \varepsilon)$-flow conjecture
Very nice and easy-to-read paper, although it would be helpful to have prior knowledge about nowhere-zero flows to better appreciate the results. Basic question: given a group $\Gamma$ and its subset $F$, when does a graph contain a $\Gamma$-flow using only values of $F$? A characterization is given for sets $F$, where the existence of such flow can be ensured by high-enough edge-connectivity. Many concrete cases are discussed.
Ágnes Tóth -- Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio
Nice student paper about a certain question on independent sets in products of graphs. No prior knowledge needed.
Noga Alon, Abbas Mehrabian -- Chasing a Fast Robber on Planar Graphs and Random Graphs
Yet another variant of cops and robbers game: the robber can move arbitrarrily fast. Contains computation with random graphs. Basic acquintance with probabilistic method (Markov inequality etc.) required. Try to separate the basic ideas from technical claims, those may be skipped.
Gabor Simonyi, Gabor Tardos -- On Directed Local Chromatic Number, Shift Graphs, and Borsuk-Like Graphs A recent version of chromatic number --- local chromatic number -- is studied for several types of graphs. Requirements: open mind.
Boris Konev, Alexei Lisitsa -- A SAT Attack on the Erdős Discrepancy Conjecture
In 1932 Erdős conjectured, that in arbitrary infinite $\pm 1$ sequence $(x_n)$ there is an arithmetic progression $x_d, x_{2d}, \dots, x_{kd}$ with arbitrary high sum. In this paper a small case of this conjecture is reformulated as a SAT problem and SAT solvers are used to verify it, getting better bounds for it than what was known without use of computer. Short and easy, it could be inspiration for playing with SAT solver on your own.
János Pach, Gábor Tardos -- The Range of a Random Walk on a Comb
The Comb in the title means infinite square grid with most of the horizontal edges removed: only those along the $x$ axis remain. The study of random walk on this graph was started by physicist as a model of "anomalous diffusion". During their study they heuristically derived that during first $n$ steps, the walk visits roughly $n^{3/4}$ of vertices. In this paper the authors prove that the answer is instead $n^{1/2} \log n$. The proof is not hard, but prior exposure to probability would be useful.
Matt DeVos, Jessica McDonald, Diego Scheide -- Average Degree in Graph Powers
By $k$-th power of a graph $G$ we here understand a graph with the same vertex-set and with edges $uv$ for all vertex-pairs of distance $\le k$ in $G$. Elementary graph theory is used to study the average degree of powers of a graph based on degrees of the graph itself. This has consequences in combinatorial number theory via Cayley graphs.