Representing Matroids over the Reals is $\exists \mathbb R$-complete
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| &...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-08-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/10810/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344680756510720 |
|---|---|
| author | Eun Jung Kim Arnaud de Mesmay Tillmann Miltzow |
| author_facet | Eun Jung Kim Arnaud de Mesmay Tillmann Miltzow |
| author_sort | Eun Jung Kim |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-b7d8f1972a714d3bb745d56c9b0ce6f6 |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-08-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-b7d8f1972a714d3bb745d56c9b0ce6f62025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-08-01vol. 26:2Discrete Algorithms10.46298/dmtcs.1081010810Representing Matroids over the Reals is $\exists \mathbb R$-completeEun Jung KimArnaud de MesmayTillmann MiltzowA 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.http://dmtcs.episciences.org/10810/pdfcomputer science - computational complexitymathematics - combinatorics |
| spellingShingle | Eun Jung Kim Arnaud de Mesmay Tillmann Miltzow Representing Matroids over the Reals is $\exists \mathbb R$-complete Discrete Mathematics & Theoretical Computer Science computer science - computational complexity mathematics - combinatorics |
| title | Representing Matroids over the Reals is $\exists \mathbb R$-complete |
| title_full | Representing Matroids over the Reals is $\exists \mathbb R$-complete |
| title_fullStr | Representing Matroids over the Reals is $\exists \mathbb R$-complete |
| title_full_unstemmed | Representing Matroids over the Reals is $\exists \mathbb R$-complete |
| title_short | Representing Matroids over the Reals is $\exists \mathbb R$-complete |
| title_sort | representing matroids over the reals is exists mathbb r complete |
| topic | computer science - computational complexity mathematics - combinatorics |
| url | http://dmtcs.episciences.org/10810/pdf |
| work_keys_str_mv | AT eunjungkim representingmatroidsovertherealsisexistsmathbbrcomplete AT arnauddemesmay representingmatroidsovertherealsisexistsmathbbrcomplete AT tillmannmiltzow representingmatroidsovertherealsisexistsmathbbrcomplete |