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\}$.

Improve this question
$\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.
    Commented 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$
    – Louis Deaett
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Nicholas Proudfoot
    Commented 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.
    Commented Oct 31, 2017 at 2:30

2 Answers 2

Reset to default
15
$\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.

Improve this answer
$\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
    Commented 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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .