# 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
Filter by
Sorted by
Tagged with
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
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
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
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
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
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
89 views

• 1,835
1 vote
78 views

• 1,821
1 vote
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
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
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
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
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
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
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
### 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 ...
### (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,...