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.

Filter by
Sorted by
Tagged with
2
votes
0answers
41 views

Are edges of inclusion minimal connected supergraphs bases of a matroid?

My reasoning is for any non-connected graph $G=(V,E)$ we can define an equivalence $\sim$ on $V$ such that for all $a,b\in V$ we get $a\sim b$ iff there is an undirected walk from $a$ to $b$ in the ...
0
votes
1answer
24 views

Proving the independence of sets in the context of matroid over fields other than $\mathbb{R}$

I was going through the text Introduction to Algorithms by Cormen et. al. [CLRS] where I came across the following section about matroids. A matroid is an ordered pair $M = (S, \ell)$ satisfying the ...
1
vote
1answer
28 views

What is a 1-graphic matroid?

I came across the definition of a 1-graphic matroid as follows: The 1-graphic matroid: the set of edges that form a forest with at most one simple cycle. Isn't a forest supposed to have no cycles? ...
0
votes
1answer
30 views

Linear maps on vectors in general position

Let $V$ be a finite dimensional vector space over an infinite field $\mathbb{F}$, and let $v_1,\dots, v_n \in V$ be a collection of non-zero vectors for which $\dim \text{span}\{v_i, v_j\} =2$ for all ...
0
votes
1answer
21 views

Property of closure relation.

I am reading $\textit{On the Foundations of Combinatorial Theory II. Combinatorial Geometries}$. They give a definition. A closure relation on a set $S$ is a function $A\mapsto \bar{A}$ defined for ...
2
votes
0answers
26 views

Integer matrix behind a chromatic polynomial?

Any finite graph has a chromatic polynomial, whose value at $n$ is the number of colorings using $n$ different colors. Its polynomiality can be proven by induction. What intrigues me more is its ...
1
vote
0answers
58 views

Proof of laminar matroid

Let $S$ be a ground set, and $S$ be a laminar family of subsets of $S$, which means that for every two distinct subsets $A,B \in S$, we have either $A \subseteq B$ or $B \subseteq A$ or $A \cap B = \...
0
votes
1answer
42 views

Tutte–Grothendieck invariants and Tutte polynomial. Is this property even used in the proof?

I am using “Matroids: A Geometric Introduction” by Gordon and McNulty. On page 337, in Theorem 9.19 Tutte-Grothendieck invariants are defined. The theorem itself gives their description in terms of ...
1
vote
1answer
35 views

Different definitions of Incidence Matrix of a graph?

Recently, I have been trying to learn some graph theory and matroids. I read from one source that you can build a vector matroid $M[A]$ of a graph $G$, by letting $A$ be the incidence matrix, but the $...
0
votes
1answer
43 views

Prove that optimal set is unique

Prove that there is a unique optimal set in a weighted matroid M = (S, I, w), with distinct weights on elements from S.
1
vote
1answer
62 views

Step in proof regarding existence of bijection $\omega$ between two bases of matroid $A,B$ s.t. $(A - a) \cup \omega(a)$ is independent

I'm not really sure what the proper procedure for this kind of question is. I was looking at this post which gives an (in my opinion) incomplete proof of the statement in the question title. I follow ...
0
votes
1answer
30 views

How can I tell if this independence system forms a matroid?

Let $(V,E)$ be a graph and consider a system $f$ of subsets of $V$ with $U\in f \mbox{ and } \forall u,v\in U$ we have $(u,v)\notin E$. This, $(V,f)$ is trivially an independence system, but how can ...
1
vote
0answers
25 views

Postnikov's Lemma 16.3 in TOTAL POSITIVITY, GRASSMANNIANS, AND NETWORKS

Paper linked here: https://math.mit.edu/~apost/papers/tpgrass.pdf I'm having trouble parsing the proof of Lemma 16.3, perhaps because I only have first-principles-level familiarity with matroids. I ...
0
votes
1answer
77 views

Independence systems

Can someone give me a hint on this please, thanks! Let $(E, F)$ be an independence system. Set $A ⊆ E$ is called maximal F-independent if $A \in F$ and there is no A' ∈ F with A ⊆ A' and A != A'. Let ...
0
votes
0answers
24 views

Submodular Function Maximization and Contention Resolution Scheme

I am reading some papers related to contention resolution schemes (CR-schemes) for submodular function maximization. I would like to understand why they are useful. I am interested in maximizing a ...
0
votes
0answers
18 views

How is the characteristic polynomial of a matroid derived?

More specifically, I was wondering how the generating function $$p_{M_G}(\lambda) := \sum_{S \subseteq E}(-1)^{|S|}\lambda^{r(M)-r(S)}$$ and its relation to the chromatic polynomial $$\chi_G(\lambda) =...
0
votes
0answers
26 views

