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$) and transitive ($x\leq y$ and $y\leq z$ implies $x \leq z$).

learn more… | top users | synonyms

2
votes
2answers
87 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 ...
-4
votes
0answers
35 views

Partially ordered set [closed]

Show that a subset $C$ of a preordered space $(X, ≤)$ is a chain if and only if $C × C ⊂ A ∪ A^{−1}$, where $A := \{(x, y) : x ≤ y\}$, $A^{−1} := \{(x, y) : (y, x) ∈ A\}$.
0
votes
0answers
33 views

Upper and Down Bound,directed,cofinal [closed]

I'm learning a partially ordered set.Can you give me some example of each these definition: 1.Upper and Down Bound : ...
3
votes
2answers
143 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 ...
9
votes
3answers
363 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
109 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
42 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?
2
votes
1answer
66 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 ...
5
votes
2answers
108 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 = ...
3
votes
1answer
62 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
198 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
0answers
105 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 ...
2
votes
1answer
66 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 ...
10
votes
3answers
220 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$ ...
3
votes
1answer
199 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 ...
11
votes
1answer
168 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
110 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
169 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
50 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 ...
4
votes
3answers
276 views

Classification of countable posets?

Is there a classification of countable posets where between each two comparable elements there is a third element between them?
8
votes
0answers
125 views

Fixed points and universal maps for posets

In a recent post about f.p.p. for poset products, @M.Mirabi brought back an old-standing problem about the fixed point property of the product of two arbitrary posets which already enjoy the fixed ...
27
votes
3answers
844 views

Is the fixed point property for posets preserved by products?

Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point. Theorem. Suppose $P$ and $Q$ are posets ...
0
votes
2answers
102 views

a dcpo seen as a category: when does a dcpo map induce a functor with an adjoint?

Take two posets $A, B$ (partially ordered sets). Now consider these posets to be categories $Cat(A), Cat(B)$ respectively. Consider a map from $A$ to $B$, $f: A \rightarrow B$. This can be seen as ...
3
votes
2answers
168 views

Directed subposet of a poset containing the minimal elements

The following appears naturally in a certain context: Let $P$ be a graded partially ordered set. Let $M$ be the subset of minimal elements of $P$. Define subsets $E_i$ inductively as follows: First, ...
7
votes
1answer
236 views

The category of categories and adjunctions

What is known about the category that has small categories as objects and adjunctions as morphisms? Obviously, it has neither terminal nor initial objects. But what about other kinds of limits? Are ...
5
votes
1answer
169 views

Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...
1
vote
1answer
93 views

Krull dimension of dense extensions

Let $A$ be a boolean algebra and let $B\leq A$ be a boolean sub-algebra which is dense (for all $0\neq a\in A$, there is a $0\neq b\in B$ such that $b\leq a$). We suppose also that $B$, as a partially ...
2
votes
1answer
127 views

Galois Connections: algorithmic generation

Given two finite posets $P,Q$, is it known any algorithm to count and/or generate every Galois Connection between $P$ and $Q$ ? I'm looking for references about this problem.
2
votes
1answer
166 views

Maximal number of antichains of a connected poset

Assume we have a connected poset $P$ of $n$ elements, I am searching to know what is the maximal number of antichains such a poset can have? $2^n$ is obviously an upper bound, and my feeling is that ...
3
votes
1answer
115 views

Matching in the Boolean Algebra

We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show ...
6
votes
1answer
424 views

Order homomorphism functions on $\omega_1$

Let $\omega_1$ be the first uncountable ordinal, same as the set of all countable ordinals. Let $F$ be the set of all functions $f$ from $\omega_1$ minus singleton $0$ into $\omega_1$ that are (a) ...
4
votes
1answer
180 views

About subposet of Levy collapse

Let $\lambda>\kappa$ and $\operatorname{Coll}(\kappa, \lambda)$ be the poset collapsing $\lambda$ to $\kappa$. Pick a subposet $P$ which is $\lt\kappa$-closed and of size $\lambda$. Can we say that ...
2
votes
2answers
106 views

Representation of Banach spaces partially ordered by solid, normal, minihedral cones

