Is the following is a matroid

  • Thread starter jetoso
  • Start date
73
0
I would like to know if the following is a matroid:
Matroid: a matroid M on a ground set E is a pair (S, l), where l is a collection of subsets of S (called the independent sets) with the following properties:
1. The empty set is independent.
2. Every subset of an independent set is independent; this is sometimes called the hereditary property.
3. If A and B are two independent sets and A has more elements than B, then there exists an element in A which is not in B and when added to B still gives an independent set; this property is called the exchange property.


1. Let G=(V,E) be an undirected graph. Let the set S=E and the independent sets corresponding to acyclic subgraphs with at most two edges is a subset.
 

fresh_42

Mentor
Insights Author
2018 Award
10,721
7,332
A good point to start with would be a few examples. This also often guides a way to an answer.
 

Want to reply to this thread?

"Is the following is a matroid" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top