Monday, May 9, 2016
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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.