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.

291 questions
Filter by
Sorted by
Tagged with
31 views

What is a free element of a matroid?

I have often read the term free element of a given matroid $M$. However, I could not find a proper defintion of what a free element actually is. I know what the free matroid is but free elements seem ...
25 views

Properties of the rank function on independence systems

Let $\mathcal{M}=(X,\mathcal{I})$ a matroid on $X$ (here $\mathcal{I}$ is the collection of independent subsets of $\mathcal{M}$). If $\rho$ denotes the corresponding rank function, namely the ...
39 views

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})$ ...
30 views

42 views

95 views

Matroid: another version of basis exchange property

Let $M$ be a matroid and $A,B$ be two bases of $M$. The basis exchange property tells us that for every $a\in A\setminus B$, there exists $b\in B\setminus A$ such that $(A\setminus \{a\})\cup \{b\}$ ...
74 views

Properties of submodular functions

I was working on submodular set functions, and I came across a property on Wikipedia, that I was not able to prove/find any reference for. On the Wikipedia article on submodular set functions, Under ...
16 views

Is there a set partition associated with a matroid

It is well-known that for any set partition of X one may construct a matroid by taking the subsets whose intersections with each block of the partition has at least one element (clearly one may ...
112 views

What is an independent subset of a set? [closed]

I am reading a book about approximation algorithms. The book first defines an independent system and an independent set of a family of subsets. The definition about the independent subset of a set ...
52 views

Example of a representable matroid

I'm studying theorem 6.6.3, Oxley. It states that a matroid $M$ is representable over every field if and only if $M$ is binary and for some field $K$ of characteristic other than 2, $M$ is ...
37 views

Intersection of flats containing X

I need to prove this statement about matroids: Given $X\in E$, the closure of $X$ is equal to the intersection of all the flats that contain $X$. Can anybody show me how to solve this? Thank you.
47 views

Understanding $\mathfrak{S}_n$ invariant algebras via the Orlik-Solomon algebra

I am trying to understand invariant algebras for nontrivial characters. The gist of my question is confusion over the definition and an equivalent condition given in Stanley's survey paper Invariants ...
43 views

Transform a submodular function into a monotone one?

First, some definitions. Given a finite set $E$, a function $f: E \to \mathbb{R}$ is submodular if, for any $A,B \subseteq E$, we have $$f(A) + f(B) \geq f(A \cup B) + f(A \cap B).$$ The function $f$ ...
37 views

Help needed with Matroids! Applicable theorems? A CSP Complexity.

Unfortunately, I am not very familiar with Matroids and do not have much time to study them. I would appreciate someone helping me figure out whether any of the following theorems, taken from the ...
79 views

Is the following set system a matroid? [closed]

Suppose $\mathcal{M}=(E,\mathcal{I})$ is a matroid without any loop where $E$ is the ground set and $\mathcal{I}$ is the set of independent sets. Let $x,y$ be two distinct elements of $E$. Take set ...
38 views

Equivalence relation connected components matroid

A matroid $M$ is said to be connected if any two elements of the matroid lie on a common circuit. We say that $S\subseteq E(M)$ is a connected component of $S$ if for all $i,j\in S$ there exists a ...
28 views

75 views

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

if $X \subseteq Y$ are flats s.t. $r(Y) = r(X)-1$ then $\exists$ hyperplane $H$ s.t. $Y = H \cap X$.

Let $X$ and $Y$ be flats of a matroid $M$ such that $Y \subseteq X$ and $r(Y) = r(X)-1$. How can i prove that $M$ has a hyperplane $H$ such that $Y = H \cap X$ ?
81 views

Does this matroid invariant have a name?

For a matroid $M$ on $X$ with closure operator $\tau:2^X\to 2^X$ let $c(M)=\min\{|S|:\tau(X\setminus S)\neq X\}$. This is an invariant because if $M$ and $M'$ are isomorphic (i.e. if flats of $M$ are ...
63 views

A proof that if $M’$ is a matroid quotient of $M$, each base in $M$ contains a base of $M’$ that doesn’t use rank function?

I'm a math student and I'm studying matroids. I tried to prove it myself, but I just couldn’t do it. Just note that the book I'm following, called Coxeter Matroids by A. V. Borovik, I. M. Gelfand and ...
37 views

Is there a way to construct a matroid from an independence system?

I'm asking for the following problem: Let $E$ be a finite set and $\mathcal{I}$ a given independence system (i.e. a non-empty collection of subsets of $E$ closed under taking subsets). Is there a way ...
76 views

Geometric representation of a rank 4 matroid

I am working through Oxley's notes on Matroid Theory (https://www.math.lsu.edu/~oxley/survey4.pdf). Exercise 5.8 asks for a geometric representation of the matroid associated to the graph $K_5$, the ...
43 views

66 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 ...
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 \$...