Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial Resultants in the Algebraic Rigidity Matroid
109
0
0.0
(
0
)
Added by
Goran Malic
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid associated to the Cayley-Menger ideal for $n$ points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from $K_4$ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.
rate research
Read More
A bar-joint framework $(G,p)$ in $mathbb{R}^d$ is rigid if the only edge-length preserving continuous motions of the vertices arise from isometries of $mathbb{R}^d$. It is known that, when $(G,p)$ is generic, its rigidity depends only on the underlying graph $G$, and is determined by the rank of the edge set of $G$ in the generic $d$-dimensional rigidity matroid $mathcal{R}_d$. Complete combinatorial descriptions of the rank function of this matroid are known when $d=1,2$, and imply that all circuits in $mathcal{R}_d$ are generically rigid in $mathbb{R}^d$ when $d=1,2$. Determining the rank function of $mathcal{R}_d$ is a long standing open problem when $dgeq 3$, and the existence of non-rigid circuits in $mathcal{R}_d$ for $dgeq 3$ is a major contributing factor to why this problem is so difficult. We begin a study of non-rigid circuits by characterising the non-rigid circuits in $mathcal{R}_d$ which have at most $d+6$ vertices.
We study conditional independence (CI) models in statistical theory, in the case of discrete random variables, from the point of view of algebraic geometry and matroid theory. Any CI model with hidden random variables corresponds to a variety defined by certain determinantal conditions on a matrix whose entries are probabilities of events involving the observed random variables. We show that any CI variety, and more generally any hypergraph variety, admits a matroid stratification. Our main motivation for studying decompositions of CI varieties is the realizability problem: given a collection of CI relations, the goal is to determine the existence of random variables that satisfy these constraints and violates the rest. We show that the realization spaces of CI models and the matroid varieties in their decompositions are closely related. We use ideas from incidence geometry, in particular point and line configurations, to find minimal decompositions of general hypergraph varieties in terms of matroid varieties, which are not necessarily irreducible by Mnev--Sturmfels universality theorem, and may have arbitrary singularities. We focus on various families of hypergraph varieties for which we explicitly compute an irredundant irreducible decomposition. Our main findings in this direction are threefold: (1) we describe minimal matroids of such hypergraphs; (2) we prove that the varieties of these matroids are irreducible and their union is the hypergraph variety; and (3) we show that every such matroid is realizable over real numbers. Our decomposition strategy gives immediate matroid interpretations of the irreducible components of many families of CI varieties in algebraic statistics, and unravels the symmetric structures in CI varieties which hugely simplifies the computations.
The Neighbor-Joining algorithm is a popular distance-based phylogenetic method that computes a tree metric from a dissimilarity map arising from biological data. Realizing dissimilarity maps as points in Euclidean space, the algorithm partitions the input space into polyhedral regions indexed by the combinatorial type of the trees returned. A full combinatorial description of these regions has not been found yet; different sequences of Neighbor-Joining agglomeration events can produce the same combinatorial tree, therefore associating multiple geometric regions to the same algorithmic output. We resolve this confusion by defining agglomeration orders on trees, leading to a bijection between distinct regions of the output space and weighted Motzkin paths. As a result, we give a formula for the number of polyhedral regions depending only on the number of taxa. We conclude with a computational comparison between these polyhedral regions, to unveil biases introduced in any implementation of the algorithm.
We show Kantors conjecture (1974) holds in rank 4. This proves both the sticky matroid conjecture of Poljak and Turzik (1982) and the whole Kantors conjecture, due to an argument of Bachem, Kern, and Bonin, and an equivalence argument of Hochstattler and Wilhelmi, respectively.
We showed in the first paper of this series that the generic $C_2^1$-cofactor matroid is the unique maximal abstract $3$-rigidity matroid. In this paper we obtain a combinatorial characterization of independence in this matroid. This solves the cofactor counterpart of the combinatorial characterization problem for the rigidity of generic 3-dimensional bar-joint frameworks. We use our characterization to verify that the counterparts of conjectures of Dress (on the rank function) and Lov{a}sz and Yemini (which suggested a sufficient connectivity condition for rigidity) hold for this matroid.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
