29
$\begingroup$

Let $M(n,k)$ be the matroid on the ground set $\{\pm 1,\ldots,\pm n\}$ for which a set is independent if and only if it contains at most $k$ pairs $\pm i$. Note that the signed permutation group (the Coxeter group of type $B_n$) acts on this matroid. Questions:

  1. Does this matroid have a name?
  2. Has it been studied before?
  3. Is there a nice formula for its characteristic polynomial?

Here are some boring special cases:

  • $M(n,n)$ is the Boolean matroid on $2n$ elements.

  • $M(n,n-1)$ is the uniform matroid of rank $2n-1$ on $2n$ elements.

  • $M(n,0)$ is the direct sum of $n$ copies of the uniform matroid of rank 1 on 2 elements.

The first interesting case is $M(3,1)$, which has rank 4 and characteristic polynomial

$$q^4 - 6q^3 + 15q^2 - 17q + 7$$

I am also interested in truncations of this matroid. That is, let $M(n,k,d)$ be the matroid on the ground set $\{\pm 1,\ldots,\pm n\}$ for which a set is independent if and only if it contains at most $k$ pairs $\pm i$ and has size at most $d$. All of the same questions apply!

Remark: I would like to regard these matroids as type B analogues of uniform matroids. Uniform matroids are the permutation-invariant matroids on the ground set $\{1,\ldots,n\}$, while these are the signed-permutation-invariant matroids on the ground set $\{\pm 1,\ldots,\pm n\}$.

$\endgroup$
9
  • 3
    $\begingroup$ I hate to be a spoilsport but the title, while cute and attention-grabbing, is a bit too vague for my tastes. As it stands, a reader seeing the title on the main page or a reader that might see the title in the "Related" list on another question page will have no idea of what "your matroid" is like. $\endgroup$
    – j.c.
    Oct 30, 2017 at 21:14
  • 13
    $\begingroup$ @j.c.: Well, a quick search shows 47 questions with titles of the form "Does this ___ have a name?" Your criticisms would seem to apply to most of those titles as well. It doesn't seem quite obvious how to produce a more suitable title in such cases. (For that matter, "Does this matroid have a name?" was already taken.) $\endgroup$ Oct 31, 2017 at 0:22
  • 20
    $\begingroup$ Let us hope the answering post is titled "How I Met Your Matroid". Gerhard "Sometimes Just Can't Stop Himself" Paseman, 2017.10.30. $\endgroup$ Oct 31, 2017 at 0:44
  • 3
    $\begingroup$ @Will Jagy - I was thinking more of goodreads.com/book/show/18209408-have-you-seen-my-dragon $\endgroup$ Oct 31, 2017 at 1:30
  • 1
    $\begingroup$ @LouisDeaett Yes, it's not obvious at all, but still I think it's important! Every question with a vague title is a question that could be improved to be that much more helpful to someone searching for answers to the same question. Anyways, I won't belabor the point. I voted the question up by the way. $\endgroup$
    – j.c.
    Oct 31, 2017 at 2:30

2 Answers 2

14
$\begingroup$

Let $U$ be the uniform matroid of rank $k$ on $n$. Since $U$ is orientable one can consider the Lawrence oriented matroid $\Lambda(U)$ associated with any orientation of $U$ (the Lawrence construction doesn't care about which orientation you take). Then $M(n,k)$ is precisely the underlying unoriented matroid $\underline{\Lambda(U)}$ of $\Lambda(U)$.

Also, the dual matroid $M^*(n,k)$ is a symplectic matroid, which explains why the group $B_n$ acts on the primal.

$\endgroup$
1
  • 2
    $\begingroup$ $M(n,k)$ can be constructed by starting with the uniform matroid $U_{k,n}$, and then replacing each element with a series pair. Alternatively, $M^{*}(n,k)$ is constructed by starting with the uniform matroid $U_{n-k,n}$ and adding an element in parallel to each point of the uniform matroid. I'm not aware of any name for these classes in the matroid literature. $\endgroup$
    – Dillon M
    Nov 7, 2017 at 20:57
19
$\begingroup$

One can use Whitney's theorem to show that the characteristic polynomial is $$ \sum_{i=0}^k{n\choose i}q^{k-i}(q-2)^{n-i} + \sum_{i=k+1}^n{n\choose i}(q-2)^{n-i}. $$ I doubt that this can be simplified.

$\endgroup$
1
  • $\begingroup$ Thanks, this is a pretty reasonable formula! Certainly well suited to putting into a generating function. $\endgroup$ Oct 31, 2017 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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