Monday, October 20, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
A coloring of the vertices of a graph G is called distinguishing if the trivial
automorphism is the only automorphism of G that preserves the coloring.
There is a vast literature on distinguishing graphs, finite or infinite. The lecture
begins with a general introduction to the topic and then focusses on infinite graphs.
For infinite graphs ,Tom Tucker conjectured that, if every automorphism of a connected,
infinite, locally finite graph moves infinitely many vertices, then there exists a
distinguishing coloring that uses only two colors. This is known as the Infinite Motion
Conjecture. Despite many intriguing partial results, it is still open and, together with
its generalizations to uncountable graphs, and to groups acting on structures, the main
topic of the talk.
On the way, numerous problems of various degrees of difficulty will be encountered.
Colloquium - 16:00
Abstract:
I will review the celebrated construction of the secondary polytope [2]
and its relation to connectivity of regular triangulations in the
graph of flips, and then present an example of a point set whose
triangulations are not connected by flips (probably one of the
5-dimensional constructions in [1]). This topic is related to the
first, more combinatorial part of my thesis, where we generalize
regular subdivisions of a point set in a new direction (which does not
preserve connectivity by flips).
[1] F. Santos, Non-connected toric Hilbert schemes. Math. Ann. 332:3
(2005), 645-665.
[2] I. M. Gelfand, M. M. Kapranov and A. V. Zelevinsky,
Discriminants, Resultants and Multidimensional Determinants,
Birkhäuser, Boston, 1994.