Combinatorial rigidity and its applications

Témavezető: Jordán Tibor
ELTE TTK, Operációkutatási Tsz.
email: tibor.jordan@ttk.elte.hu

Projekt leírás

A d-dimensional framework (also called geometric graph) consists of a set V of n points in the d-dimensional Euclidean space and a designated subset E of the pairs of points. The distance between each pair u,v of points in E, which is the length of the line segment from u to v, is assumed to be fixed. The fixed distances are naturally described by a graph G on vertex set V and edge set E. We can think of the framework as a bar-and-joint structure with rotatable joints (V) and rigid bars (E).

Rigidity theory is concerned with the following basic geometric question: do the fixed distances in E determine all the pairwise distances (locally, or globally)? Can the framework be deformed so that the distances in E are preserved? When does the answer depend only on the graph G? Perhaps the first result in this area is the celebrated theorem of Cauchy on the rigidity of triangulated convex polyhedra. It is a very active field of research with several applications (for example, sensor network localization, molecular conformation, CAD, statics, control theory). It is in the intersection of combinatorics, algebra, and geometry, in which advanced methods from several areas (e.g. graph theory, matroid theory, algebraic geometry) have been used successfully.

Előfeltételek

discrete mathematics, basics of graph theory. matroid theory is a plus.

Hallgató

Korábbi hallgatók