Mathematics Stack Exchange
Mathematics Stack Exchange

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.

A Matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice.

Matroid theory borrows extensively from the terminology of linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory

378 questions
1
vote
1 answer

When is a matroid a graphical one?

I'm struggling with the definition of a graphical matroid. Let $ G = (V, E)$ be an undirected graph. Matroid $M = ( E,I ),$ where $I= \{ F ⊆ E : F$ is acyclic $\}$ ; ie, forests in G. So if $M$ follows this rule than we can state that $M$ is a…
Oleg
  • 499
1
vote
1 answer

Submodular monotone functions

A few definitions: A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ S,T\subseteq E $ with $…
Shmoopy
  • 325
1
vote
2 answers

Submodular functions

A few definitions: A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ S,T\subseteq E $ with $…
Shmoopy
  • 325
1
vote
1 answer

Intersection of circuits in matroid and dual matroid

I am thinking about the following problem: Suppose $(E, \mathcal F)$ is a matroid and $(E, \mathcal F^*)$ is the dual matroid of $(E,\mathcal F)$. Let $C$ be a circuit of $(E, \mathcal F)$ and $C^*$ be a circuit of $(E, \mathcal F^*)$. Show that…
slin0
  • 385
1
vote
1 answer

How to prove two matroids are equal?

One of my homework problem is to prove $(M^*)^*=M$, given $M=(S,\mathcal{I})$ is a matroid, i.e. dual of a dual matroid is itself. My confusion is what is needed to prove the equality, in general. Is it good enough to say two matroids have same…
adosdeci
  • 165
1
vote
1 answer

Examples of Gammoids

We have the following definition of a Gammoid from Schrijver's "Combinatorial Optimization, Polyhedra and Efficiency" volume B: "Take a directed graph $D = (V,A)$ and subsets $U$ and $S$ of $V$. For $X,Y \subseteq V$, call $X$ linked to $Y$ if…
combo
  • 178
1
vote
1 answer

Number of Different Bases in a Matroid

I am trying to figure out a lower bound on the number of different bases a matroid can have. The matroid has rank $n$ and its ground set is the disjoint union of two bases. I think that it's $2^n$ because we can take any element from the first…
TheVarunShah
  • 45
1
vote
1 answer

What is the analog of a uniform matroid when the ground set is not finite?

If $E$ is a finite set and $k \in \mathbb{N}$, then the uniform matroid of rank $k$ is defined as the matroid generated by taking the collection of $k$ element subsets of $E$ as a basis. Is there an analog of this notion when $E$ is not…
Jackson Walters
  • 1,447
1
vote
0 answers

What does it mean to be equicardinal?

I'm reading up on matroids and have run into a lemma (and proof for said lemma) stating that the bases of a matroid are equicardinal. I assume that it means the bases have the same cardinality, but they proved that fact on the previous page.
tots
  • 11
0
votes
0 answers

the proportion of $GF(2)$-representable matroids

I just came into contact with matroid theory through James Oxley's book 'Matroid Theory (2011)', and I was stuck on a problem while doing the exercises in the first section of Chapter 1: Deduce that, as $n\rightarrow\infty$,the proportions of…
Jungang Chen
  • 61
0
votes
0 answers

How to show that an independence system whose maximally independent subsets have same cardinality is a matroid

Suppose $M=(E,S)$ is an independence system, meaning $S\neq \emptyset$ $S\subseteq 2^E$ $\forall A\in S, B\subseteq A: B\in S$ For $A\subseteq E$, $X$ is called a maximally independent subset of $A$ iff $X\subseteq A$ $X\in S$ $\forall Y\supset…
Manatee Pink
  • 711
  • 4
  • 8
0
votes
1 answer

How to prove that a matroid restricted to a subset is still a matroid

A pair $M=(E,S)$ is a matroid iff $M$ is an independence system, meaning 1.1 $\forall A\in S, B\subseteq A: B\in S$ 1.2 $S\subseteq 2^E$ $\forall A,B\in S: |A|=|B|+1\implies \exists v\in A\setminus B: B\cup\{v\}\in S$ Let $E_0\subseteq E$ and…
Manatee Pink
  • 711
  • 4
  • 8
0
votes
1 answer

Why matching matroid is a generalization of graph matching and matroid intersection

I readed in the book of Schrijver on matching matroid problem. Follow the figure: I understood that this problem is a generalization of graph matching problem applied in the matroid $M = (S, 2^{S})$ and any graph. But I did not understand the part…
Frank
  • 113
0
votes
1 answer

Let $V$ be a vector space. Let $S=\{v_1,v_2,\cdots,v_n\}\subseteq V$. Let $I=\{X\subseteq S:X\text{ is linearly independent}\}$ ...

I am learning matroids and I saw the following example: Let $V$ be a vector space. Let $S=\{v_1,v_2,\cdots,v_n\}\subseteq V$. Let $I=\{X\subseteq S:X\text{ is linearly independent}\}$. Then $(S,I)$ is the vector matroid. The problems is that I don't…
PDP
  • 23
  • 4
0
votes
0 answers

Independency of a set in matroid theory

Suppose $M=(X,I)$ be a matroid , $X=\{x_1,...,x_m\}$ and $$Y=\{x_i\mid \operatorname{rank}(\{x_1,...,x_i\}) > \operatorname{rank}(\{x_1,...,x_{i-1}\}) \}$$ then $Y$ is in I. Could anyone help me with this problem? Thanks for any helps.
Mathgreek
  • 79
1 2
3
4