What is the difference between matriods and hypergraphs?

350 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

Fix a finite set $S$. A hypergraph on $S$ is just a set system on $S$, that is, a collection of subsets $E$ of $S$. The subsets in $E$ are called the edges of $S$ and, for a general hypergraph, the edges don't need to exhibit any particular structure aside from being contained in $S$.

On the other hand a matroid on the set $S$ is a set system with a highly restrictive (and very useful) structure. For example, if we let $\mathcal{I}$ be the independent sets of a matroid on $S$, then $\mathcal{I}$ is a hypergraph (with empty edges allowed) such that (1) $\mathcal{I}$ is a simplicial complex and (2) the augementation property holds. These two properties imply that the inclusion-maximal independent sets (i.e., the bases of the matroid) all have the same size, while inclusion-maximal edges in an arbitrary hypergraph don't need to satisfy any relations.