- Introduction & motivation
- Exercise session -- guided solution of problems from the area, to help everybody understand what is it all about
- Two talks on somewhat advanced topic.

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

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 kam.mff.cuni.cz. We will then meet and decide which parts of the book will be selected, and who will take each part.

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.

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.

Nice student paper about a certain question on independent sets in products of graphs. No prior knowledge needed.

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.

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.

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.

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.