Questions tagged [posets]

A poset or partially ordered set is a set endowed with a partial order, meaning a binary relation $\leq$ which is reflexive ($x \leq x$ for all $x$), antisymmetric ($x\leq y$ and $y\leq x$ implies $x=y$), and transitive ($x\leq y$ and $y\leq z$ implies $x \leq z$).

Filter by
Sorted by
Tagged with
3
votes
1answer
371 views

Are there overwhelmingly more finite posets than finite groups? [closed]

A function $f:\mathbb{Z}_{\geq 1}\to\mathbb{Z}_{\geq 1}$ overwhelms $g:\mathbb{Z}_{\geq 1}\to\mathbb{Z}_{\geq 1}$ if for any $k\in \mathbb{Z}_{\geq 1}$ the inequality $f(n)\leq g(n+k)$ holds only for ...
1
vote
0answers
89 views

Free monoids on posets

I've suddenly found myself working with some free monoids $F(S)$ in which the set $S$ is a poset, and the order extends to an order $F(S)$, satisfying if (but not only if) $s_1, s_2, \ldots, s_r, t_1, ...
26
votes
1answer
710 views

Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?

Zorn’s Lemma applies to posets in which every chain has an upper bound. However, in all applications I know, the poset is also evidently chain-complete — chains have least upper bounds. A few ...
3
votes
0answers
83 views

What do you call such a relation between subsets in a poset

Consider a poset $(X, \geq)$. Let's define a new relation $\succsim$ on subsets of $X$: for $A, B\subseteq X$, say $A\succsim B$ if for any $a\in A$ and any $b\in B$, we have $a\geq b$. Does such a ...
8
votes
1answer
576 views

What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...
6
votes
1answer
373 views

What is the Möbius function of substrings?

Define a poset on the set of all finite binary strings, defined by $a \le b$ whenever $b = uav$ for (possibly empty) binary strings $u, v$. What is the Möbius function of this poset?
7
votes
1answer
99 views

Tameable hypergraphs

Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$. We say that $H$ is tameable if every independent set is contained in a maximal ...
3
votes
0answers
122 views

Does every finite lattice embed into a finite Eulerian lattice?

A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,...
10
votes
3answers
890 views

Listing all posets on 9 points?

I'm looking for a list of all (non-isomorphic) posets on 9 points. I know there are 183231 of them (OEIS A000112), but in order to progress with a problem I'm working on, I'd need the posets ...
3
votes
1answer
145 views

${\frak b}$ and ${\frak d}$ in the Rudin-Keisler preordering

If $(Q,\leq)$ is any preordered set (that is, $\leq$ is a reflexive and transitive, but not necessarily anti-symmetric relation), then we say that $S\subseteq Q$ is unbounded if for all $q\in Q$ ...
1
vote
1answer
78 views

Minimizing the set of monochromatic edges

For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$. Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...
6
votes
1answer
166 views

Sum of order polynomials of a set of posets

