inequivalent vertex weights on finite poset

Question

Let $m\geq1$ and $P$ be an arbitrary poset with vertex set $V=\{v_1,\dots,v_n\}$, edge set $E,$ and set $O$ of orbits under $\text{Aut}(P).$ Can we efficiently generate all inequivalent nonnegative weight assignments $\alpha:V\to\mathbb{N}$ such that $\sum_{i=1}^n\alpha(v_i)=m$ from this information alone or do we need all inequivalent $\alpha$ with sum $\leq m$ for all $|P|<n?$ My goal is to obtain them for every $P$ (up to isomorphism) with $|P|\leq10$.

If an inductive procedure is needed, maybe it will involve something along the following lines.

Fix an orbit $o\in O$ and weight assignment $\alpha$ on $V\setminus o$ with sum $m-m'.$ For each $v\in o$ and orbit $o'\neq o,$ let $N_\alpha(v,o',w)$ be the number of incoming edges to $v$ from vertices in $o'$ with weight $w.$ For each $v_i,v_j\in o$ we set $v_i\sim_{o'}v_j$ iff $N_\alpha(v_i,o',w)=N_\alpha(v_j,o',w)$ for all $w\geq0,$ and $v_i\sim v_j$ iff $v_i\sim_{o'}v_j$ for all $o'\neq o.$

Let the equivalence classes under $\sim$ have cardinalities $a_1,\dots,a_h.$ For each composition $(c_1,\dots,c_h)$ of $m'$ with nonnegative parts (one part to each class), we compute all possible combinations of partitions of $c_i$ with $a_i$ nonnegative parts (one part to each vertex).

I think the weight assignments produced by these partitions will be inequivalent, as will the entire collection obtained by repeating the above for all inequivalent $\alpha\text{'s}$ on $V\setminus o,$ but major issues remain such as how do we choose $o,$ etc.

Answer 1

Let's see if I understand the question. You have a vertex set $V$ with an automorphism group $G$. You want to assign a nonnegative integer weight to each vertex, with sum fixed to $m$, and you want to list all possible weight assignments when two assignments related by an element $g\in G$ are considered equivalent. Also, you want this to be efficient. I don't know if it helps to know that $V$ is also a poset, so let us just consider it as set that has a group acting on it.

A practical way of doing this is available in Sage module Integer vectors modulo the action of a permutation group. Here is an example, with $V=B_2$ the Boolean lattice on a ground set of two elements (so $|V|=4$), and $m=3$. Note that, due to the automorphism group, the second and third elements are in symmetric position, so for example $[2,0,1,0]$ is not listed because it is equivalent to $[2,1,0,0]$.

sage: V = posets.BooleanLattice(2); sage: G = V.hasse_diagram().automorphism_group(); sage: v = IntegerVectorsModPermutationGroup(G, 3); sage: display(list(v)) [[3, 0, 0, 0], [2, 1, 0, 0], [2, 0, 0, 1], [1, 2, 0, 0], [1, 1, 1, 0], [1, 1, 0, 1], [1, 0, 0, 2], [0, 3, 0, 0], [0, 2, 1, 0], [0, 2, 0, 1], [0, 1, 1, 1], [0, 1, 0, 2], [0, 0, 0, 3]] 

Whether this is efficient enough for you I don't know, in particular because I don't know how big $m$ you are considering. It works in ~10 seconds for the $B_4$ lattice (16 elements) and $m=10$, listing 155004 assignments. You could inspect the algorithm from the source code and decide if you want to implement it in a more efficient language. At least this gives you a working baseline. The algorithm is described in Nicolas Borie, FPSAC 2013, Generation modulo the action of a permutation group. The paper has this absolute gem of a statement: "This problem is not well solved in the literature."

If you do not need to list the vectors, but only need their count, then you should consider Redfield-Pólya counting instead. That is much faster and can handle (practically) any $m$ you wish.