Monday, November 17, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 7
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Thue-Morse sequence that can be defined by t_n = s(n) mod 2, where s(n) denotes
the binary sum-of-digits function, has been studied in many diff erent contexts
from combinatorics to algebra, number theory, harmonic analysis,
geometry and dynamical systems.
For example, it has a linear subword complexity and is almost periodic.
It is also one of the easiest examples of a non-trivial automatic
sequence, that is, a sequence
that is the output of a finite automaton, where the input are the
q-ary digits of a positive integer.
Since the subword complexity of the Thue-Morse sequence is linear (as
for all automatic sequences)
the entropy of the related dynamical system is zero. This also means
that is does not behave
like a random sequence. However, the situation changes drastically
when one uses proper subsequences
of automatic sequences, for example the subsequence along primes or squares.
It is conjectured that the resulting sequences are normal sequences so
that they are "random".
Recently this property was proved (together with C. Mauduit and J. Rivat)
for the Thue-Morse sequence along the subsequence of squares.
The purpose of this talk is give an overview of this field of research
and to present the
key techniques for obtaining distributional results.
Colloquium - 16:00
Abstract:
We say a family of sets is intersecting if all pairwise intersections are trivial. The celebrated Erdős--Ko--Rado theorem of 1961 shows that when n > 2k, the largest intersecting families of k-subsets of [n] are the trivial ones of size {n-1 \choose k-1}, which consist of all subsets containing a fixed element. This cornerstone of extremal set theory continues to inspire a great deal of research today.
Knowing the structure of the extremal intersecting families, it is natural to ask for the structure of the typical intersecting family. In this talk, we will show that almost all intersecting families are trivial, a result which in some sense strengthens the Erdős--Ko--Rado theorem. From this, we shall derive a sparse version of the Erdős--Ko--Rado theorem for random hypergraphs.
Time permitting, we will mention analogous results in the settings of permutations and vector spaces.
Joint work with Jozsef Balogh, Michelle Delcourt, Hong Liu and Maryam Sharifzadeh.