Questions tagged [matroids]
Matroids are a common generalization of linearly independent sets and independent sets in graphs. Among other applications, they are exactly the simplical complexes in which the greedy algorithm outputs the optimal solution. Matroids are also studied for their own sake.
339
questions
0
votes
0
answers
36
views
Can we have a regular matroid $U_{1,2}$?
Here is the definition of a regular matroid:
Here is the definition of regular:
A regular matroid is one that can be represented by a totally unimodular matrix. And a totally unimodular matrix is a ...
- 1,835
0
votes
1
answer
26
views
Characterizing paving matroids in terms of their bases.
Here is the question I am trying to solve:
Characterize paving matroids in terms of their collections of independent sets and in terms of their collection of bases.
What exactly does it mean to ...
- 1,835
0
votes
0
answers
52
views
Examples\ Non-examples on Prop. 1.3.10 in James Oxley, Matroid Theory, second edition.
Here is the Proposition:
Let $\mathcal{D}$ be a collection of non-empty subsets of a set $E.$ Then $\mathcal{D}$ is the set of circuits of a paving matroid on $E$ iff there are a positive integer $k$ ...
- 1,217
1
vote
1
answer
82
views
Proving $r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$
Here is the question I am trying to prove the inequality below of part $(a)$ in it:
$$r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$$
Let $M$ be a matroid on a set $E$ and $k$ be ...
- 1,217
0
votes
0
answers
30
views
what is the difference in adjacency matrix between $GF(2)$ and $GF(3)$?
Here is the question I am trying to solve:
Let $G$ be the graph obtained from $K_5$ by deleting two non-adjacent edges. Find representations for $M(G)$ over $GF(2)$ and $GF(3).$
My attempt:
I wrote ...
- 1,835
1
vote
1
answer
90
views
why So $C_4 \subseteq C_2$?
Here is the question I am trying to understand its solution:
Let $C_1$ and $C_2$ be circuits of a matroid $M$ such that $C_1 \cup C_2 = E(M)$ and $C_1 - C_2 = \{e\}.$ Prove that if $C_3$ is a circuit ...
- 1,835
0
votes
0
answers
89
views
How to show that $M_2[A]$ is graphic but $M_3[A]$ is not?
Here is the question I am trying to solve letter $(b)$ in it:
Let $A$ be the matrix $\begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 &...
- 1,835
1
vote
0
answers
36
views
what is the quickest way of finding the set of all linearly independent sets over GF(2) and GF(3)?
Here is the question I am trying to solve (note that in the textbook the columns are numbered from 1 to 6):
Let $A$ be the matrix $\begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0\\
0 & 1 ...
- 1,835
1
vote
1
answer
78
views
A matroid with zero Euler characteristic has an isthmus
Let $M$ be a rank $r$ matroid on the ground set $E$. $e\in E$ is said to be an isthmus of $M$ if $e$ is contained in every base of $M$. We also define the Euler characteristic of $M$ to be
$$\chi(M)=\...
- 310
0
votes
0
answers
44
views
A matroid that is graphic in characteristic 2 but not in characteristic 3
Let $A$ be the matrix
$$A=\begin{pmatrix}1 & 0 & 0 & 1 & 1 & 0 \\ 0& 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1\end{pmatrix}$$
in the field $...
- 3,522
0
votes
1
answer
37
views
Which quadrants can a codimension 3 subspace intersect?
I am given 3 linearly independent vectors $x,y,z \in \mathbb{R}^n$ and I would like to understand which quadrants the orthogonal complement of their span intersects (depending on the coefficients of $...
- 91
1
vote
1
answer
71
views
Are all non-Paving Matroids Linear Matroids? [closed]
A matroid is called a paving matroid if all circuits of the matroids are of cardinality $k$ or $k+1$, where $k$ is the rank of the matroid. A matroid $(E,I)$ is called a linear matroid if there is a ...
- 63
3
votes
0
answers
54
views
What kind of matroidal information is contained in the ratio of the Tutte polynomial and its dual?
Let $M$ be a matroid and $T(x,y)$ its Tutte polynomial. It is well-known that $T(y, x)$ is equal to the Tutte polynomial of the dual of $M$. What kind of matroidal information (if any) is contained in ...
0
votes
0
answers
42
views
Proof that all maximal independent sets of a matroid have the same cardinality
I'm trying to prove the following statement about some matroid $(X,\mathcal{I})$:
For every subset $Y\subseteq X$, all maximal independent sets contained in $\mathcal{I}$ have equal size.
Proof:
...
1
vote
1
answer
64
views
Can Sigma Algebras have a Matroid with independent sets defined as mutually independent?
Let ($\Omega$, $\mathcal{A}$, $\mathcal{p}$) be a probability space and consider the pair ($\mathcal{A}$, $\mathcal{I}$) with $\mathcal{I}$ $\subseteq$ $\mathcal{P}$($\mathcal{A}$) where for all $I$ $\...
0
votes
0
answers
64
views
Existence of family of binary vectors with certain spanning properties.
Given dimension $d$, can you construct a full-rank family of vectors $V \subseteq \mathbb F_2^d$, satisfying the following property?
If $U \subseteq V$ is an independent family of $\Omega(d)$ vectors,...
0
votes
1
answer
22
views
Why is $c(t_i) ≥ c(t_p)$ in this matroid theorem proof?
In the proof of theorem 5.2 here https://math.mit.edu/~goemans/18453S17/matroid-notes.pdf ,
Since $c(t_i) ≥ c(t_p) > c(s_p)$, ti should have been selected when it was considered
Why is $c(t_i) ≥ ...
- 101
0
votes
1
answer
26
views
Is there a name for a family of subsets which satisfies the finite matroid axioms and the ground set is infinite?
I know that finitary matroids are those which can have potentially infinite ground sets yet have an additional axiom regarding additional axiom. I was wondering if there are any widely used terms for ...
- 5,763
1
vote
2
answers
102
views
Independence complex of a prime ideal is a matroid
Let $k$ be a field and $I \subseteq k[x_1, \ldots, x_n]$ be an ideal.
Definition. A subset $ \underline{u} \subseteq \{ x_1, \ldots, x_n\} = \underline{x} $ of variables is independent modulo $I$ if $...
- 154
2
votes
0
answers
50
views
What's the smallest rank matroid in which a given collection of sets are all closed?
Let us suppose we have a finite ground set $E$ and a collection of sets $S_1, \ldots, S_m$ which we can assume without losing much generality is closed under intersection and we can
similarly assume ...
- 113
2
votes
1
answer
93
views
Why is this almost affine code not equivalent to a linear code?
I am a bachelor student who just started studying coding theory and I came across the following example in "Generalized Hamming weights for almost affine codes" by Johnsen and Verdure, page ...
0
votes
1
answer
37
views
Why matroid cannot have S in I?
I'm learning matroids for algorithm analysis. Definition of a matroid is as follows,
In terms of independence, a finite matroid M is a pair (E,I), where E is a finite set (called the ground set) and I ...
- 103
0
votes
0
answers
34
views
Algorithm to construct a graph with minimal spanning trees
I need an algorithm that constructs an undirected graph given all of its minimal spanning trees (bases of a matroid) to find circles in the underlying graph. Has anyone an idea how I can do that?
...
- 1
1
vote
1
answer
33
views
Why ground set of submodular function maximization is finite set?
There is famous statement for submodular function maximization by greedy algorithm, roughtly:
greedy submodular maximization algorithm is guaranteed to be
$(1-\frac{1}{e})$-optimal approximate ...
- 321
1
vote
1
answer
35
views
Seperating Spanning Tree inequalities and equivalence to rank function of the cycle matroid
The motivation of this post is to answer the question
How can I decide for a given graph $G = (V,E)$ and $x \in \mathbb{R}^E$ whether $\sum_{e \in E[X]}x_e \leq |X| -1$ for all non-empty $X \subseteq ...
- 177
1
vote
1
answer
33
views
Vector matroid with infinite ground set?
One type of matroid is called vector matroid which has finite ground set.
I am wondering is there a name for the following type of matroid, whose ground set is $\mathbb{R}^n$, and whose independent ...
- 1,821
0
votes
0
answers
32
views
Minors of matroids
I'm learning matroids for the first time, and I'm trying to prove two things:
For a graph $G$ and one of its edges $e$, $M(G-e)=M(G)-e$, and $M^\ast(G-e)=M^\ast(G)/e$ where $M$ is the cycle matroid ...
- 779
0
votes
0
answers
51
views
Oriented matroids: A map between chirotopes and the set of covectors?
I am just getting used to the topic of oriented matroids. I was surprised to read that a central aspect of oriented matroid theory is that there exists a "non-trivial equivalency" between ...
0
votes
0
answers
16
views
Graphical matroid with a mechanism design interpretation
What is the interpretation of a graphical matroid as a mechanism design problem?
Lucier's survey on prophet inequalities says:
"An illustrative example is the graphical
matroid: the buyers ...
- 1
0
votes
0
answers
28
views
How can I show that $X_1 \cup Y_2$ and $X_2 \cup Y_1$ are basis of $M$?
Let $M = (S, {\cal I})$ be a matroid. Let $B_1$ and $B_2$ basis of $M$. Let $ \{ X_1, Y_1 \} $ be the partition of $B_1$ (this is $X_1 \cap Y_1 = \emptyset$ and $B_1 = X_1 \cup Y_1$).
Let $M_1 = M/Y_1$...
- 113
2
votes
0
answers
54
views
Monotonized Submodular Function with the Same Polymatroid
I am doing Exercise 8.10 (Submodular function minimization) of Introduction to Linear Optimization by Bertsimas and Tsitsiklis and may have found a mistake in (b).
Exercise 8.10* (Submodular function ...
- 629
0
votes
0
answers
90
views
Enumerate all possible sign patterns spanned by matrix column space
Given a $m \times n$ matrix $A$ with $m>n$, I would like to enumerate all possible sign patterns $w$ generated by $Av$ for all $v \in \mathbb{R}^n$. More specifically, if $(Av)_i \geq 0$ then $w_i =...
- 585
2
votes
1
answer
77
views
Do "possible face sets" of planar graphs satisfy the exchange property?
Given a finite planar graph $\mathfrak{G}=(V,E)$, let $Cyc(\mathfrak{G})$ be the set of all cycles in $\mathfrak{G}$. For each planar embedding $f$ of $G$, let $Face(f)$ be the subset of $Cyc(\...
- 236k
1
vote
0
answers
39
views
Bases and Matroids of a graph
I would appreciate some guidance regarding the concept of matroids in a graph.
I have the following graph: V = {1,2,3,4,5,6,7} with E = {(1,2),(1,3,(2,3),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7)}.
...
- 11
0
votes
1
answer
52
views
Please prove that $(S^{'},\mathcal{I}^{'})$ is a weighted matroid. ("Introduction to Algorithms 3rd Edition" by CLRS)
I am reading "Introduction to Algorithms 3rd Edition" by CLRS.
A matroid is an ordered pair $M=(S,\mathcal{I})$ satisfying the following conditions.
$S$ is a finite set.
$\mathcal{I}$ is a ...
- 8,410
2
votes
0
answers
22
views
How to find an uncommon base of two matroids
Let $M_1=(E,\mathcal{I}_1)$ and $M_2=(E,\mathcal{I}_2)$ be two matroids defined on the same ground set $E$ with independent sets $\mathcal{I}_1$ and $\mathcal{I}_2$ respectively. Suppose we can check ...
3
votes
0
answers
46
views
Does this knot collinearity condition have a nontrivial solution?
Recall that a link is an embedding of some number of circles in space up to isotopy. (Think "a knot but maybe multiple pieces.") Three oriented links form a skein triple if they have ...
- 21.7k
0
votes
0
answers
51
views
Can a math software do decide whether an abstract simplicial complex is or not a matroid?
As the title suggests, I need to know if there exists some math software deciding whether an abstract simplicial complex is or not a matroid. In other terms, I would like to give a finite ground set ...
- 4,839
1
vote
0
answers
59
views
connectivity of a matroid equal to its rank?
The connectivity $\eta(X)$ of a simplicial complex $X$ is defined as the
$$1+\min_j\{j \mid \tilde{H}_j(X)\neq 0\}$$
(see here for this definition.)
If $M$ is a matroid not having a co-loop (an ...
- 1,821
2
votes
0
answers
37
views
Orientation-compatible intersections
(Note: Cross posted on MO in https://mathoverflow.net/questions/426436/orientation-compatible-intersections since not clear what is a suitable platform)
This question is about clarifications on the ...
- 971
0
votes
1
answer
40
views
fractional coloring of a matroid
Given a matroid $M$, a fractional coloring $f$ is a function from the collection $I(M)$ of independent sets of $M$ to non-negative real numbers such that for any $v$ in the ground set,
$$\sum_{A\in I(...
- 1,821
1
vote
0
answers
26
views
Loop and Homotopical connectivity of simplicial complex
Let $M$ be a matroid and $x$ is a loop in it, which means $x$ is not in any independent set of $M$.
Then $M$ is also a simplicial complex (all its independent sets are faces).
Then I feel confused to ...
- 1,821
0
votes
0
answers
26
views
Matroid Theory Terminology - What is the name of independent sets which can be extended to be dependent but are not a superset of another such set?
Let $M=(I,E)$ be a matroid of ground set I and independent sets E.
I am now looking for a term for all those sets $X\subseteq I$ such that there exists an element $e$ which fulfills the following ...
- 1
0
votes
1
answer
47
views
Matroid: adding an arbitrary element?
Let $M$ be a matroid and $I\in M$. For any $x\not\in I$, it is true that there exists $y\in I$ such that $(I\setminus\{y\})\cup \{x\}\in M$?
If $I\cup\{x\}\in M$, then we know any subset of it is also ...
- 1,821
3
votes
1
answer
77
views
On category of matroids
In the paper
https://homepages.inf.ed.ac.uk/cheunen/publications/2015/matroids/matroids.pdf
the category of matroids and strong maps is defined and investigated. In Section 8, the authors take into ...
- 4,839
1
vote
1
answer
167
views
Why a matroid contracting to a subset is a matroid?
Let $M$ be a matroid and $X$ is a subset of the ground set of $M$.
Someone claims that
$$M.X:=\{\tau\subseteq X: \tau \cup \sigma \in M \text{ for all $\sigma\in M$ with $\sigma\cap X=\emptyset$}\}$$
...
- 1,821
2
votes
0
answers
70
views
Explicitly describe the cryptomorphism between greedoids and greedy set operators
A greedoid $\mathcal{F}$ on a finite ground set $E$ is cryptomorphic to an operator $\sigma$ (usually - and improperly - called the closure operator of the greedoid) such that:
$X \subseteq \sigma(X)$...
- 4,839
2
votes
1
answer
90
views
Property of circuits of a matroid made up of two circuits that differ by one element
Exercise 5 in section 1.1. of Oxley's Matroid Theory (1992) says:
Let $C_1$ and $C_2$ be circuits of a matroid $M$ such that $C_1 \cup C_2 = E(M)$ and $C_1 \setminus C_2 = \{e\}$. Prove that if $C_3$ ...
- 1,511
0
votes
1
answer
62
views
Extending $A$ by $x \in B\setminus A$
If I have:
matching $M$ which matches all vertices of $A$
matching $M'$ which matches all vertices of $B$
Where $|A| < |B|$
and $A$ and $B$ are two independent sets
I created a subgraph of the ...
0
votes
0
answers
40
views
(proof clarification) - ( E, $\mathscr{F}_G$) is a matroid
I'm having trouble understanding why we make the assumption in the highlighted part of the proof, any help would be appreciate, thanks.
Proposition. $\forall G = (V,E)$ undirected graph, the pair $(E,...
- 728