27
$\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$
  • 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 '17 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$ – Louis Deaett Oct 31 '17 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$ – Gerhard Paseman Oct 31 '17 at 0:44
  • 3
    $\begingroup$ @Will Jagy - I was thinking more of goodreads.com/book/show/18209408-have-you-seen-my-dragon $\endgroup$ – Nicholas Proudfoot Oct 31 '17 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 '17 at 2:30
12
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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 '17 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, this is a pretty reasonable formula! Certainly well suited to putting into a generating function. $\endgroup$ – Nicholas Proudfoot Oct 31 '17 at 3:11

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.