Program at Spring school 2017

This year the scientific program at the spring school will consist of two 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 speaker 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.
Dependent random choice (coordinator Zdeněk Dvořák)
Dependent random choice is a method used in extremal graph theory based on the following idea. We randomly choose a small subset of vertices B from a sufficiently dense graph. We let A denote the set of all common neighbors of vertices in B. Than the probability, that A is big and almost all k-tuples in A have a lot of neighbors in common, is big (for a k-tuple with few neighbors in common the probability that we choose B as its subset is small). We can use this set A to construct different subgraphs of the given graph.
Network coding (coordinator Karel Král)
Network coding is a technique that might improve network throughput and performance. This tutorial will introduce network coding and its benefits, design of network codes and perhaps some applications. The basic idea of network coding is that we can allow nodes of a network to process incoming independent information flows (packets of data). At the network layer we could for instance perform binary addition of independent bitstreams.
I would like one or two participants. We will mainly use the tutorial paper NCF of Christina Fragouli and Emina Soljanin. Please note that I would like you to do a full rehersal (talk with the handout) before the Spring School.

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.
Cops and Robbers ordinals of cop-win trees--Anthony Bonato, Przemyslaw Gordinowicz, Geňa Hahn
De Bruijn-Eros-type theorems for graphs and posets--Pierre Aboulker, Guillaume Lagarde, David Malec, Abhishek Methuku, Casey Tompkins
Note on terminal-pairability in complete grid graphs--Ervin Gyori, Tamás Róbert Mezei, Gábor Mészáros
Equilateral Triangles and the Fano Plane--Philippe Caldero and Jérome Germoni
This paper is harder and it is recommended for more experienced speaker.
A Short Proof That $\chi$ Can be Bounded $\varepsilon$ Away from $\Delta + 1$ toward $\omega$--Andrew D. King and Bruce A. Reed
Searching for knights and spies: A majority/minority game--Mark Wildon
Bubblesort, stacksort and their duals--Luca S. Ferrari
On the Shortest Path Game--Andreas Darmann, Ulrich Pferschy, Joachim Schauer
Edge-coloring of 3-uniform hypergraphs--Pawel Obszarski, Andrej Jastrzebski
A relaxation of the Bordeaux Conjecture -- Runrun Liu, Xiangwen Li, Gexin Yu
Fractional triangle decompositions in graphs with large minimum degree--Francois Dross
On the probability that a random subgraph contains a circuit -- Peter Nelson
Nice and simple probabilistic proof
Counting the Number of Perfect Matchings in K5-Free Graphs -- Simon Straub, Thomas Thierauf, Fabian Wagner
Uses variant of Pfaffian orientations to compute number of perfect matchings in polynomial time.
Chip Games and Pintability -- Lech Duraj, Grzegorz Gutowski, Jakub Kozík
Correspondence between online coloring and certain combinatorial games. Quite easy paper.
Zeilberger to the rescue -- Moa Apagodu
An example of how computer based proofs work for combinatorial sums. Pretty impressive. Some background about Wilf-Zeilberger method, Gospers algorithm, etc. should be studied beforehand (can provide references, e.g A=B book is awesome).
Ramsey numbers of trees versus odd cycles -- Matthew Brennan
Estimating Ramsey numbers. In this setting the number is pretty small -- and the paper is not long either.
Clique coloring of dense random graphs -- Noga Alon, Michael Krivelevich
We color a random graph so that no clique is monochromatic. Log(n) colors is the right number. The proof is quite short and nontechnical, but previous exposure to prababilistic method is useful/required.
The Cerny conjecture and 1-contracting automata -- Henk Don
Bounding the size of a synchronizing word for a finite automaton. Settles the conjecture for a (small) class of automata.
An improved bound on the fraction of cerrectable deletions -- Boris Bukh, Venkatesan Guruswami, Johan Hastad.
Nice paper by good authors. They analyze a new-ish type of codes (they should be robust against deleting some number of characters).
Ranks of matrices with few distinct entries -- Boris Bukh
INterestin algebra (and linear algebra) with applications to extremal combinatorics. Nicely presented but somewhat long (don't attempt to present all).
Priority Transmission -- Noga Alon, Guy Rutenberg
Broadcast model analyzed by expert combinatorialist (and probably his student).