Combinatorial rigidity and its applications  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
81472
Type K
Principal investigator Jordán, Tibor
Title in Hungarian Kombinatorikus merevség és alkalmazásai
Title in English Combinatorial rigidity and its applications
Keywords in Hungarian merev szerkezet, gráf, matroid, globális merevség
Keywords in English rigid framework, graph, matroid, global rigidity
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Starting date 2010-04-01
Closing date 2015-09-30
Funding (in million HUF) 4.000
FTE (full time equivalent) 2.09
state closed project
Summary in Hungarian
Struktúrák merevségének és flexibilitásának vizsgálata
izgalmas kutatási terület a geometria, az algebra és a
kombinatorika határán. A terület iránti érdeklődés és az új
eredmények száma rohamosan nő az 1970-es évek óta, köszönhetően
egyrészt Laman fontos eredményének, amelyben jellemezte a síkbeli
generikusan merev rúd-csukló szerkezeteket, másrészt az alkalmazások
növekvő számának. Szerkezetek segítségével számos struktúra
merevsége, szilárdsága, vagy éppen flexibilitása jól modellezhető,
ezáltal a terület eredményei alkalmazhatók többek között
a statikában, molekuláris biológiában, drótnélküli szenzor
hálózatokra, CAD feladatokban, kontrol elméletben, továbbá
a diszkrét geometria más ágaiban.

A kombinatorikus merevség, amely a kutatási projekt témája,
a merevség elméletének azon részét takarja, amely azon eredményekkel
és kérdésekkel foglalkozik, amelyekben a szerkezetek kombinatorikus
tulajdonságai a döntőek és ahol hatékony algoritmusok kidolgozása
is fontos. Ez a terület rendkívül aktívnak bizonyult az elmúlt 6-8
évben, és továbbra is nő. Ez köszönhető az új alkalmazásoknak és
annak is, hogy a terület néhány fontos és régóta nyitott kérdése nemrég megoldást
nyert. A kutatás fő célja a merev szerkezetek elméletéhez és annak
alkalmazásaihoz való hozzájárulás új matematikai eredményekkel
és algoritmusokkal a kombinatorikus merevség területén.
Summary
Rigidity and flexibility of structures is
an exciting research area in the intersection of
geometry, algebra, and combinatorics.
Interest and developments in
rigidity have increased rapidly since the 1970's, motivated initially by
the combinatorial
characterization of rigid two-dimensional generic bar-and-joint frameworks
by Laman in 1970 and also by the increasing number of applications.
One can use frameworks to model the robustness or
flexibility of several structures, which
leads to a wide range of applications in engineering,
molecular biology, wireless sensor networks, CAD,
control theory, and in other parts of discrete geometry.

Combinatorial rigidity, the focus of this research project,
refers to the part of rigidity theory
which is concerned with those results and problems where
the underlying combinatorial structure of
the frameworks plays a key role and where efficient algorithms
are needed. This area has been extremely active in the past 6-8 years and
it is still expanding. This is due to the new applications as well as
to the fact that several long-standing open questions have recently been
solved. The main goal of this research project is to contribute to rigidity
theory and its applications by new mathematical results and algorithms
in combinatorial rigidity.




 

Final report

  
Results in Hungarian
A kombinatorikus merevségi vizsgálatok célja (absztrakt) rúdszerkezetek merevségi tulajdonságainak meghatározása gráf- és matroidelméleti módszerekkel. A terület eredményei alkalmazhatók pl. mérnöki tudományokban, a molekuláris biológiában, szenzorhálózatok lokalizációs problémáiban, alakzatok irányításában. A pályázat támogatásával elért közel 20 tudományos eredmény különféle szerkezetek merevségi és globális merevségi tulajdonságait jellemzi, valamint ezen tulajdonságok tesztelésére hatékony algoritmusokat ad. Többek között pontos kombinatorikus jellemzést sikerült adni tetszőleges dimenzióban a generikusan globálisan merev test-rúd és test-zsanér szerkezetekre. A merevséghez kapcsolódó módszerek mátrix kiegészítési feladatok megoldására is jól alkalmazhatónak bizonyultak.
Results in English
Combinatorial rigidity is about analysing the rigidity properties of (abstract) bar-and-joint frameworks by using graph and matroid theoretic methods. The results of this field are applicable in engineering, molecular biology, localization problems of sensor networks, formation control, and elsewhere. Each of the cca. 20 new results, obtained with the support of this research grant, is concerned with rigidity and global rigidity properties of various frameworks and provides efficient algorithms for testing these properties. Among other results we could give an exact combinatorial characterization of the generically globally rigid body-bar and body-hinge frameworks, in all dimensions. The techniques from rigidity theory turned out to be useful also in the solutions of some matrix completion problems.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=81472
Decision
Yes





 

