Paradoxical flexibility of frameworks
Project goals
A framework which is a graph together with a realization of its vertices in some space is called rigid if there are only finitely many realizations inducing the same edge lengths as the given one, up to isometries. Otherwise, the framework is flexible. Since rigidity is a generic property, the graph itself can be called rigid if every generic realization yields a rigid framework. Nevertheless, such a rigid graph can have non-generic flexible realizations. These paradoxical situations are investigated in the frame of this project. Using tools from algebraic geometry, the existence of paradoxical motions in the plane was recently characterized in terms of a special type of colorings of the edges. The purpose of this project is to combine graph theory and combinatorics with more sophisticated tools from algebraic geometry in order to be able to answer paradoxical flexibility questions in a broader sense. As such we are interested in symmetric flexes, different generalizations of rigidity, applications thereof to sensor networks and the above mentioned edge colorings.
Keywords
Paradoxical MotionFlexible FrameworkRigid GraphOverconstrained MechanismGraph RealizationEdge Coloring
Public support
Provider
Czech Science Foundation
Programme
—
Call for proposals
—
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
M2 - International cooperation
Contract ID
22-04381L
Alternative language
Project name in Czech
Paradoxně pohyblivé realizace grafů
Annotation in Czech
Realizace vrcholů grafu v rovině nebo jiném prostoru se nazývá tuhá, pokud existuje pouze konečně mnoho jiných realizací daného grafu se stejnými délkami hran (až na shodná zobrazení). Pokud naopak můžeme realizaci spojitě deformovat při zachování délek hran, nazýváme ji pohyblivou. Jelikož tuhost je generická vlastnost, má smysl nazvat samotný graf tuhý, pokud je jeho libovolná generická realizace tuhá. Nicméně, i tuhý graf může mít pohyblivé, negenerické, realizace. Tyto paradoxní situace jsou předmětem tohoto projektu. S využitím algebraické geometrie bylo nedávno ukázáno, že graf má paradoxní pohyblivou realizaci v rovině, pokud pro něj existuje jisté hranové obarvení. Cílem tohoto projektu je zkombinovat teorii grafů a kombinatoriku se sofistikovanějšími nástroji algebraické geometrie ke zkoumání paradoxní pohyblivosti v širším smyslu. Zajímají nás symetricky pohyblivé realizace, různá zobecnění konceptu tuhosti nebo realizace na algebraických plochách, třídy grafů relevantní pro aplikace do senzorových sítí či již zmíněná hranová obarvení.
Scientific branches
Solution timeline
Realization period - beginning
Oct 1, 2022
Realization period - end
Dec 31, 2025
Project status
K - Ending multi-year project
Latest support payment
Jul 3, 2024
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GF-R
Data delivery date
Mar 14, 2025
Finance
Total approved costs
2,442 thou. CZK
Public financial support
2,442 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
2 442 CZK thou.
Public support
2 442 CZK thou.
0%
Provider
Czech Science Foundation
OECD FORD
Applied mathematics
Solution period
01. 10. 2022 - 31. 12. 2025