All Questions
10 questions
12
votes
3
answers
2k
views
Representability of matroids over $\mathbb R$
Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,...
- 25.5k
8
votes
2
answers
824
views
Matroids of rank two
I am interested in matroids of rank two and would like to understand how interesting/big this class of matroids is.
I know that the 2-uniform matroid on (k+2) elements is not representable over any ...
- 613
8
votes
1
answer
593
views
Representability of polymatroids over $GF(2)$
A polymatroid is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$,
2) $A \subset B$ implies $d(A) \leq d(B)$, and
3) $d(A \cap B) + d(A \cup B) \leq d(...
- 25.5k
5
votes
1
answer
410
views
Exchanges between independent sets of a matroid
Let $I, J$ be two bases of a matroid. For every $x$ in $I$, there is some $y$ in $J$ such that, if we exchange $x$ with $y$, then both resulting sets ($I \setminus x \cup y$ and $J \setminus y \cup x$)...
- 3,549
4
votes
0
answers
94
views
Totally Unimodular matrix edited from ordinary matrix
Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...
- 13.9k
2
votes
1
answer
251
views
Dimension of circuit space of a matroid
If $G$ is a graph with edge set $E$, let $W$ be the $\mathbb{Z}/2$-vector space generated by the elements of $E$. If $A = \{a_1, \dots, a_n\} \subset E$, let $\bar{A} = a_1 + \dots + a_n \in V$; then $...
- 95
1
vote
1
answer
221
views
How to find all minimal dependent sets of a set of vectors effectively?
In my research, I need to find the set of all minimal dependent sets of a given set of vectors. One method is to check every subset of the given set. But this method is very slow when the set of ...
- 6,201
1
vote
1
answer
227
views
Do the cycles containing a fixed edge generate the cycle space of a graph?
Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a basis of the ...
- 1,034
1
vote
0
answers
111
views
$r(M)$-subsets of a 3-connected matroid $M$
It is proved in Lowrance, Oxley, Semple, and Welsh - On properties of almost all matroids that almost all matroids are 3-connected asymptotically. Also, it is conjectured that almost all matroids are ...
- 429
0
votes
1
answer
91
views
Finite projective geometry and the Krasner hyperfield
The Krasner hyperfield is an algebraic structure of two operations on $K=\{0,1\}$ called $+\colon K\times K\to \mathcal{P}(K)$ and $\cdot\colon K\times K\to K$ with
$0+0=0$
$0+1=1+0=1$
$1+1=\{0,1\}$
...
- 10.4k