Program at Spring school 2015
This year the scientific program at the spring school will consist
of several thematic series and also some "stand-alone" presentations.
Series
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:
- 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.
(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.
Handouts
It is a nice custom to provide handouts with the most basic definitions
and theorems to the audience. We provide a LaTeX
template for you (although the template is not mandatory). The text
should be an extended abstract. It will be used as a handout during the
presentation and then it will be recycled to "Sbornicek" (thin book about Spring School). So don't
be shy and write more than 10 lines :-)
List of the series
If you want to participate in a series, please contact both us spring-at-kam.mff.cuni.cz and the coordinator.
Hanani-Tutte theorem and related topics (coordinator
Martin Tancer)
The weak Hanani-Tutte theorem states that if a graph can be drawn in
the plane in such a way that every pair of edges crosses an even number of
times, then the graph is actually planar. There is also a stronger version of
this theorem. It requires that only those pairs of edges cross an even number
of times, which do not share a vertex. Even such a drawing of a graph implies
that a graph is planar.
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.
Minimalist-FPT practitioners course (coordinator
Dušan Knop)
We will provide a breaf introduction into the field of parameterized
complexity. Our main focus will be a practial design of algorithms and hardness
results. Several talks should focus on some important recent results (such as
using algebraic techniques to speed-up an algorithm or lower bounds on
kernelization). Advanced topics will be selected according to skills of
enrolled students.
The classical view on the complexity of various CSP-type problems (including
coloring, labeling homomorphism and other problems) looks at the hardest
problem instances and worst-cases, but for some NP-hard problems, most of the
instances can be actually very easy. In some cases, you can even tell whether a
large random instance has a coloring (with high probability) just by looking at
the edge density.
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.
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.
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.
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.
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.