Eun Jung Kim ; Arnaud de Mesmay ; Tillmann Miltzow - Representing Matroids over the Reals is $\exists \mathbb R$-complete

dmtcs:10810 - Discrete Mathematics & Theoretical Computer Science, August 20, 2024, vol. 26:2 - https://doi.org/10.46298/dmtcs.10810
Representing Matroids over the Reals is $\exists \mathbb R$-completeArticle

Authors: Eunjung Kim ; Arnaud de Mesmay ; Tillmann Miltzow

    A matroid $M$ is an ordered pair $(E,I)$, where $E$ is a finite set called the ground set and a collection $I\subset 2^{E}$ called the independent sets which satisfy the conditions: (i) $\emptyset \in I$, (ii) $I'\subset I \in I$ implies $I'\in I$, and (iii) $I_1,I_2 \in I$ and $|I_1| < |I_2|$ implies that there is an $e\in I_2$ such that $I_1\cup \{e\} \in I$. The rank $rank(M)$ of a matroid $M$ is the maximum size of an independent set. We say that a matroid $M=(E,I)$ is representable over the reals if there is a map $\varphi \colon E \rightarrow \mathbb{R}^{rank(M)}$ such that $I\in I$ if and only if $\varphi(I)$ forms a linearly independent set. We study the problem of matroid realizability over the reals. Given a matroid $M$, we ask whether there is a set of points in the Euclidean space representing $M$. We show that matroid realizability is $\exists \mathbb R$-complete, already for matroids of rank 3. The complexity class $\exists \mathbb R$ can be defined as the family of algorithmic problems that is polynomial-time is equivalent to determining if a multivariate polynomial with integers coefficients has a real root. Our methods are similar to previous methods from the literature. Yet, the result itself was never pointed out and there is no proof readily available in the language of computer science.


    Volume: vol. 26:2
    Section: Discrete Algorithms
    Published on: August 20, 2024
    Accepted on: May 13, 2024
    Submitted on: January 14, 2023
    Keywords: Computer Science - Computational Complexity,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 108 times.
    This article's PDF has been downloaded 71 times.