I've been using the representation result below, from Krasnosel'skij/Lifshits/Sobolev; Positive Linear Systems---The Method of Positive Linear Operators. Heldermann Verlag, 1989. Theorem. Let $E$ be ...
17
votes
0answers
245 views

Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. ...
1
vote
0answers
67 views

Suprema and infima in spaces ordered by non-normal cones

Background We shall call a subset $V_+ \subseteq V$ of a Banach space $V$ a cone if $V_+$ is closed, $\alpha V_+ \subseteq V_+$ for all $\alpha \geqslant 0$, and $V_+ \cap (-V_+) = \{0\}$. Cones ...
7
votes
0answers
143 views

Strength of claims about extensions of partial preorders and orders to linear ones

Consider these two axioms: Every partial order extends to a linear order. Every partial preorder (reflexive and transitive relation) extends to a linear preorder while preserving strict orderings: ...
2
votes
0answers
68 views

Rank generating functions on a graded poset and a linear extension of it

Let $A$ be a possibly infinite ensemble and let $\leq$ be a partial order between elements of $A$. We denote $P_{\leq}=(A,\leq)$ the corresponding poset. Furthermore, we suppose that $P$ is graded, ...
1
vote
1answer
88 views

Generalized connected components decomposition for Priestley spaces

Preliminaries A partially ordered space is both a poset and a topological space. It has connected components both as a topological space, and connected components as a poset, i.e. the maximal ...
2
votes
1answer
100 views

Are the connected components of a Priestley space closed?

Preliminaries A Priestley space is both a poset and a topological space. The topologically connected components of the space are trivially closed. (They are just the points of the underlying set.) But ...
2
votes
1answer
137 views

Linear order extensions on (nonabelian) groups

If $G$ is a group with a (left) linear order, does every (left) partial order on $G$ extend to a (left) linear order? The answer is affirmative on abelian groups, where being torsion-free is ...
6
votes
1answer
205 views

Terminology question for poset maps

Is there a standard name for order-preserving maps $f\colon P\to Q$ of posets with the property that the image of a lower set is a lower set, or equivalently if $q\leq f(p)$ then there exists $p'\leq ...
7
votes
1answer
266 views

Does this lattice have a name (and literature)?

The "lattice" in the title appears to be a lattice. At least it's a poset, which I define now. Fix a partition $\lambda$ of $n$ and consider the set of all standard Young tableaux (each of ...
10
votes
2answers
335 views

Do operations generate well-ordered sets only?

I've read   @TauMu's question   about the set of functions   $\mathbb N\rightarrow\mathbb N$   generated from the identity map by repeatedly applying exponentiation of two already ...
9
votes
1answer
429 views

Does this property of a partially ordered set have a name?

What do you call a poset with this property? For any elements $a,b,c,d$ such that $\{a,b\}\le\{c,d\}$, there is an element x such that $\{a,b\}\le x\le\{c,d\}$. (Equivalently, for any finite sets ...
6
votes
0answers
145 views

“Double convolution” with the Mobius function on a poset

Let $f$ and $g$ be arbitrary (say integer-valued) functions on some poset $P$, and say $\mu$ is the Mobius function of $P$. I'm studying a quantity that's a sort of "double convolution" of $f$ and $g$ ...
9
votes
2answers
305 views

How exactly does Schützenberger promotion relate to Striker-Williams promotion?

Schützenberger promotion, studied (for example) in Richard Stanley, Promotion and Evacuation, 2009, is a permutation of the set of all linear extensions of a finite poset. Since one can identify the ...
22
votes
2answers
1k views

Does this poset have a unique minimal element?

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the ...
7
votes
1answer
251 views

Which of these relations on partial orders allows us to identify forcing equivalence?

Background This question was inspired by Justin Palumbo's excellent question Cantor Bernstein for notions of forcing. In his question, Justin considers a relation $\lhd$ on partial orders (defined ...
4
votes
0answers
161 views

When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where ...
2
votes
4answers
417 views

Minimal (semi)lattice containing a given poset

For a given poset, (I think that) it is easy to construct the minimal join-semilattice containing that poset. I wonder whether the minimal lattice containing that poset is also easy to construct. I ...