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

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

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

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.
This paper is harder and it is recommended for more experienced speaker.
Nice and simple probabilistic proof
Uses variant of Pfaffian orientations to compute number of perfect matchings in polynomial time.
Correspondence between online coloring and certain combinatorial games. Quite easy paper.
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).
Estimating Ramsey numbers. In this setting the number is pretty small -- and the paper is not long either.
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.
Bounding the size of a synchronizing word for a finite automaton. Settles the conjecture for a (small) class of automata.
Nice paper by good authors. They analyze a new-ish type of codes (they should be robust against deleting some number of characters).
INterestin algebra (and linear algebra) with applications to extremal combinatorics. Nicely presented but somewhat long (don't attempt to present all).
Broadcast model analyzed by expert combinatorialist (and probably his student).