All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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

  • R&D category

    ZV - Basic research

  • OECD FORD - main branch

    10102 - Applied mathematics

  • OECD FORD - secondary branch

  • OECD FORD - another secondary branch

  • BD - Information theory

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

Basic information

Recognised costs

2 442 CZK thou.

Public support

2 442 CZK thou.

100%


Provider

Czech Science Foundation

OECD FORD

Applied mathematics

Solution period

01. 10. 2022 - 31. 12. 2025