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.


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.


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 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.
Statistical Physics of Optimization Problems (coordinator Tomáš Gavenčiak)
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.
Thomas Robinson, Sujith Vijay -- Dreidel Lasts $\mathcal{O}(n^2)$ Spins
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.
Mikhail Lavrov and Po-Shen Loh -- Hamiltonian increasing paths in random edge orderings
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$.
Bernhard A. Moser -- The Range of a Simple Random Walk on $\mathbb{Z}$: An Elementary Combinatorial Approach
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.
N. Alon -- Size and degree anti-Ramsey numbers
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.
N. Alon and P. Pralat -- Chasing robbers on random geometric graphs---an alternative approach, Discrete Applied Math., to appear.
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.
Marthe Bonamy, Nicolas Bousquet and Stéphan Thomassé -- The Erdős-Hajnal Conjecture for Long Holes and Anti-holes
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}$.
Alexandr Kostochka, Matthew Yancey -- Ore’s Conjecture for $k = 4$ and Grotzsch Theorem
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.
Rafał Kalinowski, Monika Pilśniak -- Distinguishing graphs by edge-colourings
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.
Michael S. Payne, Jens M. Schmidt, and David R. Wood -- Which point sets admit a $k$-angulation?
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).
Joanna Cyman, Tomasz Dzido, John Lapinskas, and Allan Lo -- On-line Ramsey Numbers of Paths and Cycles
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.
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.
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.
Pierre Aboulker -- Excluding 4-wheels
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.
Radoslav Fulek, Csaba D. Tóth -- Universal point sets for planar three-trees
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.
Luca S. Ferrari -- Bubblesort, stacksort and their duals
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.
Gábor Bacsó, Piotr Borowiecki, Mihály Hujter, Zsolt Tuza -- Minimum order of graphs with given coloring parameters
Varians of colorings of graphs.