Invited speakers
1. Marc Noy
Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain & Barcelona Graduate School of Mathematics, Barcelona, Spain
Title: Logic of sparse random graphs
Abstract: We survey recent results on limiting probabilities of graph properties expressible in first order logic and monadic second order logic for two models of sparse random graphs: the classical model G(n,p) with p = c/n, and random planar graphs and related classes of graphs under the uniform distribution.
Theoretical Computer Science at the Institute of Mathematical Sciences, Chennai, India & Computer Science at University of Bergen, Norway
Title: Parameterized algorithms for geometric graphs via decomposition theorems
Abstract: Parameterized complexity is one of the most established algorithmic paradigms to deal with computationally hard problems. In the first two decades, the field largely focused on problems arising from studies of graphs and networks. However, lately the focus has changed substantially and it has started to permeate into other fields such as computational geometry, and computational social choice theory. In this talk, we will survey some exciting developments in the emerging field of parameterized computational geometry through our contributions. We will focus on designing efficient parameterized algorithms on unit-disk graphs via new graph decomposition theorems.
CNRS, projet COATI, commun I3S (CNRS, Univ. Nice-Sophia Antipolis), Sophia Antipolis, France & INRIA (UR Sophia Antipolis), Sophia Antipolis, France
Title: Unavoidability and universality of digraphs
Abstract: A digraph $F$ is {\it $n$-unadoidable} (resp. {\it $n$-universal}) if it is contained in every tournament of order $n$ (resp. $n$-chromatic digraph). Well-known theorems imply that there is an $n_F$ such that $F$ is $n_F$-unavoidable (resp. {\it $n_F$-universal}) if and only if $F$ is acyclic, (resp. an oriented forest). However, determining the smallest $n_F$ for which it occurs is a challenging question. In this talk, we survey the results on unavoidability and universality with an emphasis on oriented forests. In particular, we shall detail the following new results obtained jointly with F. Dross: every arborescence of order $n$ with $k$ leaves is $(n+k-1)$-unavoidable, $(\frac{21}{8} n- \frac{47}{16})$-unavoidable, and $(n+ 144k^2 - 280k + 124)$-unavoidable.