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$).

learn more… | top users | synonyms

6
votes
1answer
71 views

Are these two quotients of $\omega^\omega$ isomorphic?

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$. For $f,g\in\omega^\omega$ we say $f\simeq_{\text{fin}} g$ if there is $n\in \omega$ such that $f(k) = g(k)$ for all $k\geq n$. ...
4
votes
0answers
75 views

Face structures of chain polytopes

For a finite poset $P$ the chain polytope $\mathscr C(P)\subset\mathbb{R}^P$ consists of such $g$ that $g(p)\ge 0$ for all $p\in P$ and $$g(p_1)+\ldots+g(p_n)\le 1$$ for any chain ...
3
votes
1answer
143 views

Can a length n distributive lattice be embedded into Bn?

Let $\mathcal{L}$ be a finite distributive lattice, then it is known that it can be embedded into a finite boolean lattice (see theorem 8.5. p91 in this note). Let $n$ be the length of ...
3
votes
0answers
81 views

Weighted maximal number of disjoint singly-generated ideals in the divisibility poset for $\{1,2,\ldots,n\}$

In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual ...
3
votes
2answers
92 views

What are bounds for the number of monotone functions $M:P\rightarrow T$ where $P$ is a finite poset and $T$ is a finite totally ordered set?

For the case where $P=\{0,1\}^n$ and $T=\{0,1\}$ the number of such functions is called the $n$-th Dedekind number and I discovered that there is large literature on determining bounds for these ...
5
votes
0answers
74 views

Minimal Hausdorff topologies compatible with a bunch of functions

