Program at Spring school 2014
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.
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.
The underlying philosophy of Ramsey-type statements is that every sufficiently large system contains a well-organized subsystem. This theory contains many beautiful
and famous results, for example Ramsey´s Theorem for hypergraphs, Theorem of Erdös and Szekeres about convex subsets of plane or Van der Waerden Theorem for
arithmetic progressions.
In this section we would like to introduce some other results from Ramsey theory (it could be Rado´s Theorem, Ramsey numbers for graphs with
a bounded degree, chromatic number of plane, induced Ramsey Theorems, for example) and used techniques (Stepping-Up Lemma, probabilistic methods, topological
dynamics) which are usually omitted in the lectures. We can also focus on the recent results in this area (monochromatic monotone paths and their connection to
integer partitions, homogeneous point-sets in R^d, results about semialgebraic predicates). For reporting basic combinatorial knowledge are sufficient.
Kolmogorov complexity is, in many senses, a universal measure of the
complexity of combinatorial and other discrete objects. To put it simply,
Kolmogorov complexity $C(x)$ of an object (string, graph, etc.) $x$ is the
bit-length of a shortest program in some universal language that generates $x$
as its output. It might be surprising, but the Kolmogorov complexity does not
depend on the language selected under some reasonable constraints (be it C,
assembly language or English) up to an additive constant $O(1)$ depending on
the language.
The miniseries will consist of a brief introduction to Kolmogorov
complexity and its basic properties, some applications (e.g. a purely
combinatorial weak bound on the number of prime numbers below $n$), an exercise
session and 2-3 papers with slightly advanced results and applications.
The main source of information is the book An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitanyi. Michal Koucký's
A Brief Introduction to Kolmogorov Complexity [PDF] is available online.
The papers to be presented will be decided with your participation; if
you are interested in joining the series let us know right now! An
inspirational list of papers and topics follows.
Among all normalized/admissible distance metrics on strings (and
indirectly also other combinatorial objects), the Kolmogrov information
distance derived from relative Kolmogorov complexity is always the least (up to
the usual additive $O(1)$). Described in Li and Vitanyi book in sections 8.3
and 8.4 (3rd ed). A talk on this topics would likely
also contain some extension or application of this principle to be selected.
It is incomputable to find the shortest program for given string, but
it is possible to generate few programs one of which will be close to the
shortest one, as presented in
Short lists with short programs in short time by Bauwens et el.
[arXiv] and
Linear list-approximation for short programs (or the power of a few random bits) by Bauwens et al.
[arXiv].
A closer look at Kolmogorov random (incompressible) strings and the
same notion with limited "decompression" time. While it is undecidable which
strings are K-random, the characteristic vector of the set of all K-random
strings is itself not K-random. Surprisingly it becomes K-random when we limit
the time the "decompression" program may use.
Derandomizing from random strings by Buhrman et al.
[PDF].
If we choose $n$ points in the unit square randomly, the expected area
of the smallest triangle defined by these points is $\Theta(n^{-3})$ (even
almost surely), the paper
Kolmogorov Complexity and a Triangle Problem of the Heilbronn Type by Jiang et al.
[PDF] and an older, similar paper
The Average-Case Area of Heilbronn-Type Triangles by the same authors
[PDF].
PCP theorem and approximation (coordinator
Dušan Knop)
Understanding of what PCP theorem is all about (no proof though) and how it
can be used for approximation algorithms -- or rather, for bounding their
efficiency.
Algorithmic game theory is an area in the intersection of game theory and algorithm design: there is a game framework with
many players, each of them optimizes its own payout. The usual object of interest is how the equilibria of such games look like,
these may be considered an output of the computational model.
This session aims to give an introduction to the basic concepts,
followed by several talks on more advanced topics.
The session will be composed from the book by Nisan and Roughgarden: Algorithmic Game Theory.
The participants interested in the AGT topic are encouraged to contact Tomá
by email at the addres valla at the domain kam.mff.cuni.cz.
We will then meet and decide which parts of the book will be selected,
and who will take each part.
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.
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.
In 1932 Erdős conjectured, that in arbitrary infinite $\pm 1$ sequence $(x_n)$ there is an
arithmetic progression $x_d, x_{2d}, \dots, x_{kd}$ with arbitrary high sum.
In this paper a small case of this conjecture is reformulated as a SAT problem and
SAT solvers are used to verify it, getting better bounds for it than what was known without use of computer.
Short and easy, it could be inspiration for playing with SAT solver on your own.
The Comb in the title means infinite square grid with most of the horizontal edges removed: only those along
the $x$ axis remain. The study of random walk on this graph was started by physicist as a model
of "anomalous diffusion". During their study they heuristically derived that during first $n$ steps, the
walk visits roughly $n^{3/4}$ of vertices. In this paper the authors prove that the answer is
instead $n^{1/2} \log n$. The proof is not hard, but prior exposure to probability would be
useful.
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.