Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, May 9, 2016

Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005



Lecture - 14:15

Oleg Pikhurko - University of Warwick

Measurable Banach-Tarski via Augmenting Paths

Abstract:
The famous result of Banach-Tarski states that any two bounded subsets A and B of R^n, n>2, with non-empty interior are equidecomposable, that is, one can split A into finitely many parts and move the parts using isometries to obtain a partition of B. We show that if, additionally, A and B are (Lebesgue) measurable and of the same measure, then one can further require that all parts are measurable. This follows from the a.e.-stabilisation of some local augmenting path algorithm.

This is a joint work with Lukasz Grabowski and Andras Mathe.




Colloquium - 16:00

Codruţ Grosu - Freie Universität Berlin

Quasirandom Cayley graphs (Doctoral defense)

Abstract:
A graph is called quasi-random if at a large scale, it "looks" as if it has a random edge distribution. A classic result of Chung, Graham and Wilson makes this definition precise and further shows it is equivalent to several other seemingly unrelated properties: in particular, for pn-regular graphs it is equivalent to the second eigenvalue of the adjacency matrix being small. However, the result of Chung, Graham and Wilson is valid only for graphs with constant density not depending on the number of vertices. As shown by Krivelevich and Sudakov, there are examples of sparse regular graphs with a random-like edge distribution, and for which the second eigenvalue is large. The purpose of my talk is to present a recent result of Conlon and Zhao, which shows that at least for Cayley graphs the equivalence still holds. This result is interesting as many of the explicit constructions of quasi-random graphs we have today are Cayley graphs. The proof recasts the problem in terms of norms of matrices and uses an inequality of Grothendieck, which we shall explain.



Letzte Aktualisierung: 09.05.2016