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

The task of the series is to introduce the Hanani-Tutte theorem; give a proof of it; show some interesting (and perhaps unexpected) applications of some of the variants of this theorem; and discuss related topics such as Hanani-Tutte theorem on other surfaces.

To get a closer look on statistical physics approach to combinatorial problems, we will present several papers looking at the behavior of typical (large and random) instances for several problems, and will see how can examining the space of solutions and almost-solutions together with some basic physics give us new insights and results.

The series is mostly reserved and will be kept small, but in case you would like to join, we can select one more paper. Note, however, that this is a more difficult topic and will require a lot of time to prepare individually.

A simple child game with a die is analyzed to understand how long does it take (on average).
Two proofs are given: one using Markov chains and another that is just counting (somewhat long
but not too much). Paper by students, elementary and simple.
An improved version of the paper proves a much stronger result but we do not need to worry about it here.

Edges of a complete graph $K_n$ are randomly labeled 1, 2, ..., $\binom{n}{2}$.
One then looks for a path with edges labeled in an increasing order.
For a inexperience speaker it could be sufficient to present
the (nice and simple) proof of Proposition 1 -- there is such path of length $(1-1/e+o(1))n$.

Consider a random walk taking $n$ steps on a line, we want to understand how much is it spread out,
that is, how many vertices the walk visits. This has been known for some time; in this
paper two new elementary proofs are given.

Edges of a graph are properly colored, we want to find a given subgraph that is "rainbow" -- all
edges of different colores. (Whereas in Ramsey theory we look for subgraphs of a single color.)
Short paper by the master of probability method.

In a game of cops and robber, the cops are trying to catch a robber, while moving on a given graph.
An important conjecture says that $O(\sqrt n)$ cops always suffice.
In search of counterexamples, people look for interesting constructions of graphs and try to analyse the game there.
Here, this is done with geometrically described graphs.

Erdos and Hajnal conjectured that, for every graph $H$, there exists a constant $c_H$ such that every graph $G$ on $n$ vertices
which does not contain any induced copy of $H$ has a clique or a stable set of size $n^{c_H}$.
This is in contrast to the graphs that are extreme cases of the Ramsey theorem -- these are graphs on $n$ vertices with the largest
clique or stable set of size $O(\log n)$.
The authors prove that for every $k$, there exists $c_k>0$ such that every graph $G$ on $n$ vertices not inducing a cycle of length at least $k$ nor its
complement contains a clique or a stable set of size $n^{c_k}$.

Famous Grotzsch theorem says that planar triangle-free graph can be colored by 3 colors.
Originally, this had a complicated proof. Here a extremely simple proof is provided by
studying 4-critical graphs -- graphs that are not 3-colorable but every subgraph is.

The paper is about a variant of graph coloring problem where the edges are
colored in such a way that the coloring is not preserved by any automorphism of
the graph. The difficulty of the paper is between easy and moderate. Some of
the results of the paper may be skipped in case of lack of time.

The paper provides a characterization of a certain type of k-angulations of a
point set (k-angulations generalize triangulations). The main task is to
explain the main idea, possibly skipping some details. We also recommend to
prepare some pictures in advance which can be used during the lecture (e.g. for
a beamer).

The paper considers a game with two players: a builder and a painter. The
bulider builds a graph by adding edges one by one and the painter then
immediately paints the edges of the graph in blue or in red. Given two graphs
$G$ and $H$ the task of the builder is to build the graph in such a way that he
obtains a blue copy of $G$ or a red copy of $H$ as soon as possible whereas the
task of the painter is to prolongue this period. The paper provides bounds on
number of necessary steps for certain choices of $G$ and $H$.

Some parts of the paper are technical and should be skipped. The task for the lecturer is to choose well which parts should be skipped.

Some parts of the paper are technical and should be skipped. The task for the lecturer is to choose well which parts should be skipped.

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.

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.

A 4-wheel is a graph formed by a cycle C and a vertex not in C that has at
least four neighbors in C. If $G$ does not contain a 4-wheel as a subgraph then
$G$ is 4-colorable.

There is a point set in plane of size $O(n^{3/2} \log n)$ such that all 3-trees
may be drawn on it using straight lines.

Some interesting properties of sorting algorithms. The set of permutations
sortable by a prescribed number of iterations of bubblesort and its dual is a
pattern class.

Varians of colorings of graphs.