0
$\begingroup$

I am doing an assignment where I have to proof that every uniform matroid is a transversal matroid. My solution is a lot simpler than in the solutions manual, and normally this means that my solution is wrong. I just don't understand why. Is the following proof correct, and if not why?

First, the definitions:

Uniform matroid Given a set $E$ of size $n$ and a number $k \leq n$, the uniform matroid of rank $k$ has independent sets $J = \{I \subseteq E : |I| \leq k\} $

Partial Transversal Let $A$ be a family of subsets of a finite set $X$. A subset $I = \{ x_1,..,x_{|I|}\}$ of $X$ is called a partial transversal of $A$ if there are different sets $a_1,...,a_{|I|} \in A$ such that $x_i \in a_i$ for each $x_i$

Transversal matroid A matroid where the independent sets are the set of partial transversals

The question:

Proof that any uniform matroid is a transversal matroid.

My solution:

With set $E = \{1,..,n\}$

Take $A = \{\{i\} : i = 1,..,n\}$

Now for any independent set $I$ of the uniform matroid, each element of $I$ is in one of the sets of $A$.

I have a feeling i am completely misunderstanding the basics of a transversal matroid and missing something very obvious why my solution must be wrong, but i have no idea what it is.

$\endgroup$
1
$\begingroup$

The question is old, but in case you're still looking for the answer:

Every independent set of the rank $k$ uniform matroid on $E$ is a partial transversal of $A$. However, there are more transversals of $A$, in particular $E$ itself. Thus, $A$ is a presentation for the uniform matroid of rank $|E|$.

The rank $k$ uniform matroid is presented by the set system $A_i = E$ for $i=1,\ldots,k$. There are other smaller presentations, but this is the largest possible presentation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.