Skip to main content
3 of 4
\text{\\} -> \setminus
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Let $B$ be the subsets of $\{1,2,...,22\}$ of size $4$ which are not contained in any block of $S(3,6,22)$. $B$ satisfies the basis exchange property.

Proof:

Let $X,Y\in B$, $a\in X$. $X \setminus a$ is a 3-element set, so it is contained in exactly one block of $S(3,6,22)$. If all members of $Y$ can not be exchanged for $a$, it follows that all elements of $Y$ are in the block containing $X \setminus a$, which means $Y$ is the subset of the block by uniqueness. Contradiction.

Corollary. $B$ is the basis of a matroid with rank $4$.

LeechLattice
  • 9.5k
  • 2
  • 23
  • 57