- Béla Bollobás, Cambridge University, UK, and University of Memphis, TN, USA
- Frank Ruskey, University of Victoria, Canada
- Esko Ukkonen, University of Helsinki, Finland
Invited talks and abstracts:
- Béla Bollobás: Monotone Cellular Automata
Cellular automata, introduced in the 1940s by von Neumann, are interacting particle systems. In its simple form, we have a set of sites arranged in a grid-like fashion, with each site in one of finitely many states. Starting with such an ‘initial configuration’, at each time-step the system updates itself according to some fixed local rule: each site goes into a state that depends only on the states of a few nearby sites. Examples include the Ising model of ferromagnetism and simple models of the brain.
A cellular automaton with states 0 and 1, say, is monotone if every site in state 1 remains in sate 1 for ever. One of the simplest monotone cellular automata is bootstrap percolation with infection parameter r, introduced in 1979 by Chalupa, Leith and Reich. This process is an oversimplified model of the spread of an infection on a graph (with 0 meaning ‘healthy’ and 1 ‘infected’), in which a healthy site gets infected if it has at least r infected neighbours. By now, there is a huge literature of bootstrap percolation, with most of the early results due to probabilists, statistical physicists, and computer scientists, and many recent results proved by combinatorialists. I shall present some basic facts about bootstrap percolation, and will describe some impor- tant theorems due to Aizenman, Lebowitz, Cerf, Manzo, Cirillo and Holroyd, culminating in some substantial results I have proved with Balogh, Duminil-Copin and Morris.
Recently, with Smith and Uzzell, I introduced a far-reaching generalization of bootstrap percolation on lattices and lattice-like finite graphs. The only assumptions we made about such a process is that it is local, homogeneous and monotone. Surprisingly, much can be proved about these very general processes on Z^2; in particular, Smith, Uzzell, Balis- ter, Przykucki and I classified them into three classes, and proved much about the critical probability in each class. Very recently, Duminil- Copin, Morris, Smith and I have proved much more precise results about the most important class in the classification.
In my lecture, aimed at non-specialists, I shall give a brief introduction to some aspects of cellular automata. I shall assume very little and will keep my lecture simple.
- Frank Ruskey: Recent results about Venn diagrams
(download pdf, attention: 18.8 MB)
An n-Venn diagram is a collection of n simple closed curves in the plane that divide it into 2^n non-empty regions, one unique region per possible intersection of the interiors/exteriors of the curves. If the curves lie in general position; i.e., so that at most 2 curves intersect at a point then it is unknown whether rotationally symmetric diagrams exist for every prime n (the primality of n being an easily proved necessary condition). However, if curves can intersect at 3 or more curves, rotationally symmetric diagrams exist for prime n, and the proof relies on a modification of the classic symmetric chain decomposition of the Boolean lattice. In this talk this proof and later developments, such as the enumeration of symmetric Venn diagrams, will be surveyed. Additional open problems in the area of Venn diagrams will be discussed; e.g., can a new curve always be added to a Venn diagram to get a new Venn diagram?
- Esko Ukkonen: Identifiability of a string from its substrings (download pdf)
A classic algorithmic challenge in biological sequence analysis, the genome assembly problem asks one to reconstruct the DNA sequence from the short fragments (called ‘reads’) that a DNA sequencing instrument samples from the original sequence in massive amounts but with some reading errors. The talk discusses the exact version of the problem in which the reads are noiseless. Given a collection F of reads (substrings) sampled from an unknown target string T, the problem is to reconstruct T from F. If F covers the entire T several times and if the repeated substrings of T are contiguously covered by the reads in F, the reconstruction becomes straightforward: Just superpose the reads as suggested by their matching suffixes and prefixes. If, however, there are repeats that are longer than the reads – as is the case for DNA sequences – the reconstruction becomes ambiguous as there may be several different reconstructions suggested by the reads. We demonstrate that identifying a unique solution is possible from F, if F is the full k-mer spectrum of T and T does not contain any 3-repeats of length k-1 and not any interleaved pair of 2-repeats of length k-1. A finite-state automaton-like representation of the pairwise overlaps of the reads is introduced such that the identifiability of T reduces to the uniqueness of the Eulerian path in this representation. Generalization for more realistic F with variable-length reads and non-uniform coverage is considered.
- G. Bresler, M. Bresler and D. Tse: Optimal assembly for high throughput shotgun sequencing. BMC Bioinformatics 14, Suppl. 5 (2013), S18
- E. W. Myers: The fragment assembly string graph. Bioinformatics 21, Suppl. 2 (2005), ii79-ii85.
- P. A. Pevzner, H. Tang and M. S. Waterman: An Eulerian path approach to DNA fragment assembly. PNAS 98 (2001), 9748-9753.
- E. Ukkonen: Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science 92 (1992), 191-211.