0
$\begingroup$

I am looking for a specific matroid. I found a source that claimed to discuss these matroids, but then, only discusses geometric lattice. Even more, in that paper, the geometric lattice that seems to be the right one was described as

... the lattice associated with the Steiner system $S(3,6,22)$.

It might be clear to some, how to translate between all these different constructs, but I have a hard time finding any source explaining to me (in short) how these concepts are linked.

I suppose, that the matroid of the geometric lattice $\mathcal L$ is defined on the set of atoms of $\mathcal L$, and independence of atoms $a_1,...,a_n\in\mathcal L$ means that the supremum $a_1\vee \cdots \vee a_n$ has rank $n$. But this is just a guess. Furthermore, the lattice that comes from $S(3,6,22)$ is said to be of rank at least 3, but there is not much more said about this.

Can someone tell me how to obtain the matroid from $S(3,6,22$)?


There are actually two papers I am talking about:

$\endgroup$
  • 1
    $\begingroup$ Just to be clear: you want the matroid realized as a set of bases? (As you are probably aware from reading Wikipedia, geometric lattices and matroids are "the same things." There are many ways to formulate the axioms of matroids that turn out yield isomorphic- or 'cryptomorphic'- structures.) $\endgroup$ – Sam Hopkins Aug 12 at 14:58
  • $\begingroup$ Could you link to the paper you are reading, by the way? $\endgroup$ – Sam Hopkins Aug 12 at 14:59
  • $\begingroup$ @Sam Yes, I am interested in the bases. I am probably not aware of the exact way the cryptomorphism goes from lattices to matroids. $\endgroup$ – M. Winter Aug 12 at 14:59
  • $\begingroup$ It's hard to believe that the matroid is really rank 3, as the action of $M_{22}$ on 22 points is 3-transitive. $\endgroup$ – LeechLattice Aug 12 at 16:08
  • 1
    $\begingroup$ @M.Winter I tried to derive a paving matroid from $M_{22}$, and it turned out to have rank 4 and the permutation group $M_{22}$ on 22 points acting on it. $\endgroup$ – LeechLattice Aug 12 at 16:15
2
$\begingroup$

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 $∀y\in Y :(X \setminus a) \cup y \notin B$, it follows that all elements of $Y$ are in some block containing $X \setminus a$, and there's only one such block, call it $A$. It follows that $Y\subset A$, contradiction.

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

$\endgroup$
  • $\begingroup$ Does "all members of $Y$ can not be exchanged for $a$" mean what it literally says ($\forall b \in Y,\,\lnot(\text{$b$ can be exchanged for $a$})$), or its colloquial English meaning ($\lnot(\forall b \in Y,\,\text{$b$ can be exchanged for $a$})$)? $\endgroup$ – LSpice Aug 12 at 17:32
  • 1
    $\begingroup$ It means what it literally says. The answer is edited to avoid confusion. $\endgroup$ – LeechLattice Aug 12 at 17:34

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.