Questions tagged [matroid-theory]
Questions related to the field of Combinatorics called Matroid Theory. Relevant topics include matroids in Combinatorial Optimization, Lattice Theory, Algebraic Geometry, Polyhedral Theory, Rigidity, and Algorithms. For questions about Oriented Matroids, the oriented-matroids tag may be used.
184
questions
1
vote
0
answers
77
views
Is there an efficient algorithm for finding a fundamental cycle basis of a graph with the fewest odd cycles? Failing that, a hardness result on this?
I can think of a greedy algorithm:
Let $B$ be a fundamental cycle basis of graph $G$ induced by spanning tree (or forest) $T$
For $e\in T$, let $n_+(e)$ ($n_-(e)$) be the number of even (odd) cycles ...
- 33
4
votes
0
answers
113
views
Find necessary & sufficient conditions for two families of sets to have $m$ pairwise disjoint common partial transversals of given sizes
Let $S$ be a finite set, $I$ a finite index set, $\mathcal A=(A_i:i\in I)$ and $\mathcal B=(B_i:i\in I)$ families of subsets of $S$.
For $J\subseteq I$, let $A(J)$ denote $\bigcup_{j\in J} A_j$.
A ...
- 1,492
1
vote
0
answers
88
views
Reconstructing a matroid by its minors
Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. ...
- 11
5
votes
1
answer
127
views
The Salvetti complex of a non-realizable oriented matroid
Given a real hyperplane arrangement, the Salvetti complex of the associated oriented matroid is homotopy equivalent to the complement of the complexification of the arrangement. In particular, its ...
- 2,527
0
votes
0
answers
49
views
Weighted matroid intersection algorithm
From Combinatorial Optimization, Theory and Algorithms, Sixth Edition, 2018, by Bernhard Korte and Jens Vygen:
...
- 131
4
votes
1
answer
189
views
Lattice description of matroid duality
Apologies for this very basic question in matroid theory, but I could not find anything about it online after a bit of searching.
There is a well-known bijective correspondence ("cryptomorphism&...
- 23.1k
6
votes
0
answers
254
views
A matroid parity exchange property
As part of my research, I encountered the following problem. Let $M = (E,I)$ be a matroid and let $P = \{P_1,\ldots,P_n\}$ be a partition of $E$ into (disjoint) pairs. For $A \subseteq P$, we say that ...
- 93
1
vote
0
answers
59
views
Matroid for Laurent series
I am trying to find a matroid for profinite rings which are the inverse limit of their finite quotients, and whose linearly independent elements are of the form $L((t_1,\dots,t_n))$.
To set this up, ...
user30211
7
votes
2
answers
361
views
A generalized matroid exchange property
Let $(E,I)$ be a matroid, and let $A,B \in I$ be disjoint independent sets in the matroid. Moreover, let $B_1,\ldots, B_k$ be a partition of $B$. I could not decide if the following is always true. ...
- 93
9
votes
2
answers
570
views
Book for matroid polytopes
I have made a study of polytopes with the books of Ziegler and "Integer Programming" of Conforti, my main goal is to study matroid polytopes; to study matroids I have thought about the book &...
- 229
0
votes
0
answers
82
views
Establishing a matroid for higher local fields K/L((t₁,..,tₙ))
In the theory of matroids, the Cohen structure theorem and theorem on transcendence degree that each field is algebraic over a field of the form k(x₁,..., xₙ), as well as Noether normalization, fall ...
user30211
0
votes
0
answers
64
views
Constructive proof sought for a theorem of J. de Sousa related to Hall's Marriage Theorem
The following is the finite version of Theorem 7 in the article by J. de Sousa, "Disjoint Common Transversals," Combinatorial Mathematics and its Applications: Proceedings of a Conference ...
- 1,492
3
votes
1
answer
108
views
Does a matroid base polytope contain its circumcenter?
Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...
- 12.8k
6
votes
2
answers
263
views
"Minimal" connected matroids
I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...
- 3,503
1
vote
0
answers
46
views
Minimal matroid of rank r size n
We can define a partial order $\leq$ on loopless matroids, such that $M_1\leq M_2$ if $M_1$ and $M_2$ are on the same groundset and $B_1\subseteq B_2$, where $B_1$ and $B_2$ are the set of bases of $...
- 593