Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Does it move?: euclidean and projective rigidity of hypergraphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. (Diskret matematik, Geometri)
2025 (English)Doctoral thesis, comprehensive summary (Other academic)Alternative title
Rör den sig? : euklidisk och projektiv stelhet av hypergrafer (Swedish)
Abstract [en]

Rigidity theory is the mathematical study of rigidity and flexibility of discrete structures. Rigidity theory, and the related field of kinematics, have a wide range of applications to fields such as material science, robotics, architecture, and computer aided design.

In rigidity theory, rigidity and flexibility are often studied as properties of an underlying combinatorial object. In this thesis, the aim is to study rigidity theoretic problems where the underlying combinatorial object is an incidence geometry. Firstly, we study rigidity problems for realisations of incidence geometries of rank 2 as points and straight lines in the plane. Finding realisations of incidence geometries as points and straight lines in the plane is an interesting problem in its own right that can be formulated as a problem of realisability of rank 3 matroids over the real numbers.

We study motions of rod configurations, which are realisations of incidence geometries as points and straight line segments in the plane, where each line segment is treated as a rigid rod. Specifically, motions of a rod configuration preserve the distance between any two points on a rod. We introduce and investigate a new notion of minimal rigidity for rod configurations. We also prove that rigidity of a rod configuration is equivalent to rigidity of a graph, under certain geometric conditions on the rod configuration. We also find realisations of v3-configurations that are flexible as rod configurations for ν ≥ 28. We show that all regularrealisations of v3-configurations for v ≤ 15, and triangle-free v3-configurations for v ≤ 20 are rigid as rod configurations.

We also consider motions of realisations of incidence geometries as points and straight lines in the plane which preserve only incidences between points and lines. We introduce the notion of projective motions, which are motions of realisations of incidence geometries as points and straight lines in the projective plane which preserve incidences. Furthermore, we introduce the basic tools for investigating rigidity with respectto projective motions. We also investigate the relationship between projective rigidity and higher-order projective rigidity.

Finally, we introduce a sparsity condition on graded posets, and introduce an algorithm which can determine whether a given graded poset satisfies the sparsity condition. We also show that sparsity conditions define a greedoid.

Place, publisher, year, edition, pages
Umeå: Umeå University, 2025. , p. 28
Series
Research report in mathematics, ISSN 1653-0810 ; 79/25
Keywords [en]
Rigidity, configurations, matroids, projective geometry
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-238259ISBN: 978-91-8070-700-8 (print)ISBN: 978-91-8070-701-5 (electronic)OAI: oai:DiVA.org:umu-238259DiVA, id: diva2:1954887
Public defence
2025-05-27, UB.A.220, Samhällsvetarhuset, Umeå, 13:00 (English)
Opponent
Supervisors
Available from: 2025-05-06 Created: 2025-04-28 Last updated: 2025-04-30Bibliographically approved
List of papers
1. Exploring the rigidity of planar configurations of points and rods
Open this publication in new window or tab >>Exploring the rigidity of planar configurations of points and rods
2023 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 336, p. 68-82Article in journal (Refereed) Published
Abstract [en]

In this article we explore the rigidity of realizations of incidence geometries consisting of points and rigid rods: rod configurations. We survey previous results on the rigidity of structures that are related to rod configurations, discuss how to find realizations of incidence geometries as rod configurations, and how this relates to the 2-plane matroid. We also derive further sufficient conditions for the minimal rigidity of k-uniform rod configurations and give an example of an infinite family of minimally rigid 3-uniform rod configurations failing the same conditions. Finally, we construct v3-configurations that are flexible in the plane, and show that there are flexible v3-configurations for all sufficiently large values of v.

Place, publisher, year, edition, pages
Elsevier, 2023
Keywords
Combinatorial rigidity, Incidence geometry, Rod configuration
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-208092 (URN)10.1016/j.dam.2023.03.030 (DOI)000983170400001 ()2-s2.0-85153509834 (Scopus ID)
Funder
Knut and Alice Wallenberg Foundation, 2020.0001Knut and Alice Wallenberg Foundation, 2020.0007
Available from: 2023-05-09 Created: 2023-05-09 Last updated: 2025-04-28Bibliographically approved
2. When is a planar rod configuration infinitesimally rigid?
Open this publication in new window or tab >>When is a planar rod configuration infinitesimally rigid?
2025 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 73, no 1, p. 25-48Article in journal (Refereed) Published
Abstract [en]

We investigate the rigidity properties of rod configurations. Rod configurations are realizations of rank two incidence geometries as points (joints) and straight lines (rods) in the Euclidean plane, such that the lines move as rigid bodies, connected at the points. Note that not all incidence geometries have such realizations. We show that under the assumptions that the rod configuration exists and is sufficiently generic, its infinitesimal rigidity is equivalent to the infinitesimal rigidity of generic frameworks of the graph defined by replacing each rod by a cone over its point set. To put this into context, the molecular conjecture states that the infinitesimal rigidity of rod configurations realizing 2-regular hypergraphs is determined by the rigidity of generic body and hinge frameworks realizing the same hypergraph. This conjecture was proven by Jackson and Jordán in the plane, and by Katoh and Tanigawa in arbitrary dimension. Whiteley proved a version of the molecular conjecture for hypergraphs of arbitrary degree that have realizations as independent body and joint frameworks. Our result extends his result to hypergraphs that do not necessarily have realizations as independent body and joint frameworks, under the assumptions listed above.