Let $n\in \mathbb{Z}_{>0}$. For every subset $S\subseteq \left[ n-1\right]$ we define a poset $P_S=\left([n],\le_{P_S}\right)$ given by the covering relation $\lessdot$ which is defined as \begin{...
4
votes
1answer
144 views

Can one characterize maximal antichains in terms of distributive lattices?

This is inspired by the recent question Verification of a maximal antichain The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them ...
8
votes
1answer
231 views

Verification of a maximal antichain

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ...
1
vote
0answers
99 views

Complexity of a poset

Let $M$ be a an integer $s \times s$ matrix. Define the complexity of $M$ as $cx(M):= \inf \{ n \geq 0 | \exists C \in \mathbb{N} , \ \forall t \in \mathbb{N} : \| M^t \| \leq C t^{n-1} \}$. Here $\| ...
15
votes
1answer
578 views

Suprema of directed sets

Let $(X, \le)$ be a partially ordered set. We call a subset $S \subseteq X$... ... a chain if each two elements in $S$ are comparable with respect to $\le$ (in other words, $S$ is linearly ordered ...
3
votes
0answers
51 views

Is the outer automorphism group of a finite poset finite when the Coxeter matrix has finite order?

Let $P$ be a finite connected poset. The Cartan matrix $C_P$ of $P$ is defined as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else for $i,j \in P$. The Coxeter matrix of $P$ is ...
1
vote
0answers
93 views

On the order of the Coxeter matrix of a poset

Let $P$ be a finite connected poset. The Cartan matrix $C_P$ of $P$ is defined as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else for $i,j \in P$. The Coxeter matrix of $P$ is ...
5
votes
0answers
133 views

Is this a counterexample to a conjecture on weakly periodic Coxeter matrices?

It seems I found an easy counterexample to a conjecture, but most often I did a stupid mistake or misunderstood the conjecture when this happens. Maybe someone can see whether this indeed is a ...
5
votes
2answers
337 views

Non-homeomorphic connected $T_2$-spaces with isomorphic topology poset

What are examples of non-homeomorphic connected $T_2$-spaces $(X_i,\tau_i)$ for $i=1,2$ such that the posets $(\tau_1, \subseteq)$ and $(\tau_2,\subseteq)$ are order-isomorphic?
5
votes
1answer
126 views

Outer automorphism group of posets

Let $X$ be a finite poset (we can assume it is connected) and $A_K(X)$ the incidence algebra of $X$ over a field $K$. The following result is well known, see for example corollary 7.3.7 in the book &...
4
votes
0answers
131 views

Finite pre-orders embeddable in the Rudin-Keisler ordering

$\DeclareMathOperator{\NPU}{\operatorname{NPU}}\DeclareMathOperator{\RK}{\,\mathrm{RK}}$A pre-ordered set is a pair $(P, \leq)$ where $P$ is a set and $\leq\subseteq P\times P$ is a reflexive and ...
17
votes
3answers
617 views

What is the minimum size of a partial order containing all partial orders of size 5?

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. ...
11
votes
0answers
204 views

Does every finite poset have a rigid endomorphism?

Crossposted on Mathematics. In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
5
votes
0answers
105 views

Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph

This question is very important for my research, which is why I ask it here. I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
0
votes
1answer
87 views

Using a poset or directed graph as input for a neural network [closed]

I'm not sure if this is the right community to post this in but I would appreciate any help. As the title states, I'm trying to train a neural network using some unconventional input. I'm wondering if ...
9
votes
2answers
195 views

Integer decomposition property with a partial order

Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...
4
votes
1answer
137 views

Maximal order of an order-preserving map

Let $X$ be a finite partially ordered set, let $f\colon X\to X$ be an order-preserving map [edit: meaning $x\le y\implies f(x)\le f(y)$], and let $x_0$ be an initial point. Define $x_n = f(x_{n-1})$ ...
23
votes
1answer
889 views

Expected height of a poset?

I am interested in any known results/empirical studies done on the average height of a poset with $N$ elements. Obviously this would depend on how that poset relation was randomly defined, however, at ...
3
votes
0answers
184 views

Poset of antichains of given cardinality

Throughout all posets will be finite. Let $P$ be a poset, and let $\mathcal{A}(P)$ denote the set of antichains of $P$. We give $\mathcal{A}(P)$ a partial order whereby $A \leq A'$ iff for all $x \in ...
7
votes
1answer
161 views

Trace of a matrix associated to posets

Let $P$ be a finite connected poset with $n$ elements. Let $C=(c_{x,y})$ be the $n \times n$ matrix with entry 1 in case $x \leq y$ and 0 else. The Coxeter matrix of $P$ is defined as the matrix $M_P=-...
5
votes
1answer
116 views

On the width of the Catalan monoid and the rank of K-groups of the Furstenberg transformation group

The semigroup algebra of the Catalan monoid is isomorphic to the incidence algebra of $P_n$, where $P_n$ is the poset consisting of subsets of { 1,...,n } where for two subsets $X \leq Y$ if and only ...
4
votes
1answer
241 views

A meet-semilattice with top element that is not a lattice?

I am reading Francis Borceux’s “Handbook of Categorical Algebra I” and on page 135 it says In particular a finite version of 4.2.5 does not hold: a finitely complete and well-powered category ...
8
votes
0answers
130 views

Periods of Coxeter transformation associated to root posets

$\DeclareMathOperator\Co{Co}$Let $P$ be the root poset associated to a simple Lie algebra. Let $L=L(P)$ denote the distributive lattice of order ideals of $P$ and let $\Co_L$ denote the Coxeter matrix ...
2
votes
0answers
78 views

When are quotients of the Boolean lattice dissective?

Let $B_n$ be the Boolean lattice and $G$ a subgroup of $S_n$ acting on $B_n$. Let $P_G=B_n/G$ denote the quotient poset. Question 1: When is $P_G$ a lattice? When is it distributive in that case? An ...
6
votes
0answers
124 views

Classification of posets that are quotient posets of the Boolean lattice

Quotient posets of the Boolean lattice $B_n$ have interesting properties and are for example discussed in chapter 5 of Stanley's book on algebraic combinatorics. $B_n/G$ for a subgroup $G$ of the ...
4
votes
0answers
125 views

Factorisation of a polynomial from the Boolean algebra

Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$. Let $M_n:=C_n+C_n^T$ and $...
0
votes
0answers
49 views

Given multiple posets, what is the probability that a randomly selected (uniform dist) subposet of their product has a max under the product order?

Given multiple totally ordered posets, how do I find the probability that a randomly selected (with uniform distribution) subposet of their product has a maximum under the product order? I have some ...
4
votes
1answer
219 views

Not sure whether I find a counterexample to poset fiber theorem

I am trying to implement Theorem 1.1 in the paper "Poset Fiber Theorems" by Bjorner, Wachs, and Welker. https://www.researchgate.net/publication/228782786_Poset_fiber_theorems I am pretty ...
4
votes
0answers
50 views

Which posets can occur from commutative Frobenius algebras?

Let $A$ be a commutative Frobenius algebra. We can assume that $A$ is local and $A=K[x_i]/(I)$ for some variables $x_1,...,x_n$ and an admissible ideal. Then the non-zero monomials $u_i$(including 1) ...
6
votes
2answers
312 views

Group structure for distributive lattices

On the (finite) Boolean lattice there is a group structure given by the symmetric difference and this group is an elementary abelian 2-group. Question: Does there exist a natural group structure on ...
9
votes
0answers
206 views

Distributivity of certain infinite products

Suppose we have a sequence of posets $\{\mathbb P_n : n\in\omega\}$ such that for each $n$, $\mathbb P_{n+1}$ is $|\mathbb P_n|^+$-distributive. Is $\prod_{n>0} \mathbb P_n$ necessarily $|\mathbb ...
3
votes
0answers
90 views

Shellability and order filters in the partition lattice

Choose $n\in\mathbb N$. Let $B$ be a non-empty subset of $[n]:=\{1,2,\dots,n\}$. Consider the set of partitions of the set $[n]$ with exactly $|B|$ parts such that each part has exactly one member ...
2
votes
0answers
86 views

Non-commutative version of the order dimension of a poset

I view the order dimension of a poset $P$ as an inherently commutative notion. On the one hand, it can be defined via realizers, which I find fairly intuitive from an order-theoretic viewpoint. On the ...
4
votes
2answers
197 views

The average size of downward closed family of the subsets of $[n]$ is at most $n/2$?

I learned that the average size in any ideal of subsets of $[n]$ is at most $n/2$, but I think the downward closed family of the subsets of $[n]$ also satisfied. I want to know how to proof it or it ...
1
vote
0answers
29 views

Posets which extend centered sets to filters

(Post cross-posted from math.se.) Suppose $(\mathcal O, \leq)$ is an arbitrary poset. Let us say that $\mathcal O$ is compact if every $\mathcal C\subseteq\mathcal O$ which is centered (any finite ...
1
vote
0answers
92 views

Do you recognise this setup of structure on a poset?

The setup is that we have a finite poset $P$, with a multiplicative rank function $r_{xy}:P\times P\rightarrow \mathbb{N}$, and a symmetric pairing $\langle\ ,\ \rangle:P\times P\rightarrow\mathbb{N}$....
10
votes
1answer
313 views

Poset-troids …?

In many respects, spanning tree : graph :: linear extension : poset For instance, the number of spanning trees/linear extensions is a measure of the "richness" or "complexity" of the graph/poset. ...
0
votes
0answers
43 views

Number of minimal elements of product order

Consider three sets: $A = \{1,2,\dotsc,n_A\}$, $B=\{1,2,\dotsc,n_B\}$, and $C=\{1,2,\dotsc,n_C\}$, where $n_A, n_B, n_C \ge 2$. Define a product order (which is a partial order) on the cartesian ...
0
votes
2answers
77 views

Is this ordering on the set of all covers of $\omega$ a (complete) lattice?

Let ${\frak C} \subseteq {\cal P}({\cal P}(\omega))$ be the collection of all covers of $\omega$ (that is, ${\cal C} \in {\frak C}$ iff $\bigcup {\cal C} = \omega$.) We define the following binary ...

1
2 3 4 5
7