Let $X$ be an infinite set, let ${\cal F}$ be a set of functions $f: X\to X$. We say that a topology $\tau$ is compatible with ${\cal F}$ if every $f\in {\cal F}$ is a continuous function $f:(X, ...
1
vote
0answers
27 views

Form of binary function over poset that is monotone over first and antitone over second argument

if I have a partially ordered set $P$, and I have a function $f: P \times P \to \mathbb{R}$ that is monotone over the first and antitone over the second argument, i.e. for any $a,b,c \in P$ $a ≤ b ...
1
vote
0answers
71 views

reconstructing a linear order corrupted by noise

Suppose we have a partial order (efficiently computable), $\leq$, on $\mathbb{R}^n$, a set $S \subset \mathbb{R}^n$, and let $\rho$ be the standard Euclidean metric. We want to find a set $S^\prime = ...
8
votes
0answers
71 views

Ideals in strong Bruhat order

Recall that a (lower) ideal in a poset $(P, \le)$ is a subset $I\subset P$ such that $x\in I \Rightarrow y\in I$ for all $y\le x$. In am interested in ideals in finite Coxeter groups $W$ equipped ...
5
votes
1answer
108 views

An equivalent definition for the adiamond lattices

A lattice is called adiamond if it admits no sublattice equivalent to the diamond lattice $M_3$ below: The top interval of a lattice is the interval between the meet of all the maximal elements and ...
0
votes
1answer
131 views

Quotients of posets

Let $\mathbf{Poset}$ denote the category of partially ordered sets and order-preserving maps. Does $\mathbf{Poset}$ have quotients?
5
votes
1answer
129 views

ACC (DCC) implies upper (lower) sets are upper (lower) closure of antichains?

I have read around (e.g. in Wikipedia) that if the ascending (descending) chain condition holds, all upper (lower) sets are the upper (lower) closure of an antichain, but I cannot find a proof. More ...
6
votes
2answers
254 views

Is this algebra isomorphic to an incidence algebra?

This question is motivated by trying to establish a converse to Theorem 7.8 of our paper. I have a finite poset $P$ with the following properties: $P$ has binary meets (and hence a least element). ...
1
vote
0answers
84 views

Properties of Coefficients of Order Polynomials [closed]

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain ...
2
votes
1answer
105 views

Surjectively rigid partially ordered sets

This question is related to a question recently asked by Joel David Hamkins. Let $(P,\leq)$ be a poset. We call it surjectively rigid if the only order-preserving surjective map $f:P\to P$ is the ...
7
votes
0answers
222 views

Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it. A permutation on a ...
0
votes
0answers
65 views

An equality for the trace of the join of a non-degenerate indecomposable system of projections in a finite factor

Let $M \subset B(H)$ be a finite factor (see for example here p2, or there) with a trace $tr$. The subset of projections of $M$ is naturally a lattice, noted $(\mathcal{P}(M), \wedge, \vee)$. A ...
2
votes
1answer
144 views

Is the top interval of a finite distributive lattice an hypercube lattice?

Let $(L,\wedge,\vee)$ be a finite distributive lattice. Let $M$ be the (unique) maximum element. An element $a \in L$ is called maximal if $a \le a' < M$ implies $a = a'$. Let $b = ...
11
votes
1answer
248 views

Posets preserving stationary subsets of $\omega_1$ and no new $\text{cof}(\omega)$ ordinals, but without countable covering property

What are some examples of posets $\mathbb{P}$ which have the following properties? It's OK if the definition uses large cardinals or some other hypothesis. $\mathbb{P}$ preserves stationary subsets ...
8
votes
2answers
291 views

Posets isomorphic to their endomorphism poset

Let $(P,\leq)$ be a poset. We set $$\text{End}(P)=\{f: P\to P: f\text{ is order-preserving}\}$$ and order $\text{End}(P)$ pointwise. Is there a poset with more than 1 point such that $P\cong ...
8
votes
1answer
135 views

Optimal strategy for game of 'online sorting' into a poset

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution: Each turn, the RNG produces a number, and the player must assign that ...
7
votes
1answer
200 views

Introducing meets while preserving directed closure

A poset $\mathbb{P}$ is called well-met iff every pair of compatible conditions in $\mathbb{P}$ has a greatest lower bound. Question: Suppose $\mathbb{P}$ is a separative partial order which is ...
9
votes
0answers
109 views

A family of posets

Consider the family of all (finite) posets that can be obtained by repeatedly applying one of the following three operations (starting e.g. with the empty poset): (O1) Disjoint union of one or more ...
0
votes
1answer
82 views

Dedekind-MacNeille completion of the strictly increasing members of $\omega^\omega$

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$ ordered by $f\leq g$ iff $f(n) \leq g(n)$ for all $n\in \omega$. Set $K = \{f\in \omega^\omega: m<n\in \omega \implies ...
3
votes
1answer
165 views

Order dimension of $\omega^\omega/(fin)$

Let $\omega^\omega$ denote the collection of all functions $f:\omega\to\omega$. For $f,g\in\omega$ we say $f\simeq g$ if and only if $\exists N \in \omega$ such that $f(n) = g(n)$ for all $n\geq N$. ...
0
votes
1answer
94 views

Priestley topologizability and connected components

This question is in the spirit of another older question. We say that a poset $(P,\leq)$ is Priestley-topologizable if there is a topology $\tau$ on $P$ such that $(P,\leq,\tau)$ is a Priestley ...
8
votes
1answer
170 views

Extending subsets to supersets in different ways

We are given a collection of sets $A_1,\ldots,A_s$, pairwise different and each of cardinality $k$, and a collection of sets $B_1,\ldots,B_s$, pairwise different and each of cardinality $l>k+1$, ...
1
vote
2answers
129 views

Poset-enrichment of abelian categories

Let $\mathsf{A}$ be an Abelian category (perhaps vector spaces or modules over your favorite ring), and let $\mathsf{A}(x,y)$ denote the set of morphisms in $\mathsf{A}$ from an object $x$ to another ...
0
votes
0answers
66 views

Is the order convergence topology on a poset always Hausdorff?

In this post two topologies on a poset $(P,\leq)$ were defined: the interval topology $\tau_i(P)$ and the order convergence topology $\tau_o(P)$. It turns out that $\tau_i(P)$ is always $T_1$ and ...
1
vote
1answer
97 views

Interval topology and order convergence topology

Throughout this post, let $(P,\leq)$ be a poset. The interval topology $\tau_i(P)$ on $P$ is generated by $$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$ where ...
0
votes
2answers
111 views

Continuous image relation on topological spaces

Let $\kappa$ be a cardinal, and let $\text{Top}(\kappa)$ be the set of topological spaces $(X,\tau)$ such that $X\subseteq \kappa$. We pre-order $\text{Top}(\kappa)$ by for $X, Y \in ...
2
votes
3answers
216 views

Antichain on $\mathcal{P}(\omega)/fin$ of cardinality $2^{\aleph_0}$?

We define an equivalence relation on $\mathcal{P}(\omega)$: for $x,y\in\mathcal{P}(\omega)$ we say $$x\simeq_{fin} y \text{ iff there is } n \in \omega \text{ such that } x\setminus \{0,\ldots,n\} = y ...
3
votes
1answer
83 views

Is $\{0,1\}^\omega$ the order-preserving image of $\{0,1\}^\omega$ modulo some finiteness relation?

Consider the following equivalence relation on $\{0,1\}^\omega$: $x\simeq y$ iff there is $n\in\omega$ such that $x(k)=y(k)$ for all $k\in\omega$ with $k\geq n$. It is easy to see that ...
1
vote
2answers
112 views

Completion of a single totally ordered down-set

This is a follow-up question to Complete sets of incompatible totally ordered down-set in a partially ordered set. Let $(P,\leq)$ be a partially ordered set such that for every $p\in P$ the set ...
2
votes
2answers
203 views

Complete sets of incompatible totally ordered down-set in a partially ordered set

Let $(P,\leq)$ be a partially ordered set. A down-set is a set $d\subseteq P$ such that $x\in d$ and $x'\in P, x'\leq x$ imply $x'\in d$. If the down-set is totally ordered, we say it is a totally ...
10
votes
3answers
434 views

Is a distributive lattice planar iff it admits no B3 sublattice?

A finite lattice is planar if it admits a Hasse diagram which is a planar graph (we want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element respects the ...
3
votes
1answer
142 views

Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...
2
votes
0answers
43 views

Decidability of first order theory of subclasses of posets

Is the first order theory of finite posets known to be undecidable? Does anyone know a survey about such results?
1
vote
1answer
90 views

Order-preserving images of $(\mathcal{P}(\kappa),\subseteq)$

Is there a cardinal $\kappa \neq \emptyset$ and a connected poset $P$ of cardinality $\leq \kappa$ such that there is no surjective order-preserving map from $(\mathcal{P}(\kappa),\subseteq)$ onto ...
4
votes
2answers
140 views

Image of poset with Hausdorff interval topology

Given a poset $(P,\leq)$ the interval topology $\tau_{\text{int}}(P)$ on $P$ is generated by $$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$ where $\downarrow x = ...
2
votes
1answer
134 views

Product of posets with Hausdorff interval topology

Given a poset $(P,\leq)$ the interval topology on $P$ is generated by $$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$ where $\downarrow x = \{y\in P: y\leq x\}$ and ...
5
votes
1answer
208 views

Is there a standard name for this poset

I've run into the following poset and I would expect it has a standard name. Let $n\geq k\geq 0$. Then $P_{n,k}$ consists of all $k$-element subsets of $\{1,\ldots,n\}$ ordered by $X\leq Y$ if ...
2
votes
1answer
136 views

Terminology question for maps between posets

Let $P$ and $Q$ be two poset (partially ordered sets) and $\phi : P \to Q$ an order-preserving function. I would like to know whether there is a name and perhaps a different characterizations of such ...
1
vote
1answer
76 views

Universal and left-factoring order-preserving maps

Trying to get a different angle for the question Fixed points and universal maps for posets, I want to compare universal maps to a different kind of functions. First recall that for posets $P,Q$ an ...
9
votes
3answers
236 views

Is the homomorphism poset directed if the codomain is directed?

Let $P,Q$ be partially ordered sets (posets). We consider the set $\text{Hom}(P,Q)$ of order-preserving functions $f:P\to Q$. (We call a function $f:P\to Q$ order preserving if $x\leq y$ in $P$ ...
2
votes
1answer
289 views

When is the homomorphism poset between posets a lattice?

Let $P,Q$ be partially ordered sets (posets). We consider the set $\text{Hom}(P,Q)$ of order-preserving functions $f:P\to Q$. There is a natural ordering relation on $\text{Hom}(P,Q)$ given by $f\leq ...
12
votes
1answer
286 views

Fastest algorithm to compute the width of a poset

An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out ...
1
vote
1answer
162 views

Does the category of posets have pushouts and pullbacks? [duplicate]

Let $\mathbf{Poset}$ be the category of partially ordered sets with order-preserving maps. Does $\mathbf{Poset}$ have both pushouts and pullbacks?
1
vote
2answers
189 views

Question on Posets and open sets [closed]

i'm sorry if my question is really trivial but this one is really bugging me out.. So let's have a partially ordered set $I$ with the topology in which the open sets are the increasing ones: $i\in U$ ...
2
votes
0answers
55 views

Computing basis of a lower set given basis of complementary upper set

In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...