Place, publisher, year, edition, pages
Springer Nature, 2025
Keywords
Combinatorial rigidity, Hypergraphs, Incidence geometries, Parallel redrawings, Rod configurations
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-218895 (URN)10.1007/s00454-023-00617-7 (DOI)001126462800001 ()2-s2.0-85180169240 (Scopus ID)
Funder
Knut and Alice Wallenberg Foundation, 2020.0001Knut and Alice Wallenberg Foundation, 2020.0007
Available from: 2024-01-04 Created: 2024-01-04 Last updated: 2025-04-28Bibliographically approved
3. Projective rigidity of point-line configurations in the plane
Open this publication in new window or tab >>Projective rigidity of point-line configurations in the plane
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper, we establish a general setup for studying incidence-preserving motions of projective geometric configurations of points and lines via a "projective rigidity matrix". The spaces of infinitesimal motions of a point-line configuration and dependencies amongst the point-line incidences can be interpreted as the kernel and co-kernel of this projective rigidity matrix, respectively. We also introduce a symmetry-adapted projective rigidity matrix for analysing symmetric configurations and their symmetry-preserving motions. The symmetry may be a point group or a more general symmetry, such as an autopolarity. 

National Category
Geometry
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-238184 (URN)10.48550/arXiv.2407.17836 (DOI)
Funder
Knut and Alice Wallenberg Foundation, 2020.0001Knut and Alice Wallenberg Foundation, 2020.0007
Note

The Fields Institute for Research in Mathematical Sciences provided financial support to several of the authors during the project

Available from: 2025-04-25 Created: 2025-04-25 Last updated: 2025-04-28Bibliographically approved
4. Counting for rigidity under projective transformations in the plane
Open this publication in new window or tab >>Counting for rigidity under projective transformations in the plane
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Let P be a set of points and L a set of lines in the (extended) Euclidean plane, and I⊆P×L, where i=(p,l)∈I means that point p and line l are incident. The incidences can be interpreted as quadratic constraints on the homogeneous coordinates of the points and lines. We study the space of incidence preserving motions of the given incidence structure by linearizing the system of quadratic equations. The Jacobian of the quadratic system, our projective rigidity matrix, leads to the notion of independence/dependence of incidences. Column dependencies correspond to infinitesimal motions. Row dependencies or self-stresses allow for new interpretations of classical geometric incidence theorems. We show that self-stresses are characterized by a 3-fold balance. As expected, infinitesimal (first order) projective rigidity as well as second order projective rigidity imply projective rigidity but not conversely. Several open problems and possible generalizations are indicated. 

National Category
Geometry
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-238185 (URN)10.48550/arXiv.2503.07228 (DOI)
Funder
Knut and Alice Wallenberg Foundation, 2020.0001Knut and Alice Wallenberg Foundation, 2020.0007
Note

The Fields Institute for Research in Mathematical Sciences provided financial support to several of the authors.

Available from: 2025-04-25 Created: 2025-04-25 Last updated: 2025-04-29Bibliographically approved
5. Sparse posets and pebble game algorithms
Open this publication in new window or tab >>Sparse posets and pebble game algorithms
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We generalize a sparsity condition for hypergraphs and show a result5relating sparseness of hypergraphs to the decomposition of a modified6incidence graph into edge-disjoint forests. We also give new sparsity con-7ditions for posets and define an algorithm of pebble game type for posets8to test when these sparsity conditions hold. Furthermore, we prove that9in certain cases, the sparsity conditions define a greedoid.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-238186 (URN)
Funder
Knut and Alice Wallenberg Foundation, 2020.0001Knut and Alice Wallenberg Foundation, 2020.0007The Kempe Foundations, SMK21-667 0074Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2025-04-25 Created: 2025-04-25 Last updated: 2025-04-29Bibliographically approved
6. Applying the pebble game algorithm to rod configurations
Open this publication in new window or tab >>Applying the pebble game algorithm to rod configurations
2023 (English)In: EuroCG 2023: Book of abstracts, 2023, article id 41Conference paper, Published paper (Refereed)
Abstract [en]

We present results on rigidity of structures of rigid rods connected in joints: rod configurations. The underlying combinatorial structure of a rod configuration is an incidence structure. Our aim is to find simple ways of determining which rod configurations admit non-trivial motions, using the underlying incidence structure.

Rigidity of graphs in the plane is well understood. Indeed, there is a polynomial time algorithm for deciding whether most realisations of a graph are rigid. One of the results presented here equates rigidity of sufficiently generic rod configurations to rigidity of a related graph. As a consequence, itis possible to determine the rigidity of rod configurations using the previously mentioned polynomial time algorithm. We use this to show that all v3-configurations on up to 15 points and all triangle-free v3-configurations on up to 20 points are rigid in regular position, if such a realisation exists. We also conjecture that the smallest v3-configuration that is flexible in regular position is a previously known 283-configuration. 

National Category
Discrete Mathematics Geometry
Identifiers
urn:nbn:se:umu:diva-215548 (URN)
Conference
The 39th European workshop on computational geometry (EuroCG 2023), Barcelona, Spain, March 29-31, 2023
Available from: 2023-10-22 Created: 2023-10-22 Last updated: 2025-04-28Bibliographically approved

Open Access in DiVA

fulltext(947 kB)35 downloads
File information
File name FULLTEXT01.pdfFile size 947 kBChecksum SHA-512
bde3c892ad7ab9169043b450c164244426550012b891b9b7115bc4cd6273a091c4bff9eeaff029b5fe74ad6fde6f4fde331fce8550fb5c22c8d99b364d41efb6
Type fulltextMimetype application/pdf
spikblad(234 kB)17 downloads
File information
File name SPIKBLAD01.pdfFile size 234 kBChecksum SHA-512
454228a5c5142e29cafacac3cfa2feab47f337bd8e900de52db7619fa49869be1b8deb41a83a0dea3ee4c628da1885ae2fdd95557075c38886ef846951067cdf
Type spikbladMimetype application/pdf

Search in DiVA

By author/editor
Lundqvist, Signe
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 35 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1814 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf