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
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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})$ ...
2
votes
1answer
30 views

Separable items and matroids

Let $E$ be a finite set and $I$ a downwards-closed set of subsets of $E$ (let's call them "independent sets"). Say that two elements $x,y\in E$ are separable if there exists a partition of $...
0
votes
0answers
26 views

The Greedy Algorihm for Matroids works for maximisation and minimisation

I am working on the following exercise: Let $(S,\mathcal{F})$ be a matroid and let $c:S \rightarrow \mathbb{R}$ be a weight function on $S$. Find an algorithm that solves the following problem: ...
2
votes
0answers
51 views

Partitioning a matroid into bases

Suppose we want to partition the elements of a matroid $M$ into $n$ subsets, each of which is a base. Of course this is not always possible. For example, when $M$ is the uniform matroid on $8$ ...
1
vote
0answers
29 views

Caracterization for disjoint transversal and partition partial transversal

In book of Schrijver (Combinatorial Optimization Polyedra and Efficiency), has a affirmation follows below: Illustration He suggested that is possible to show using matroid base packing theorem and ...
0
votes
0answers
40 views

Subsets in the context of matroid independent sets

Is the disjoint union of two Matroids a Matroid itself? Let $E_1$ and $E_2$ be two disjoint sets. Moreover, assume that $(E_1,S_1)$ and $(E_2,S_2)$ are matroids. Define $S:=\{X \cup Y|X \subseteq S_1 ...
2
votes
0answers
42 views

When is the circuit elimination axiom an equality?

The (weak) circuit elimination axiom states that if $C_1$ and $C_2$ are distinct circuits of a matroid and $e\in C_1\cap C_2$, then there exists a circuit $C_3$ such that $C_3\subseteq (C_1 \cup C_2) -...
0
votes
1answer
15 views

A base of a matroid contains its independent subset and is disjoint of an independent subset of its base.

Let $A$ and $B$ be two disjoint subsets of the matroid $M$. Let $A$ be independent in $M$, and $B$ be independent in $M$'s dual. I would like to ask for help in proving that $M$ has a base which ...
0
votes
1answer
57 views

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 ...
1
vote
0answers
49 views

Go from one partition of the ground set to another using basis exchanges

Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...
1
vote
1answer
57 views

Is the following a matroid?

If I have a bipartite graph $G = (L \cup R, E)$, then there is a matroid on ground set $L$ whose independent sets are the matchable subsets of $L$. That is, $A \subseteq L$ is independent if there is ...
2
votes
1answer
54 views

Dimension of the Circuit Space of a Matroid

If $G$ is a graph with edge set $E$, let $W$ be the $\mathbb{Z}/2$-vector space generated by the elements of $E$. If $A = \{a_1, \dots, a_n\} \subset E$, let $\bar{A} = a_1 + \dots + a_n \in V$; then $...
2
votes
0answers
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\}$ ...
0
votes
2answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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.
3
votes
1answer
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 ...
3
votes
1answer
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$ ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
28 views

Constructing Vector Matroid Algorithm

Suppose I am given a set $V$ of $n$ vectors in $\mathbb{R}^3$. I want to construct the matroid associated with these vectors (i.e. $M=(E,\mathcal{I})$ with $E=\{1,\dots, n\}$ and $E\supseteq I\in\...
1
vote
0answers
64 views

Properties of the value function generated by an integer progamming problem

Consider the following linear programming problem max $w^\top x$ s.t. $Ax\leq b, \,\,0\leq x\leq 1$, where $x\in R^E, w \in\{0,1\}^E$, $A$ is a $\{0,\pm 1\}$ matrix and $b$ is a vector. Further ...
0
votes
0answers
62 views

Prove that there is a unique optimal set in a weighted matroid

Prove that there is a unique optimal set in a weighted matroid M = ( S, I ) with distinct weights on elements from S. Note The fact that the optimal set constructing algorithm in this case yields a ...
0
votes
1answer
17 views

The correspondence between independence systems and basis systems of a matroid

Let $E$ be a finite set. $1)$ If $I$ is an independence system on $E$, then the family of maximal elements of $I$ is a basis system $2)$ If $B$ is a basis system, then $I_{b \in B} 2^b$ is an ...
2
votes
1answer
40 views

Is it true that for every connected matroid $M$ we have $\chi(M)=\chi(M^*)$?

If for any connected matroid $M$ on $E$ we let $\chi(M)$ be the minimum size of any partition of $E$ into independent sets of $M$, then is $\chi(M)=\chi(M^*)$? (where note $M^*$ is the dual of $M$ and ...
0
votes
1answer
30 views

Definition of Matroid in two cases

For matroids M = (S, U), the following property applies to U: If A, B ∈ U and |B| = |A| + 1 , then there must exist an x ∈ {B \ A} such that A∪ {x} ∈ U I want to prove this property for the ...
1
vote
1answer
62 views

Do graph homomorphisms preserve forests?

A graph homomorphisms $\phi:G\rightarrow H$ is an adjacency preserving map between graphs $G$ and $H$. In other words, if $u,v\in V(G)$ are adjacent in $G$, written $u\sim v$, then we must have $\phi(...
0
votes
0answers
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 ...
0
votes
1answer
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$ ?
4
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
43 views

How can I tell if an intersection closed family are the flats of a binary matroid?

Suppose I have a pair $(X,\mathcal{F})$ such that $\mathcal{F}$ is an intersection closed family of subsets of $X$ for which $X\in \mathcal{F}$ is there a technique I can use to determine easily if $\...
1
vote
1answer
46 views

Matroid induced by a matrix where a circuit's nullspace is spanned by a non-negative vector

Let $A = [a_1, \dots, a_n] \in \mathbb{R}^{m \times n}$, $[n] = \{1, \dots, n\}$, and $\mathcal{I} \subset \mathcal{P}([n])$ be the set of all $I \in \mathcal{P}([n])$ such that $\{a_i : i \in I\}$ is ...
2
votes
0answers
58 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
47 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
115 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
43 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
27 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
34 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
130 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
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 ...
1
vote
1answer
68 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
97 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
2 3 4 5 6