[Facets-of-complexity] Invitation to Monday Lecture and Colloquium - November 4th 2019

["Ita Brunke" <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture and Colloquium on
November 4th at 14:15 h and 16:00 at FU Berlin.

Location:
Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, November 4th - 14:15 h

Lecture: Günter Rote (Freie Universität Berlin)

Title: Lattice paths with states, and counting geometric objects via
production matrices

Abstract:

We consider paths in the plane governed by the following rules: (a) There
is a finite set of states. (b) For each state q, there is a finite set
S(q) of allowable "steps" ((i,j),q′). This means that from any point (x,y)
in state q, we can move to (x+i,y+j) in state q′. We want to count the
number of paths that go from (0,0) in some starting state q0 to the point
(n,0) without ever going below the x-axis. There are strong indications
that, under some natural technical conditions, the number of such paths is
asymptotic to C^n/(√n^3), for some "growth constant" C which I will show
how to compute.

I will discuss how lattice paths with states can be used to model
asymptotic counting problems for some non-crossing geometric structures
(such as trees, matchings, triangulations) on certain structured point
sets. These problems were recently formulated in terms of so-called
production matrices.

This is ongoing joint work with Andrei Asinowski and Alexander Pilz.


Coffee & Tea Break:
Room 134

Time: Monday, November 4th - 16:00 h

Lecture: Liana Yepremyan (University of Oxford)

Title: On the size Ramsey number of bounded powers of bounded degree trees

Abstract:

We say a graph G is Ramsey for a graph H if every red/blue edge-colouring
of the edges of G contains a monochromatic copy of H. The size Ramsey
number of a graph H is defined to be the minimum number of edges among all
graphs which are Ramsey for H. The study of size Ramsey numbers originated
by the work of Erdős, Faudree, Rousseau and Schelp from 1970's. This
number was studied for graphs including paths, cycles, powers of paths and
cycles, trees of bounded degree. For all mentioned graphs it was shown
that the size Ramsey number grows linearly in the number of vertices ("is
linear"). This line of research was inspired by a question of Beck who
asked whether the size Ramsey number is linear for graphs of bounded
degree. Later this was disproved by Rödl and Szemerédi. In this talk I
will present our recent result showing that fixed powers of bounded degree
trees also have linear size Ramsey number. Equivalently, this result says
that all graphs of bounded degree and bounded treewidth have linear size
Ramsey number. We also obtain off-diagonal version of this result. Many
exciting problems remain open. This is joint work with Nina Kam\v{c}ev,
Anita Liebenau and David Wood.