Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with matroid-theory
Search options not deleted
user 2233
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.
40
votes
What are the external triumphs of matroid theory?
Here is an example from polyhedral theory. A matrix $A \in \mathbb{R}^{n \times m}$ is totally unimodular, if every square submatrix of $A$ has determinant $1, -1,$ or $0$. Totally unimodular matric …
- 32.1k
20
votes
Menger's theorem via matroids
There is indeed a Menger's theorem for matroids first proven by Tutte. The reference is
Tutte, W. T., Menger’s theorem for matroids, Journal of Research of the National
Bureau of Standards—B. M …
- 32.1k
18
votes
Accepted
Category theoretic interpretation of matroids?
If I understand your question correctly, I believe that the problem is still open. That is, if we let $\mathcal{M}$ be the category of (simple) matroids, where the morphism are given by strong maps, t …
- 32.1k
17
votes
1
answer
1k
views
Is there a Sudoku matroid?
This question is inspired from this one, where it is asked what is the minimum number of checks needed to verify that a Sudoku solution is correct. Let
$$
E=\{r_1, \dots, r_9\} \cup \{c_1, \dots, c …
- 32.1k
12
votes
Accepted
Good introductory text book on Matroid Theory?
My first recommendation would be Oxley's Matroid Theory. The second edition was just released this year (19 years after the original), so this is a very 'modern' textbook.
Another option would be We …
- 32.1k
11
votes
Accepted
Representability of matroids over $\mathbb R$
This does not technically answer your question, but I think it may of interest to you, so bear with me. If you are interested in excluded-minor characterizations for real-representability, the situat …
- 32.1k
11
votes
Accepted
Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?
Yes. This is one of the results of the Matroid Minors Project of Geelen, Gerards and Whittle as part of their proof of Rota's Conjecture. In fact, they prove that for any finite abelian group $\Gamm …
- 32.1k
10
votes
Accepted
Is there a Sudoku matroid?
By some sort of strange mathematical cosmic entanglement, it appears that François Brunault answered his own question in the other thread while I was writing this question.
The answer is indeed ye …
9
votes
Accepted
A minimum set hitting every base of a matroid
The problem is hard in general. Note that a minimal set that intersects every base of a matroid $M$ is a dependent set in the dual matroid $M^{*}$. Such sets are called cocircuits. So, you are look …
- 32.1k
8
votes
Accepted
Does this matroid have a name?
Matrices that contain at most two non-zero entries per column are called frame matrices. The matroids representable by frame matrices (over a finite field $\mathbb{F}$) are in fact a fundamental clas …
- 32.1k
7
votes
Accepted
Minimum number of independent pairs in a matroid
As observed by Geva Yashfe, the answer is $2^n$. This can be achieved when each of $A$ and $\overline{A}:=E\setminus A$ are bases, with $A = \{a_1,\ldots,a_n\}$, $\overline{A} = \{b_1,\ldots,b_n\}$, a …
- 32.1k
6
votes
Accepted
Does the purported proof of Rota's conjecture provide an algorithm for calculating the forbi...
As far as I understand, the purported proof does not give an algorithm that given a finite field $\mathbb{F}$, computes the excluded minors for $\mathbb{F}$-representability. This is because it relie …
- 32.1k
6
votes
Matroids of rank two
Up to simplification (suppressing loops and parallel elements), every rank two matroid is just a rank two uniform matroid.
Note that the vectors $(1, a_1), \dots, (1, a_n)$ represent the uniform ma …
- 32.1k
6
votes
What upper bounds are known on the number of non-isomorphic cycle matroids?
There are $2^{\binom{n}{2}}$ labelled graphs on $n$ vertices. Since isomorphic graphs have isomorphic graphic matroids, $c_n$ is at most the number of non-isomorphic graphs on $n$ vertices (see OEIS …
- 32.1k
6
votes
Book for matroid polytopes
Matroid polytopes are a standard topic in the field of combinatorial optimization, and as such I would recommend the beautiful text Combinatorial Optimization - Polyhedra and Efficiency by Lex Schrijv …
- 32.1k