# 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.

255 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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? ...
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 ...
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 ...
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 ...
58 views

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.
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 ...
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 ...
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 ...
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 ...
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 ...
18 views

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 \...
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?