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
If you want to participate in a series, please contact both us spring-at-kam.mff.cuni.cz and the coordinator.
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 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).