5
$\begingroup$

Consider a finite graded poset $\Gamma$ and assign to each maximal element $z\in \Gamma$ a variable $\mu(z)$. I want to solve the system of equations (minimally, I want to compute its rank, ideally, obtain an explicit basis)

$$\sum_{w\leqslant z} \mu(z) = 0.$$

That is, for each $w\in \Gamma$, the weight assigned to the maximal elements that lie over it must sum to zero. (I'm excluding the maximal elements themselves, of course.)

Note that one can write any linear system in terms of a bipartite graph by assigning the equations into one group of vertices of the graph, the variables to the other, and joining an equation to a variable if such variable appears in the chosen equation. One then chooses $\mu(z)$ accordingly and the equations above are precisely those of the linear system (consider a bipartite graph as a poset in the obvious way). In such a sense, this problem is as broad as it gets.

The following extra information may (or may not) help narrowing it down.

To be more concrete, the problem arises as follows. Fix a combinatorial species $P:\mathsf{Set}^\times\longrightarrow \mathsf{Set}$ (a functor) with restrictions, that is:

  • For each finite set $I$ and each subset $S$ of $I$, there is an arrow $$(?)_S : P(I)\to P(S)$$
  • These arrows are compatible in the sense they form a sheaf over finite sets and injections of subsets, and bijections:
    • If $T\subseteq S\subseteq I$ then $((?)_S)_T = (?)_T$
    • For every $I$, $(-)_I ={\rm id}_I$
    • For every bijection $\sigma : I \longrightarrow J$ and every subset $S$ of $I$, $$(P(\sigma)(?))_{\sigma(S)} = P(\sigma)((?)_{S})$$

Using this data one can form, for any finite set $I$, a poset $\Gamma(I)$ as follows. The underlying set of $\Gamma(I)$ is the collection of $P$-structures on subsets of $I$:

$$\Gamma(I) = \bigcup_{S\subseteq I} P(S).$$

We define a partial order on $\Gamma(I)$ so that $z\leqslant w$ if

  • The support of $z$ is contained in that of $w$: $z\in P(S)$ and $w\in P(T)$ with $S\subseteq T$,
  • $z$ is obtained by restricting $w$ to $S$: $z= (w)_S$

Note that $\Gamma(I)$ is graded by the cardinality of the support of a structure. Thus, for each subset $S$ of $I$ I want to solve the system of equations

$$\sum_{z:(z)_S=w} \mu(z) = 0$$

as $z$ ranges through $P(I)$. To give even a more concrete example, I have computed a few values of the dimension $d_n$ ($n=\# I$) of solutions of the above for $L$ the species of linear orders, and $d_n$ coincides with the derrangement sequence $1,0,1,2,9,44,\ldots$.

Variants of this poset have been studied here

https://arxiv.org/pdf/0902.4011v3.pdf

for example. One option is inverting (after suitably defining $\mu(w)$ for every other $w\in \Gamma$) the equations above to obtain recurrences, but I would expect that the calculation of the Möbius function of an arbitrary poset like the above is not easy at all (as the cited paper shows).

One can fix a ring $k$ and linealize the category of species with restrictions by postcomposition with the free functor to $k$-modules. This category is in fact the category of (left) comodules over a fixed (linealized) species, the exponential species, and it is monoidal with a particular product (the Cauchy product). The problem above amounts to computing the cotensor product of $P$ with the unit for this monoidal structure.

$\endgroup$

1 Answer 1

2
$\begingroup$

A comment on the problem. This doesn't solve the problem but was too long for a comment.

Let $\mathrm{FGP}$ denote the category of finite graded posets with morphisms the graded morphisms of posets and $\mathrm{BG}$ be the full subcategory whose objects are "graded" bipartite graphs, i.e. the grading can only take two values, $0$ or $1$. Given a finite graded poset $\Gamma$, one can associate a graded bipartite graph $B(\Gamma)$ with the same underlying set but the poset relation is given by

$x <_{B(\Gamma)} y \quad \Longleftrightarrow \quad x <_{\Gamma} y$ and $y$ is a maximal element of $\Gamma$.

Since the equations you build are not affected by relations between non-maximal elements, the set of equations given by $\Gamma$ and $B(\Gamma)$ is the same. Furthermore, $B : \mathrm{FGP} \to \mathrm{BG}$ can be turned into a functor in the obvious way. Let $B_* : \mathrm{BG} \to \mathrm{FGP}$ denote the inclusion map. If we add the condition in this definition of a graded poset that the minimal value of the rank is $0$, then $B \circ B_* = \mathrm{id}_{\mathrm{BG}}$, so $B$ is a retraction which preserves your problem.

You can turn the pair $(B_*,B)$ into an adjoint pair if you choose a relaxed definition for the morphisms in $\mathrm{FGP}$, namely that a map of posets $f : P \to Q$ is a morphism in $\mathrm{FGP}'$ if it maps maximal elements to maximal elements and non-maximal elements to non-maximal elements. This is the same as being a graded morphism of posets for a map between two bipartite graphs, but you will have the problem that if $X$ is finite graded bipartite and $Y$ is finite graded not bipartite (i.e. the rank function takes at least $3$ values), there are no morphisms from $X$ to $Y$ which sends maximal elements of $X$ to those of $Y$, hence $\mathrm{Hom}_{\mathrm{BG}}(X,B(Y))$ might not be empty but $\mathrm{Hom}_{\mathrm{FGP}}(B_*(X),Y) = \varnothing$. Taking $\mathrm{FGP}'$ instead of $\mathrm{FGP}$, the pair $(B_*',B')$ where $B' : \mathrm{FGP'} \to \mathrm{BG}$ and $B_*' : \mathrm{BG} \to \mathrm{FGP'}$ are defined analogously is adjoint. This is not natural from the point of the grading but it is from the point of view of your problem.

I could have just said "you can restrict your attention to bipartite graphs", but since you deal with species, I wanted to show you it can actually be done functorially. What you mentioned in your question is that if $X$ is a finite graded poset and $F(X)$ the associated linear system, then $F(X) = F(X')$ for some graded bipartite graph $X'$. What I'm saying is that $F(X) = F(B(X))$, so I'm a bit more specific (but I'm essentially saying the same thing in a different language).

Hope that helps,

$\endgroup$

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.