Lectures and Colloquia during the semester

Humboldt-Universität zu Berlin

Rudower Chaussee 5, 12489 Berlin

Room 3.101

** Lecture - 14:15**

### Alexander Scott - University College London

### Reconstructing subsets of the plane

*Abstract:*
The *k*-deck of a set *S* in the plane is the collection of all its
subsets of size *k*, given up to rigid motion. For instance, the
*2*-deck can be thought of as the set of distances (with multiplicity)
determined by the set. We discuss the problem of when a finite subset
of the plane is determined (up to rigid motion) by its *k*-deck. We
also give some results for infinite subsets of the plane.

** Colloquium - 16:00**

### Shi Lingsheng - Humboldt-Universität zu Berlin

### Cube Ramsey Numbers are Polynomial

*Abstract:*
Given a graph *G*, the Ramsey number *R(G)* is the least integer *p* such
that for all colorings of the edges of complete graph of order *p*, at least one of the monochromatic subgraphs contains a copy of *G*.
In 1973, Burr and Erdos asked whether there is a constant *c* such that *R(Q_n) \le c2^n* where *Q_n* is an *n*-cube i.e. *R(Q_n)* is linear in the order of *Q_n*. Though we are unable to settle this question, we can deduce a polynomial bound *R(Q_n) < 2^{(3+\sqrt5)n/2+o(n)}* by showing that for any positive constant *c* and bipartite graph *G=(U,V;E)* of order *n* where the maximum degree of vertices in *U* is at most *c\log n*, *R(G) < n^{1+(c+\sqrt{c^2+4c})/2+o(1)}*. The proof is based on an idea of Kostochka and Rödl.

[top]