Deciding Connectivity in Symmetric Semi-Algebraic Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913738372677632 |
|---|---|
| author | Riener, Cordian. Schabert, Robin Vu, Thi Xuan |
| author_facet | Riener, Cordian. Schabert, Robin Vu, Thi Xuan |
| contents | A semi-algebraic set is a subset of $\mathbb{R}^n$ defined by a finite collection of polynomial equations and inequalities. In this paper, we investigate the problem of determining whether two points in such a set belong to the same connected component. We focus on the case where the defining equations and inequalities are invariant under the natural action of the symmetric group and where each polynomial has degree at most \( d \), with \( d < n \) (where \( n \) denotes the number of variables). Exploiting this symmetry, we develop and analyze algorithms for two key tasks. First, we present an algorithm that determines whether the orbits of two given points are connected. Second, we provide an algorithm that decides connectivity between arbitrary points in the set. Both algorithms run in polynomial time with respect to \( n \). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_12275 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deciding Connectivity in Symmetric Semi-Algebraic Sets Riener, Cordian. Schabert, Robin Vu, Thi Xuan Symbolic Computation Computational Geometry Algebraic Geometry A semi-algebraic set is a subset of $\mathbb{R}^n$ defined by a finite collection of polynomial equations and inequalities. In this paper, we investigate the problem of determining whether two points in such a set belong to the same connected component. We focus on the case where the defining equations and inequalities are invariant under the natural action of the symmetric group and where each polynomial has degree at most \( d \), with \( d < n \) (where \( n \) denotes the number of variables). Exploiting this symmetry, we develop and analyze algorithms for two key tasks. First, we present an algorithm that determines whether the orbits of two given points are connected. Second, we provide an algorithm that decides connectivity between arbitrary points in the set. Both algorithms run in polynomial time with respect to \( n \). |
| title | Deciding Connectivity in Symmetric Semi-Algebraic Sets |
| topic | Symbolic Computation Computational Geometry Algebraic Geometry |
| url | https://arxiv.org/abs/2503.12275 |