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.