4
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Can you give some examples that do not arise from posets? $\endgroup$
    – Andrej Bauer
    Commented 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$
    – Dan Petersen
    Commented 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$
    – Dasha Poliakova
    Commented 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$
    – Dasha Poliakova
    Commented 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$
    – Dasha Poliakova
    Commented Dec 10, 2021 at 21:08

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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