X is an hyperplane iff it is a maximal non spanning set

URGENT I'm trying to show that $X$ is an hyperplane iff it is a maximal non-spanning set. If I assume that $X$ is an hyperplane, I know that it must be of $rk(M)-1$ (with $M$ a matroid), so it follows ...
2
votes
1answer
50 views

Uniform and Transversal Matroid

I'm reading Oxley's book Matroid Theory, and I read something that is not trivial for me... The book says that every uniform matroid is also transversal, but I don't understand why! I know that a ...
0
votes
0answers
32 views

Open-ended: Upper-bounding $\dim \text{span}\{v_1,\dots,v_n\}$ in terms of $\dim \text{span}$ of subsets

I have also asked this question on Math Overflow. Let $S=\{v_1,\dots, v_n\} \subset V$ be a set of nonzero vectors in a vector space (we can take the field to be algebraically closed). It is easy to ...
1
vote
2answers
122 views

Understanding this example of projective geometry in Algebraic matroids

In this paper by Evans and Hrushovski: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s3-62.1.1 they characterize projective planes in algebraically closed fields. These are ...
2
votes
1answer
72 views

A matroid problem inspired by a linear algebra problem

Let $V$ be a finite-dimensional vector space over $\mathbb{R}$. Let $A = (v_{ij})$, with $1 \leq i \leq m$ and $1 \leq j \leq n$, be an $m$ by $n$ array of elements of $V$ (so that for each $i$, $j$ ...
4
votes
1answer
71 views

A question on row-rank and column-rank for square arrays of vectors

Consider a $d$ by $d$ array of vectors $(v_{ij})$, where $1 \leq i,j \leq d$ and each $v_{ij} \in \mathbb{R}^n$, where $n \geq d$. We say that such an array $(v_{ij})$ has maximal row-rank (...
5
votes
1answer
180 views

Motivations for and applications of Matroid Theory?

I have taken an interest in this topic recently. If one is unfamiliar with matroids, I will give the definition here. Let $M=(E,\mathcal I)$ where $E$ is a finite set called the ground set and $\...
2
votes
1answer
35 views

Bases of a Matroid

Suppose for two subsets $X\subseteq Y$ of $S$ that there are bases $B_1$ and $B_2$ for which $X\subseteq B_1$ and $B_2\subseteq Y$. Prove that there is a basis $B$ for which $X\subseteq B\subseteq Y$. ...
0
votes
0answers
40 views

Graphic Matroids are representable

How can I prove that graphic matroids are representable over every field $\mathbb{F}$? I've seen a proof where they do it through circuits, but I'm asking how can I prove it as well with the ...
1
vote
2answers
38 views

What does it really mean by independent sets in Matroids?

My professor said that if a matroid is defined by $M = (S,\mathcal{I})$, then we have $\mathcal{I} \subseteq \mathcal{P}(S)$ such that all $\alpha \in \mathcal{I}$ are independent. I am confused as ...
0
votes
0answers
29 views

total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
0
votes
1answer
30 views

Path counts in a graph via enumerating independent sets of a graphic matroid

If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a matroid? Perhaps yes, because the edge space ...
1
vote
2answers
59 views

Matroids-Discrete Optimization

I happen to stumble across this question where they ask to give an example of an independent system that has two maximal independent sets $X$ and $Y$ such that $|X|\neq |Y|$. How exactly would you ...
1
vote
1answer
20 views

Minimal number of nonzero points in $\mathbb{F}_2^n$ which cover all subspaces of codimension k

What is the minimal size of $S \subset \mathbb{F}_2^n \setminus \{0\}$ so that for any codimension $k$ subspace $W \subset \mathbb{F}_2^n$, there exists $s \in S$ such that $s \in W$? We can assume ...
0
votes
1answer
91 views

Prove $(E, I)$ is a matroid.

Where $V$ is a vector space and $E$ is a finite subset of $V$. $I$ is the the set of linearly independent subsets of $E$. How to prove $(E, I)$ is a matroid? Edit: I understand that by definition $M$ ...
0
votes
0answers
39 views

Given a tree with n vertices, is there a transformation by which we can get all the trees with n vertices

Given a tree with n vertices, is there a transformation or a series of transformations by which one can get all the trees with n vertices? For example, when $n=4$, there are two non isomorphic trees $...
2
votes
1answer
114 views

Flats of the dual matroid and union of circuits of the matroid

I'm struggling to formally demonstrate the hypothesis that every flat of the dual matroid ($F \in \mathcal{F}(M^*)$) is the complement of some circuit or union of circuits of the original matroid $M$. ...
0
votes
1answer
61 views

Minimum of two submodular functions

Let $V$ be a finite set, and denote with $2^V$ the corresponding power set. Consider two (non-monotone) submodular function $f:2^V\rightarrow \mathbb{R}_{\geq 0}$ and $g:2^V\rightarrow \mathbb{R}_{\...
0
votes
1answer
35 views

Matroid isomorphisms and self-duality

The uniform matroid $U(n,k)$ has $n$ elements and all $k$-element subsets are bases. I was under the impression that $U(2k,k)$ is self-dual, that is, it is isomorphic to its dual in which bases are ...
0
votes
0answers
46 views

Generalized matroids

Consider the following definition of matroid. A matroid over a set $X$ is a family $\mathcal B\subseteq\mathcal P(X)$ of subsets of $X$ (the set of bases) with the following properties: $\mathcal B$ ...
2
votes
4answers
80 views

Mnev's Universality Type Theorem

In order to state properly Mnev's universality type theorems, one has to understand the definition of stable equivalence. I have some questions to the definition. Here is the definition as in Oriented ...
0
votes
0answers
39 views

Name for number of coloops in a matroid

EDITED: Simpler question Given a matroid, a coloop is an element which belongs to all bases (equivalently, to no circuit). Is there a name for the number of coloops of a matroid? Can you please give ...
4
votes
1answer
128 views

Build up a matroid using a “rank-like” function

It is not hard to show that given a matroid ($E, L$) and a defined rank function, $L$ is exactly those subsets whose rank is equal to the size. The following question is about how to build up a ...
2
votes
1answer
53 views

Construct a rank-3 matroid using rank-2 flat

Let $E$ be a finite set with size bigger or equal to 3. Let $L$ be a collection of subsets of $E$ such that: $2 \leq |A| < |E|$ for any $A \in L$ $|A \cap B| \leq 1$ for any $A, B \in L$ Now show ...
0
votes
1answer
41 views

Automorphism group on a matroid

I'm trying to prove that the automorphism group on a matroid is (set-theoritically) equal to the automorphism group on its dual matroid. that is, $\ Aut(M) = Aut(M^*)$ where the automorphism group ...
0
votes
1answer
61 views

Determine whether M = ([3],B), with B = ([3] C 2), is a graphic matroid.

I currently am learning about matroids in my discrete mathematics class. While I had problems understanding them at all at first, I think I am starting to see how they work. But now I have found a ...
2
votes
0answers
60 views

properties of identically self-dual matroids

I'm dealing with an identically self-dual matroid M on the vertices E=[2N], that is, if B is a basis of M also E-B is a basis of M itself. I need simple combinatorial properties of these, things like ...
3
votes
1answer
39 views

Proving the recurrence relation of the rank polynomial (or Tutte's) on a matroid.

I'm reading through chapter 15 on Algebraic Graph Theory by Godsil and Royle. The $\mathit{rank \ polynomial}$ for a matroid $M$ is defined as $$R_M(x,y)=\sum_{A \subseteq\Omega} x^{rk(\Omega)-rk(A)}...
0
votes
1answer
33 views

How do set functions work in this example?

I'm sure this is a very simple question, and that I'm missing something quite fundamental, but here goes: Defintion: A function $f: 2^N \to \mathbb{R}$ is called submodular if $$f(S) + f(T) \ge f(S \...
0
votes
1answer
90 views

Are there any linear algebra books in which matroid theory is described and used?

I am interested in matroid theory now. Are there any linear algebra books in which matroid theory is described and used?
1
vote
1answer
56 views

Independence system/ graph-theory

$ (E,S)$ is an independence system with $ w: E \rightarrow \mathbb{R_+}$. $E= \{ e_1,...,e_m\} $ is the set of edges with $ w(e_1) \geq....\geq w(e_m), w(e_{m+1}):=0$. Define the set: $ E_i:= \{ e_1,....
1
vote
1answer
39 views

Circuits of matroid after adding rows to its representation

I just started learning about matroids and oriented matroids, and my point of interest is their relation to the ideals of linear varieties/subspaces. If I start with a proper linear subspace $L \...
3
votes
0answers
75 views

laminar matroid polytope

Let S be a ground set, and $\mathcal{S}$ be a laminar family of subsets of S. That is, for every two distinct subsets A, B$\in \mathcal{S}$, we have either $A\subseteq B$ or $B\subseteq A$ or $A \cap ...
0
votes
0answers
46 views

Using a matroid to model emotional temperament.

An idiot crank devised a model of emotional temperament using a bitmask, $XYZ$. $X$ represent the bit that means "able to handle extreme negative emotions." $Y$ represents the bit that means "able to ...

1
2 3 4 5 6