# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, February 8, 2010

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005

Lecture - 14:15

### From Irrational Numbers to Matchings: Markov´s Uniqueness Problem

Abstract:
A celebrated result in number theory is the Theorem of Markov which relates two seemingly totally different subjects: approximations of irrational numbers and the solutions of a certain equation. A proof, which Markov only sketched, was eventually provided in detail by Frobenius precisely 100 years ago. In his paper Frobenius mentioned a problem, now known as the uniqueness conjecture, which has remained unsolved to this day. I will tell you about the theorem and the conjecture, and discuss the connections to trees, groups, combinatorics of words, lattice paths, and matchings of plane graphs.

Colloquium - 16:00

### The orbit rigidity matrix of a symmetric framework

Abstract:
We present a new method for detecting non-trivial – non-congruent – finite motions in symmetric bar and joint frameworks, i.e., motions that continuously displace the joints of the framework while holding the lengths of all bars fixed and changing the distance between two unconnected joints. Basic to this method is the construction of an `orbit rigidity matrix' whose columns and rows correspond to a set of representatives for the vertex orbits and edge orbits of the underlying graph of the framework, respectively. For frameworks that are generic modulo the prescribed symmetry, a sufficiently large kernel of the `orbit rigidity matrix' guarantees the existence of a non-trivial finite motion in the framework. Thus, symmetric frameworks can often be shown to be flexible by simply counting variables (vertex orbits) and equations (edge orbits). All the motions we detect with this new method have the nice property that they preserve the symmetry of the framework throughout the path.

Letzte Aktualisierung: 03.02.2010