Skip to main content

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
2 answers
44 views

Do Egyptian representations follow a matroid structure?

Let $V=(v_1,\cdots,v_n), v_i \in \mathbb N$ be independent with respect to $\frac p q$ if there doesn't exist an indicator vector $\beta = (b_1, \cdots, b_n), b_i \in \{0,1\}$ with $\sum \frac{b_i}{...
Snared's user avatar
  • 952
0 votes
0 answers
24 views

weighted matroid intersection theorem

I am trying to prove the result in Section 6 of this lecture note. It just says the proof is similar to the non-weighted version without giving it. (A same non-weighted version proof is here, which ...
Connor's user avatar
  • 2,085
1 vote
1 answer
43 views

matroid intersection and graph orientation

I am reading this lecture note and feel confused about the Theorem 6.2 there. Using the notation in Section 6.1.3, we should prove that for any $U\subseteq A$, $$r_1(U)+r_2(A\setminus U)\ge |E|.$$ I ...
Connor's user avatar
  • 2,085
0 votes
0 answers
12 views

A weighted Edmonds matroid intersection theorem

I am wondering why Theorem 9.4 of this paper this true. (I don't find any proof in the references there.) To state the theorem, assume $M,N$ are two matroids on $V$. Let $w$ be a weight function $w:V\...
Connor's user avatar
  • 2,085
3 votes
1 answer
42 views

Dimers from Postnikov diagrams

I am reading several papers on Postnikov diagrams, dimer models, and quivers. From the Postnikov diagram, we can draw a dimer model and an ice quiver. My question is as follows. Does every dimer model(...
aleph0's user avatar
  • 103
0 votes
0 answers
36 views

represent linear matroid as an affine matroid

There is an exercise in András Frank’s book Connections in Combinatorial Optimization, An easy exercise shows that every affine matroid can be represented as a linear matroid, and vice versa. I ...
Yu Cong's user avatar
0 votes
0 answers
36 views

Prove a property of rank function from its definition using matroid closure operator

A matroid may be defined using a finite ground set $E$ and a closure operator on $E$ which is a map from $2^E\rightarrow 2^E$ written $A\rightarrow \bar{A}$ such that: $A\subseteq \bar{A}$ $\bar{A}=\...
Vasac's user avatar
  • 73
0 votes
0 answers
30 views

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, ...
Jungang Chen's user avatar
1 vote
1 answer
170 views

Matroid on graphs using disjoint paths

Let $G$ be a graph and $A, B \subseteq V(G)$. Let $\mathfrak{F}$ be the set containing all $F \subseteq B$ that satisfy the condition: There are $|F|$ disjoint $a,b$-paths with $a\in A$ and $b\in F$ ...
Norn0556's user avatar
1 vote
0 answers
35 views

Does this property from linear algebra also hold for infinite matroids?

I'm reading this paper on infinite matroids and wondering if this theorem from linear algebra also holds for matroids. Let $E$ be a (possibly infinite) matroid, $I$ be an independent set and $S$ be a ...
David Lui's user avatar
  • 6,329
0 votes
0 answers
23 views

Affiness, $U_{2,4}$ and $M(K_4).$

I do not know why $M(K_4)$ is not affine over $GF(2)$ or $GF(3)$ but it is affine over all fields with more than 3 elements. I proved that $U_{2,4}$ is $\mathbb F$-representable iff $|\mathbb F| \geq ...
Intuition's user avatar
  • 3,181
0 votes
0 answers
20 views

Lift and frame matroids.

I want to read more about lift matroid and frame matroid and their flats and relations to signed graphs, do you know any basic resources for this?
Emptymind's user avatar
  • 2,069
1 vote
0 answers
56 views

The rank of $X$ in $M^*(G).$

If $X$ is a set of edges in a graph $G,$ how can we know the rank of $X$ in $M^*(G)$ in terms of $G[X].$ Where $M^*(G)$ is the dual of the graphic matroid of $G.$ Some thoughts We know that for all ...
Emptymind's user avatar
  • 2,069
1 vote
0 answers
22 views

Characteristic polynomial and bounded regions.

I know that the number of bounded regions of a homogeneous hyperplane arrangement $\mathcal{A}$(a collection of n hyperplanes) in $\mathbb R^d$is ${ n - 1 \choose d}$ but how can this be expressed in ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
46 views

Understanding contraction in hyperplane arrangements.

Here are two figures that shows a hyperplane arrangement's contraction (this is from McNulty book, "Matroids, a geometric introduction"): I am not sure why a became a line in the right ...
Intuition's user avatar
  • 3,181
0 votes
0 answers
88 views

Hyperplane Areangements and contraction.

I am trying to understand an idea presented in McNulty book, matriods a geometric introduction about the new hyperplane arrangement $\mathcal{A}^{''} = \{ H \cap H_x | H \in \mathcal{A}\}$ where $\...
Intuition's user avatar
  • 3,181
0 votes
1 answer
47 views

When are projective, affine geometries uniform matroids?

I am trying to understand the following corollary in James Oxley book: A simple rank-r matroid M that is representable over $GF(q)$ has at most $\frac{q^r - 1}{q - 1}$ elements. Moreover, if $|E(M)| = ...
Intuition's user avatar
  • 3,181
2 votes
0 answers
55 views

Some properties in Projective Geometry

I am trying to understand the following two Propositions in James Oxley's book "Matroid Theory" Prop. 6.1.3 Let $M$ be a simple rank-r matroid and $\mathbb F$ be a field. The following ...
Hope's user avatar
  • 95
1 vote
1 answer
101 views

Vertices of Matchings in bipartite Graph are Matroid

Let $G=(V,E)$ be a bipartite graph with $V=A \cup B$ (disjoint) and $\mathcal{F}=\{V(N) \cap B\ |\ N\ is \ a\ matching\ in\ G\}$ . Now I have to prove that $(B,\mathcal{F})$ is a matroid. The first ...
Norn0556's user avatar
1 vote
0 answers
20 views

Examples of Delta-Matroids in various branches of math

A delta-matroid is a generalization of a matroid. It is a set system $(E, \mathcal{F})$ with $\mathcal{F}\neq \emptyset$ satisfying the symmetric exchange axiom: $$ \forall X, Y \in \mathcal{F},\...
Mathieu Rundström's user avatar
0 votes
1 answer
47 views

Help undsersanding matroid closure, loops, contraction and duality.

These ideas are being used a lot, but I cannot justify why they are correct: If M is a matroid and $T$ a subset of $E(M).$ Then $$(a)\ cl(T) = T \cup \{e \in E(M) - T: e \text{ is a loop of M/T}\}.$$ ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
141 views

No minors isomorphic to $U_{0,1}$ and $U_{1,2}.$

I am trying to find all the matroids having no minors isomorphic to $U_{0,1}$ and $U_{1,2}.$ I know that the matroid $U_{0,n}$ is a matroid of rank zero with n edges and so it is just a vertex with n ...
Hope's user avatar
  • 95
0 votes
1 answer
59 views

Contraction, loops and flats.

This idea is being used a lot, but I cannot justify why it is correct: If M is a matroid and $T$ a subset of $E(M).$ Then $M/T$ has no loops iff $T$ is a flat of $M.$ I know how to proof that in a ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
46 views

The basis of a regular matroid.

I know that a regular matroid is one that can be represented by a totally unimodular matrix. I also know that a rank r totally unimodular matrix is a matrix over $\mathbb R$ for which every submatrix ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
56 views

affine geometries that are self-dual matroids.

I want to know which of the affine geometries $AG(n,q)$ are self-dual matroids? I have proved before that uniform matroids $U_{n,m}$ that are self duals are those who satisfies that $m = 2n.$ I am ...
Intuition's user avatar
  • 3,181
3 votes
1 answer
95 views

Understanding how to find the dual of a matroid.

I am trying to understand the following picture of a matroid and its dual but I found myself not understanding exactly what we are doing to find the dual: ]1 Roughly speaking, according to some ...
Hope's user avatar
  • 95
1 vote
0 answers
49 views

A Matroid Exchange Property

Let $(E,I)$ be a matroid, and let $A,B \in I$ be disjoint independent sets in the matroid. Moreover, let $B_1,\ldots, B_k$ be a partition of $B$. I could not decide if the following is always true. ...
John's user avatar
  • 193
0 votes
1 answer
64 views

if $X$ is independent and $E(M) - X$ is coindependent, show that $X$ is a basis and $E(M) - X$ is a cobasis.

here is the question I am trying to solve: In a matroid $M,$ if $X$ is independent and $E(M) - X$ is coindependent, show that $X$ is a basis and $E(M) - X$ is a cobasis. I know how to prove that a set ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
60 views

What is the definition of affine independence then?

The following is the definition of affine dependence (This definition is from James Oxley book, second edition "matroid theory") Definition of affine dependence: A multiset $\{ \underline{...
Emptymind's user avatar
  • 2,069
0 votes
1 answer
36 views

Let $A\subset B$ be flats of a matroid $M$ such that $r(A)=r(B)<\infty$. Then $A = B$.

I want to prove the following lemma: Let $r$ denotes the rank. Lemma. Let $A\subset B$ be any flats of a matroid $M$ such that $r(A)=r(B)<\infty$. Then $A = B$. My thoughts are: I know that $cl(A) =...
Intuition's user avatar
  • 3,181
0 votes
1 answer
82 views

Proving that $ \beta(M) = \beta (M - e) + \beta (M /e).$

Here is the statement I am trying to prove: If $e \in E$ is neither a loop nor an isthmus, then $$ \beta(M) = \beta (M - e) + \beta (M /e).$$ Here are all the properties I know about the Crapo's beta ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
71 views

Why always the Crapo beta invariant value greater than or equal zero?

Here are the definitions of the Crapo beta invariant I know: My definition of the Crapo's beta invariant of a matroid from the book "Combinatorial Geometries" from page 123 and 124 is as ...
Intuition's user avatar
  • 3,181
2 votes
1 answer
155 views

If $e \notin C,$ then $C$ is the union of circuits of $M/e$

I want to understand why the following statement is true: Let $C$ be a circuit of a matroid $M.$ For e in $E(M)$: If $e \notin C,$ then $C$ is the union of circuits of $M/e.$ I understood why the ...
Intuition's user avatar
  • 3,181
0 votes
0 answers
40 views

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$ ...
Manatee Pink's user avatar
3 votes
0 answers
120 views

Largest number of disjoint subsets of certain cardinality in bipartite graph such that every vertex is matched

Given a bipartite graph $G=(V,E)$, where $V$ is partitioned into $A$ and $B$, how can I design an algorithm that runs in polynomial time, such that given a positive integer $n\in\mathbb{N}$, the ...
Vista0711's user avatar
0 votes
1 answer
83 views

Finding an $\mathbb R$-representation for $M^*.$

Here is something I want to learn ( Problem #2.2.7 in Matroid Theory, first edition( page 88 ) , by James Oxley: Finding an $\mathbb R$-representation for the dual matroid $M^*$ when $M$ is the vector ...
Intuition's user avatar
  • 3,181
0 votes
2 answers
120 views

Show that no row of $A$ contains exactly one non-zero entry.

Here is the question I am trying to tackle: Let $A$ be a non-zero matrix over a field $\mathbb F$ and suppose that $M[A]$ has no coloops. Show that no row of $A$ contains exactly one non-zero entry. ...
Intuition's user avatar
  • 3,181
2 votes
1 answer
87 views

prove that $M\big[ \frac{A_1}{A_2}\big] = M[A_1].$

Here is the question I am trying to tackle: For $i = 1,2,$ let $A_i$ be an $m_i \times n$ matrix over a field $\mathbb F.$ If every row of $A_2$ is a linear combination of rows of $A_1,$ prove that $M\...
Intuition's user avatar
  • 3,181
0 votes
1 answer
25 views

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:...
Manatee Pink's user avatar
0 votes
1 answer
94 views

Determining all self-dual uniform matroids.

I want to determine all self-dual uniform matroids; I know that the dual of a uniform matroid $U_{r,n}$ is $U_{n - r,n}$ by Example $2.1.4$ in James Oxley, second edition, "Matroid Theory". ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
46 views

The relation between contraction and deletion in a matroid.

Here is the relation I have seen a lot in the books, but I am not sure why it is always true: If $T \subseteq E(M)$ then $$M \setminus T = (M^* / T)^* \quad\quad (*)$$ I know that contraction is ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
65 views

Why every component of a loopless matroid is flat?

Why every component of a loopless matroid is flat? I know that the rank of a loop in a matroid is zero and I read that: A loop is an element of a matroid that is not contained in any independent set (...
Intuition's user avatar
  • 3,181
0 votes
1 answer
107 views

The relation between the closure and the contraction of a matroid M.

Here is the relation I am trying to justify: $cl_{ M/T}(X) = cl_M(X \cup T) - T$ for all $X \subseteq E - T.$ Why this relation true? Any proof will be greatly appreciated! **Here are all what I know ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
114 views

Why does the greedy algorithm work when simplifying fractions?

Suppose we have a fraction $\frac{A}{B}$ and want to find a (possibly different) way $\frac{a}{b}$ of writing the same fraction, where $a$ and $b$ are as small as possible. In primary school we learn ...
Vincent's user avatar
  • 10.7k
0 votes
1 answer
44 views

$e \in C,$ then $e$ is a loop of $M,$ or $C - e$ is a circuit of $M/e.$

Here is the relation I am trying to understand Let $C$ be a circuit of a matroid $M.$ For e in $E(M)$: If $e \in C,$ then $e$ is a loop of $M,$ or $C - e$ is a circuit of $M/e$ ( M contract e). Does ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
164 views

circuit and a cocircuit can not have an odd number of common elements.

Here is the question I am trying to solve: Show that, in a binary matroid, a circuit and a cocircuit can not have an odd number of common elements. Here are the required definitions: A binary matroid ...
user avatar
1 vote
1 answer
111 views

If $X \subseteq Y$ and $r(X) = r(Y),$ then $cl(X) = cl(Y).$

Here is the question I am trying to understand its solution: Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following: $(e)$ If $X \subseteq Y$ and $r(...
Emptymind's user avatar
  • 2,069
1 vote
0 answers
64 views

Proving that $r(cl(X) \cup cl(Y)) = r(cl(X \cup Y))$.

Here is the question I am trying to prove: Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following: $(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
Emptymind's user avatar
  • 2,069
1 vote
1 answer
89 views

proving that $r(X \cup cl(Y)) = r(cl(X) \cup cl(Y)).$

Here is the question I am trying to prove: Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following: $(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
Emptymind's user avatar
  • 2,069
0 votes
1 answer
92 views

proving that $r(X \cup Y) = r(X \cup cl(Y)).$

Here is the question I am trying to prove: Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following: $(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
Emptymind's user avatar
  • 2,069

1
2 3 4 5
8