I am looking for a name of a certain structure, which is a generalization of poset that admits non-binary comparisons.

Let $P$ be a set equipped with operations, for $n\geq2$, $$ C_n: P^n \to \{True, False\}$$ such that

  1. $(P,C_2)$ is a poset
  2. $C_n(p_1,\ldots,p_n) = True$ implies $C_k(p_{i_1},\ldots,p_{i_k}) = True$ for any $1\leq i_1< \ldots<i_k \leq n$.
  3. Some higher transitivities that I'm struggling to formulate.

Note that the converse of 2 does not need do hold!

Having a poset, you can build a structure like this by saying that $C_n(p_1,\ldots,p_n) = True$ if for all $i$ you have $C_2(p_i,p_{i+1}) = True$. In this case, chains $(p_1, \ldots, p_n)$ satisfying $C_n(p_1,\ldots,p_n)= True$ are just chains in your poset, and converse to 2 holds. But not every "higher poset" arises this way.

Question: have you ever seen these structures? How are they called? Where can I read about them?

  • 1
    $\begingroup$ Can you give some examples that do not arise from posets? $\endgroup$ Dec 10, 2021 at 20:10
  • 1
    $\begingroup$ It sounds to me like you're describing an abstract simplicial complex, equipped with the extra structure of a directed acyclic graph on its 1-skeleton. $\endgroup$ Dec 10, 2021 at 20:47
  • $\begingroup$ 2Andrej (1): In my example of interest, the higher poset will be a generalization of Bruhat poset of permutations. My set P will consist of all ordered partitions of n elements (aka faces of permutahedron, aka nestings = filtrations on the set {1,2,...,n}). Let D(n) be the set of pairs (I,J) where I and J are non-intersecting subsets of {1,2,...,n} of the same cardinality with min(I + J) in I. $\endgroup$ Dec 10, 2021 at 21:07
  • $\begingroup$ 2Andrej (2): By a theorem of Laplante-Anfossi, summands of Saneblidze-Umble diagonal on permutahedra can be described as pairs of nestings (N,M) such that for every (I,J) in D(n) at least one of the following holds: either there exists a nest N' in N such that |N'∩I|>|N'∩J| or there exists a nest M' in M such that |M'∩I|<|M'∩J|. We then say C_2(N,M)=True. (Note that it's a suitable generalization of Bruhat order on vertices). $\endgroup$ Dec 10, 2021 at 21:08
  • $\begingroup$ 2Andrej (3): Now let's say that C_n(N(1),... ,N(k)) = True if at least on of k options holds, where option #k sounds like this: There exists a nest N'(i) in N(i) for every i not equal to k, where |N'(i)∩I| > |N(i)∩J| if i<k and |N'(i)∩I| < |N(i)∩J| if i>k. Then C_n's should assemble into the structure that I'm interested in, where converse of axiom 2 fails (example: C_3(2|1|34,2|14|3, 24|13) = False but True for all pairs). $\endgroup$ Dec 10, 2021 at 21:08

1 Answer 1


Though not exactly the same what you're asking, there is the concept of oriented matroids, especially when described through chirality: https://en.wikipedia.org/wiki/Oriented_matroid#Chirotope_axioms
There is also a nice book by Knuth that discusses similar systems of axioms: https://www-cs-faculty.stanford.edu/~knuth/aah.html


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.