Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

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

1
vote
0answers
27 views

properties of identically self-dual matroids

I'm dealing with an identically self-dual matroid M on the vertices E=[2N], that is, if B is a basis of M also E-B is a basis of M itself. I need simple combinatorial properties of these, things like ...
3
votes
1answer
24 views

Proving the recurrence relation of the rank polynomial (or Tutte's) on a matroid.

I'm reading through chapter 15 on Algebraic Graph Theory by Godsil and Royle. The $\mathit{rank \ polynomial}$ for a matroid $M$ is defined as $$R_M(x,y)=\sum_{A \subseteq\Omega} x^{rk(\Omega)-rk(A)}...
0
votes
1answer
30 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 \...
0
votes
1answer
57 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?
0
votes
0answers
38 views

The cardinality of every maximal subset of the independent set $\mathcal{I}$ is same. (Matroid Theory)

I am watching this lecture on matroid now. The definition of matroid in this lecture is here: Definition: Let $S$ be a finite set. Let $\mathcal{I}$ be a set of subsets of $S$ which ...
0
votes
0answers
214 views

Euclidean incidence spaces

Structure $\left<X,B\right>$ is an $n$-dimensional Euclidean incidence space iff $B$ is ternary betweenness relation associated with $n$-dimensional Euclidean geometry. That is, Euclidean ...
1
vote
1answer
44 views

Independence system/ graph-theory

$ (E,S)$ is an independence system with $ w: E \rightarrow \mathbb{R_+}$. $E= \{ e_1,...,e_m\} $ is the set of edges with $ w(e_1) \geq....\geq w(e_m), w(e_{m+1}):=0$. Define the set: $ E_i:= \{ e_1,....
1
vote
1answer
34 views

Circuits of matroid after adding rows to its representation

I just started learning about matroids and oriented matroids, and my point of interest is their relation to the ideals of linear varieties/subspaces. If I start with a proper linear subspace $L \...
1
vote
0answers
34 views

laminar matroid polytope

Let S be a ground set, and $\mathcal{S}$ be a laminar family of subsets of S. That is, for every two distinct subsets A, B$\in \mathcal{S}$, we have either $A\subseteq B$ or $B\subseteq A$ or $A \cap ...
0
votes
0answers
41 views

Using a matroid to model emotional temperament.

An idiot crank devised a model of emotional temperament using a bitmask, $XYZ$. $X$ represent the bit that means "able to handle extreme negative emotions." $Y$ represents the bit that means "able to ...
0
votes
1answer
25 views

Definition: Matroids being Equal

I've been trying to find a definition of two matroids being equal. I would have thought two matroids are equal iff their ground sets and independent sets are equal. However, online I found out that ...
4
votes
2answers
90 views

Combinatorial or polyhedral description for tropicalization of the positive subset of a real linear subspace

I had two questions: one regarding a definition of tropicalized linear subspaces, and the second about how to find similar characterizations for the logarithmic limit set of the positive subset of a ...
0
votes
0answers
47 views

Optimal matching with halls marriage theorem

Hall’s marriage theorem says that a bipartite graph with vertex set $U ∪ V$ has a matching of size $|U |$ if and only if every subset $S ⊂ U$ has at least $|S|$ neighbours. Suppose that ${1, 2, 3, 4, ...
-1
votes
1answer
169 views

Show that $M_k(G)$ is the set of independent sets of a matroid! [closed]

Let $G = (V,E)$ be an undirected graph. Set $M_k(G) = (E,S)$ where $$S = \{F ∪M | F ⊆ E,(V,F) \;\text{acyclic},M ⊆ E,|M| ≤ k\}.$$ Show that $M_k(G)$ is the set of independent sets of a matroid! In ...
0
votes
0answers
46 views

Show that a set of subsets is the set of bases of a matroid

Let $\mathcal E$ be a set and $\mathcal B$ be a set of subsets of $\mathcal E$ satisfying the following conditions: $B_1$: $\mathcal B$ is non-empty $B_2$: If $A, B \in \mathcal B$ are distinct and $...
0
votes
1answer
33 views

The collection of anti-ideals of a ring forms a matroid?

Let $A \subset \Bbb{Z}$. $A$ is a called an anti-ideal when $x, y \in A \implies x - y \notin A$. $\Bbb{Z}\ni z \neq \pm 1 \neq a\in A \implies za \notin A$. (Notice that from before only $z$ had ...
1
vote
1answer
25 views

Anti-ideals in $\Bbb{Z}$ form a matroid, so all maximal anti-ideals are in bijection?

Let $A \subset \Bbb{Z}$. $A$ is a called an anti-ideal when $x, y \in A \implies x - y \notin A$. $z \in \Bbb{Z}, z \neq \pm 1, a \in A \implies za \notin A$. Matroids are something in graph theory ...
0
votes
0answers
24 views

How to Prove a Matrix is Not a Vector Matroid Over $\mathbb{R}$: Fano Plane Example

$\therefore$"> Above is point-line incidence geometry for the Fano Plane. In other words, this matroid $M$ has a ground set $E(M)=\{ a, b, c, d, e, f, g\}$ and a collection of bases $\mathcal{B}(M)=...
1
vote
1answer
41 views

How to decide whether a linear subspace over $\mathbb{Z}_2$ is the cycle space of some graph?

Preliminaries: Assume we have a simple graph $G=(V,E)$ (no loops, no multiple edges). If we label the edges with $k=1,\dots,|E|$, its cycle space $C$ can be identified with a linear subspace of $\...
1
vote
2answers
34 views

Matroids and greedy algorithms - how can a singleton subset be dependent?

I'm reading up on greedy algorithms (using [CRLS]) and the book discusses a connection between such algorithms and Matroids. The given definition for a Matroid is $S$ is a finite set. $I$ is a ...
3
votes
1answer
92 views

Proving property of two trees.

Consider a graph $G$. Let $A, B$ are two trees in a graph and $T_a, T_b$ represents their corresponding edge sets. Also an edge $e \in E$ is an extension of tree $A$. If $T_b \cup \{e\}$ forms a cycle ...
0
votes
1answer
49 views

What is the difference between matriods and hypergraphs?

Matroids have a more complicated definition but it looks to me like they might be equivalent. I would like to know exactly what the difference is, if any.
0
votes
0answers
16 views

Formalization of an ad-hoc discrete structure

I've implemented a structure I've called CompactPaths that basically represent "paths" across dimensions in a compacted way (explained below). Intuitively, it makes ...
0
votes
0answers
16 views

Is such “characteristic function” studied in matroid theory?

As a beginner it seems to me such a function $F$ on a matroid $M$ seems very natural i.e. $F(A)=0$ if $A$ is an independent set and $F(A)=1$ if $A$ is dependent. But I don't know whether people ...
1
vote
1answer
43 views

Covering relation in the lattice of closed subsets

Covering relation in the lattice of closed subsets Hello! I am currently reading Martin Aigner's Combinatorial Theory and I have to say this book is definitely above my level, but (very) slowly ...
3
votes
1answer
82 views

Stronger Axiom for Circuit Matroids - why is it equivalent?

The typical definition of a circuit matroid is as follows. A matroid $M$ consists of a finite set of elements $E(M)$ along with a collection of non-empty subsets $C(M)\subseteq 2^M$ (called circuits) ...
1
vote
1answer
45 views

Graphic matroids - What's wrong with this simple example?

I am trying to understand the definition of graphic Matroids in Cormen's Introduction to algorithms. However, I have trouble understanding it for the simple example shown below. But first Cormen's ...
0
votes
1answer
22 views

Well defined matroid invariant

I'm currently studying Gordon/McNUlty book Matroids: a geometric introduction. Chapter 9 is the Tutte polynomial and corank nullity polynomial Theorem: For all matroids $M$, the Tutte-polynomial is ...
0
votes
0answers
50 views

Circuit Hyperplane relaxation Thm

I need to prove the following, If $A$ is a circuit-hyperplane of a matroid $M$, then the relaxation of $M'$ is also a matroid. So far I have: Assume $A \in \mathcal C(M)$, since every proper subset ...
2
votes
2answers
83 views

Matroid Theory with Graph Theory, Need an Introduction Book

I am looking for a undergraduate introduction to matroid theory. We got them introduced today, to prove the Kruskal algorithm.... I can't say it was more elegant then the direct proof of the algorithm....
1
vote
1answer
42 views

Is this a matroid?

Given a matroid $(N,\mathcal{M})$, for some $a \in N$, is this a matroid: $$ (N \setminus \{a\},\mathcal{M} \setminus \{S : S \subseteq N,\ a \in S\} )$$ Is the following reasoning correct: Since $\...
6
votes
1answer
78 views

Prescribing the dimension of intersections of sub-vector spaces

Let $n$ be a positive integer. For each subset $S$ of $\{1,\dots,n\}$ let $d_S$ be a nonnegative integer. Assume that the $(d_S)$ satisfy: $$ S\subset T\implies d_S\ge d_T, $$ $$ d_{S\cap T}\ge d_S+...
2
votes
1answer
23 views

Equivalence of valuated vectors in standard matroids

Valuated matroids can be defined in terms of valuated vectors. I'm wondering whether is there an equivalent definition for ordinary matroids? Below I include two standard definitions of valuated ...
0
votes
0answers
64 views

Example of greedy algorithm for matroid optimization?

Let $M=(E,\mathcal I)$ with $|E|=n$ be a matroid and $c\in\mathbb R^n$, then the optimization problem \begin{align} \max_T &\quad\sum_{j\in T} c_j\\ \mathrm{s.t.} &\quad T\in\mathcal I \end{...
0
votes
1answer
108 views

Proof of Graphic Matroids (Using Rank in Context of Graph Theory)

The rank of a graphic matroid given by an edge set $X$ can be denoted as $r(X)=n-c$ where $n$ is the number of vertices in the subgraph of edges $X$ and $c$ is the number of connected components of $X$...
1
vote
0answers
23 views

Circuit(cyle)-hyperplanes in a graph

Im currently working in matroid theory problem involving graphs. A circuit-hyperplane in a matroid is a circuit with |r| elements in a Flat of |r-1|. Translated into a graph the circuit-hyperplane ...
0
votes
1answer
77 views

0-1 Knapsack problem, minimal dependent sets,another unclear proof

We consider the constrained set of a $0-1$ knapsack problem $$S=\{x\in B^n\mid \sum_{j\in \{1,\ldots,n\}}a_j x_j\leq b\}$$ where $a_j\in \mathbb{Z}_+$, for $j\in \{1,2,\ldots,n\}$ and $b\in \mathbb{...
1
vote
0answers
58 views

Conditions for Graphic Matroids

Basically, I've been researching chromatic graph theory for an essay and have come across this article regarding matroids and their generalisation of graphs. The article in question is here: "http://...
0
votes
2answers
60 views

Struggling with the definition of rank for a independent system/matroid

Let $U = (E, I)$ be an independent system (not a matroid). A base $B$ of $E$ is a maximal independent set. $(E, I) = (\{1,2,3,4\}, \{\{\emptyset, \{1\}, \{2\}, \{3\}, \{2, 3\}, \{1, 2\},\{4\}\}$ ...
1
vote
1answer
58 views

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

Graphic examples of matroids [closed]

I am interested in some graphic examples of matroids. I am having trouble finding anything substantial on the internet.
0
votes
1answer
32 views

Proving universality of the Tutte-Grothendieck polynomial.

I'm following the proof in McNulty and Gordon's graphic introduction to matroids. The theorem isIf $\mathcal{M}$ is the set of isomorphism classes of matroids, then if $f:\mathcal{M}\rightarrow\mathbb{...
2
votes
2answers
100 views

0-1 Knapsack problem, dependent sets, unclear proof

We consider the constrained set of a $0-1$ knapsack problem $$S=\{x\in B^n\mid \sum_{j\in \{1,\ldots,n\}}a_j x_j\leq b\}$$ where $a_j\in \mathbb{Z}_+$, for $j\in \{1,2,\ldots,n\}$ and $b\in \mathbb{...
1
vote
1answer
70 views

Why is this not a matroid?

If I recall correctly both of these definitions are equivalent: $(E,I)$ is an independence system and satisfies the augmentation property. $(E,I)$ is an independence system and all maximal ...
2
votes
0answers
26 views

Contraction of oriented matroid as related to polytope?

I'm reading the following description of the contraction of oriented matroid, and its connection to polytopes: I have yet to find a numerical example to verify 6.13., but first I just want to check ...
3
votes
0answers
61 views

Relationship between Affine Dependence and Linear Dependence in Oriented Matroids?

I'm reading "Lectures on Polytopes" by Gunter Ziegler. The author first introduces the components of oriented matroids in affine case, then making a transition to linear case, with the condition "1z ...
1
vote
1answer
38 views

How to list all circuits of an oriented matroid and all circuits of its contraction of a vertex by hand?

For example, the oriented matroid CUBE has $40$ signed circuits. Its contraction to the vertex $8$ has $34$ signed circuits. What is a smart way to list out all the circuits without missing out or ...
1
vote
1answer
113 views

Given bases $A$, $B$ of a matroid there is a one-to-one mapping $\omega$ from $A$ to $B$ such that $(A - {a}) \cup {\omega(a)}$ is independent

Given any two bases A and B of a matroid, there is a one-to-one mapping $\omega$ between $A$ and $B$, such that for element $a$ in $A$, $ (A − {a}) \cup {\omega(a)}$ is independent. I am having ...
0
votes
1answer
25 views

How much does the number of connected components of a graph grow in the case below?

Let $G=(V,E)$ be a simple graph with $c$ connected components. We say that $e_1, e_2 \in E$ is inseparable if the fundamental cycles of $e_1$ and $e_2$ are identical in a given fundamental cycle basis....
0
votes
0answers
25 views

Smallest matroid containing two disjoint maximal elements of cardinality $K$?

Given a ground set $N=(a_0,a_1,\dots,a_{K-1},b_0,b_1,\dots,b_{K-1})$ of size $2K$, what is the smallest matroid for which $A=(a_0,a_1,\dots,a_{K-1})$ and $B=(b_0,b_1,\dots,b_{K-1})$ are independent ...