You are cordially invited to our next Monday Lecture &
Colloquium on February 3rd - again at regular times - at 14:15
h & 16:00 h at FU Berlin. Location: Freie Universität Berlin Takustr. 9 14195 Berlin Time: Monday, February 3rd - 14:15 h Lecture: Sándor Kisfaludi-Bak (MPI Saarbrücken) Title: Separators and exact algorithms for geometric
intersection graphs Given n ball-like objects in some metric space, one can
define a geometric intersection graph where the vertices
correspond to objects, and edges are added for pairs of
objects with a non-empty intersection. A separator of a graph
is a small or otherwise "nice" vertex set whose removal
disconnects the graph into two roughly equal parts. In this
talk, we will see some separator theorems for intersection
graphs in Euclidean and hyperbolic space. One can use these
separators to design simple divide and conquer algorithms for
several classical NP-hard problems. It turns out that
well-designed separators often lead to subexponential
algorithms with optimal running times (up to constant factors
in the exponent) under the Exponential Time Hypothesis (ETH). Coffee & Tea Break: Room 134 Time: Monday, February 3rd - 16:00 h s.t. Colloquium: Yanitsa Pehova (University of Warwick) Title: Characterisation of quasirandom permutations by
a pattern sum We say that a sequence {π_{_i}} of permutations
is quasirandom if, for each k>1 and each σ∈S_{_k},
the probability that a uniformly chosen k-set of entries of π_{_i}
induces σ tends to 1/k! as i tends to infinity.
It is known that a much weaker condition already forces π_{_i}
to be quasirandom; namely, if the above property holds for all σ∈S_{4}.
We further weaken this condition by exhibiting sets S⊆S_{4},
such that if randomly chosen four entries of π_{_i}
induce an element of S with probability tending to |S|/24,
then {π_{_i}} is quasirandom. Moreover, we are
able to completely characterise the sets S with this
property. In particular, there are exactly ten such sets, the
smallest of which has cardinality eight. This is joint work with
Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan
Volec. |