free matroid

File:Free matroid.svg of a forest with 4 edges, which is the free matroid with a ground set of size 4 (also the uniform matroid $U\{\}^4\_4$). More generally, the graphic matroid of a forest with {{mvar|n}} edges is $U\{\}^\{n\}\_\{n\}$.]]

In mathematics, the free matroid over a given ground-set {{mvar|E}} is the matroid in which the independent sets are all subsets of {{mvar|E}}. It is a special case of a uniform matroid; specifically, when {{mvar|E}} has cardinality $n$, it is the uniform matroid $U\{\}^\{n\}\_\{n\}$.{{cite book

| last = Oxley | first = James G. | authorlink = James Oxley

| isbn = 9780199202508

| page = 17

| publisher = Oxford University Press

| series = Oxford Graduate Texts in Mathematics

| title = Matroid Theory

| volume = 3

| year = 2006}} The unique basis of this matroid is the ground-set itself, {{mvar|E}}. Among matroids on {{mvar|E}}, the free matroid on {{mvar|E}} has the most independent sets, the highest rank, and the fewest circuits.

Every free matroid with a ground set of size {{mvar|n}} is the graphic matroid of an {{mvar|n}}-edge forest.

{{cite book

| last = Welsh

| first = D. J. A.

| year = 2010

| title = Matroid Theory

| publisher = Courier Dover Publications

| page = 30

| isbn = 9780486474397

}}