List of publications

  
Z. Fekete, T. Jordán, V.E. Kaszanitzky: Rigid realizations of graphs with two coincident points, Graphs and Combinatorics, Vol. 31, Issue 3, pp 585-599, 2015
T. Jordán, V-H. Nguyen: On universally rigid frameworks on the line, Contributions to Discrete Mathematics, to appear, 2015
B. Jackson, T. Jordán, Z. Szabadka,: Globally linked pairs of vertices in rigid frameworks, Rigidity and Symmetry (R. Connelly, W. Whiteley and Asia Weiss, eds.), Fields Institute Communications, 70, pp. 177-203, 2014
T. Jordán: Combinatorial rigidity: graphs and matroids in the theory of rigid frameworks, Memoirs of the Japanese Math. Soc., to appear, 2015
T. Jordán, V.E. Kaszanitzky: Sparse hypergraphs with applications in combinatorial rigidity, Discrete Appl. Math., Vol. 185, pp. 93-101, 2015
B. Jackson, T. Jordán, S. Tanigawa: Combinatorial conditions for the unique completability of low rank matrices, SIAM J. Discrete Math. 28-4, pp. 1797-1819, 2014
T. Jordán, C. Király, S. Tanigawa: Generic global rigidity of body-hinge frameworks, MTA-ELTE Egerváry Research Group, Technical report, TR-2014-06, 2014
B. Jackson, T. Jordán, S. Tanigawa: Unique low rank completability of partially filled matrices, MTA-ELTE Egerváry Research Group, Technical report, TR-2015-08, 2015
B. Jackson, T. Jordán, B. Servatius, H. Servatius: Henneberg moves on mechanisms, Beitr. Algebra Geom., vol. 56, 2, pp. 587-591, 2015
T. Jordán: Generically globally rigid zeolites in the plane, Information Processing Letters, Vol. 110, Issues 18-19, Pages 841-844., 2010
B. Jackson, T. Jordán: Operations preserving global rigidity of generic direction-length frameworks, International Journal on Computational Geometry and Applications, Volume 20, Number 6, pp. 685-706., 2010
T. Jordán, V.E. Kaszanitzky,: Highly connected rigidity matroids have unique underlying graphs,, European J. Combinatorics, Volume 34, Issue 2, pp. 240--247., 2013
T. Jordán: Highly connected molecular graphs are rigid in three dimensions, Information Proc. Letters, Vol. 112, pp. 356-359., 2012
Z. Fekete, T. Jordán, V.E. Kaszanitzky: Rigid realizations of graphs with two coincident points, Proc. 7th Hungarian Japanese symposium on discrete mathematics and its applications, Kyoto, 2011
T. Jordán, G. Domokos, K. Tóth: Geometric sensitivity of rigid graphs, 7th Hungarian Japanese symposium on discrete mathematics and its applications, Kyoto, 2011
T. Jordán, V.E. Kaszanitzky: On generically affinely rigid hypergraphs, 7th Hungarian Japanese symposium on discrete mathematics and its applications, Kyoto, 2011
T. Jordán, V. Kaszanitzky, S. Tanigawa,: Gain-sparsity and symmetry-forced rigidity in the plane, MTA-ELTE Egerváry Research Group, Technical report, TR-2012-17., 2012
T. Jordán, V-H. Nguyen: On universally rigid frameworks on the line, Proc. 8th Hungarian Japanese symposium on discrete mathematics and its applications, to appear, 2013
B. Jackson, T. Jordán: Globally linked pairs and mechanisms, kézirat, 2012
B. Jackson, T. Jordán, Cs. Király,: Strongly rigid tensegrity frameworks on the line, Discrete Applied Mathematics, Volume 161, Issues 7–8, pp. 1147--1149., 2013
R. Connelly, T. Jordán, W. Whiteley,: Generic global rigidity of body-bar frameworks, J. Combinatorial Theory, Ser. B., accepted, 2013
J. Geleji, T. Jordán,: Robust tensegrity polygons, MTA-ELTE Egerváry Research Group, Technical report, TR-2012-15, 2012
B. Jackson, T. Jordán, Z. Szabadka,: Globally linked pairs of vertices in rigid frameworks, MTA-ELTE Egerváry Research Group, Technical report, TR-2012-19, 2012
Z. Fekete, T. Jordán, V.E. Kaszanitzky: Rigid realizations of graphs with two coincident points, Graphs and Combinatorics, in press, 2014
T. Jordán, G. Domokos, K. Tóth: Geometric sensitivity of rigid graphs, SIAM J. Discrete Math., vol. 27, No. 4, pp. 1710-1726., 2013
T. Jordán, V-H. Nguyen: On universally rigid frameworks on the line, Contributions to Discrete Mathematics, to appear, 2014
R. Connelly, T. Jordán, W. Whiteley,: Generic global rigidity of body-bar frameworks, J. Combinatorial Theory, Ser. B., Vol. 103, Issue 6, November 2013, pp. 689-705., 2013
J. Geleji, T. Jordán,: Robust tensegrity polygons, Discrete and Computational Geometry 50: 537-551 (2013)., 2013
B. Jackson, T. Jordán, Z. Szabadka,: Globally linked pairs of vertices in rigid frameworks, Rigidity and Symmetry (R. Connelly, W. Whiteley and Asia Weiss, eds.), Fields Institute Communications, in, 2014
T. Jordán: Combinatorial rigidity: graphs and matroids in the theory of rigid frameworks, Memoirs of the Japanese Math. Soc., to appear, 2014
T. Jordán, V.E. Kaszanitzky: Sparse hypergraphs with applications in combinatorial rigidity, MTA-ELTE Egerváry Research Group, Technical report, TR-2013-05, 2013
B. Jackson, T. Jordán, S. Tanigawa: Combinatorial conditions for the unique completability of low rank matrices, MTA-ELTE Egerváry Research Group, Technical report, TR-2014-01, 2014



Back »