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.
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
3
votes
Checking if a matroid is binary(Detecting $U^2_4$ minor in a matroid)
This is actually implemented (as well as a host of other features) in the latest version of Sage. This is the culmination of 2 and a half years of hard work by Stefan van Zwam and Rudi Pendavingh, to …
- 32.1k
0
votes
Checking whether a set family forms a matroid.
Here's a probabilistic approach.
First check if your set family $\mathcal{I}$ is closed under taking subsets. If not, then it is not a matroid. Next assign a 'random' weight function $w: S \to \m …
- 32.1k
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
1
vote
Accepted
How to prove the local search algorithm can find the maximum weight independent set in a mat...
Let $I$ be the independent set of size $k$ returned by the local search algorithm. Thus, $c(J) \leq c(I)$ for every independent set $J$ of size $k$ such that $|I \Delta J|=2$. Towards a contradictio …
- 32.1k
3
votes
Is there a graph-theoretical proof of Tutte's theorem on matroids?
Your condition should say that the conflict graph is bipartite instead of non-planar.
Let me define the conflict graph more precisely and then give a proof. For a cycle $C$ of
$G$ a $C$-path is a pa …
- 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 …
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
5
votes
Accepted
Exchanges between independent sets of a matroid
No, not every matroid satisfies this property. For example, it is known to fail for the cycle matroid of $K_4$. The matroids that satisfy your property are called base orderable matroids. There are …
- 32.1k
5
votes
Accepted
When do the circuits of a matroid have a connected intersection graph?
This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph of circuits is disconnected if $M$ has two connected components which each …
- 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
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
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
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
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