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
2 votes
1 answer
205 views

Order on Euclidean space in which a finite poset embeds

Fix positive integers $k$ and $n$. For which finite posets $(X,\lesssim)$ with $\#X=k$ does there exist an order embedding $\phi\colon(X,\lesssim)\to (\mathbb{R}^n,\le)$, where $\le$ is the standard ...
1 vote
2 answers
225 views

coset poset of reflection subgroup

Fix a finitely generated Coxeter system $(W, S)$, and let $W_J$ denote the standard parabolic proper subgroup generated by a subset $J \subset S$. It is well known that the poset of cosets $\{xW_J\}$ ...
7 votes
1 answer
384 views

Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history

Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces. Counting the ...
1 vote
1 answer
110 views

Are there more than 2 types of posets $P\cong\mathcal O_{\rm fin}(P)\setminus\{\emptyset\}$?

We use notation derived from Davey and Priestley, Introduction to Lattices and Order. Let $\mathcal O_{\rm fin}(P)$ be the poset of finite down-sets of the poset $P$. A finite poset is ranked if all ...
1 vote
0 answers
33 views

Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
3 votes
1 answer
191 views

Embedding of a poset with "desirable" characteristics

Let $(P, \succeq)$ be a poset (you can assume $\succeq$ is not empty). I am interested in finding a poset $(X, \succeq^*)$ that embeds $(P, \succeq)$, and $\forall x,y \in X$ both of the following ...
1 vote
1 answer
63 views

Multidimensional power series with coefficients equal to an order of stabilizer of a set of powers

I have encountered a necessity to work with a series of the following form. There are $N$ variables $x_1,\ldots x_N$. It is convenient to introduce monomial symmetric polynomials $m_{\lambda}$. They ...
0 votes
0 answers
206 views

Ordering labellings of a fixed poset

Let $\{A_1,\ldots, A_m\}$ be a family of sets and $I=\{1, \ldots, m\}$. Assume for any $J\subset I$, $B_J=\bigcap_{i\in J}A_j$ satisfies $1\leq |B_J| \leq m-1$ as long as $|J|>1$. We define a ...
10 votes
1 answer
300 views

Writing matrices deduced from upper triangular 0-1 matrices as a product of a permutation matrix and an upper triangular matrix

Let $C$ be an upper triangular matrix with entries 0 or 1 such that every diagonal entry is equal to one. Let $M_C:=-C^{-1}C^T$. Question: Is there a nice direct criterion (or even classification) on ...
8 votes
1 answer
499 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 ...
9 votes
1 answer
351 views

Are the Boolean algebras ${\cal P}(\omega)/(\text{fin})$ and ${\cal P}(\omega)/(\text{thin})$ isomorphic?

A set $A\subseteq \omega$ is said to be thin if $$\lim\sup_{n\to\infty}\frac{|A\cap \{0,\ldots, n\}|}{n+1} = 0.$$ We say for $A, B\subseteq \omega$ that $A\simeq_\text{fin} B$ if the symmetric ...
9 votes
1 answer
499 views

Reference request: number of antichains of a partially ordered set

Let $\mathbb{N}$ denote the set of all positive integers. For each $n \in \mathbb{N}$, define the set $$ P_n = \{ (a,b) \in \mathbb{N} \times \mathbb{N} : 1 \leq a \leq b \leq n \} $$ and consider the ...
14 votes
1 answer
549 views

"Scott completion" of dcpo

If $A$ is poset with all directed suprema, it is common to consider the Scott topology on $A$, whose open subsets are the $U \subset A$ such that $U$ is upward closed and if $\bigcup_I a_i \in U $ for ...
3 votes
1 answer
203 views

Dimension of the cartesian product of a poset and a chain

Let $P$ be a finite poset and for $n\in\mathbb N$, let $\bf n$ denote the $n$-element totally ordered set. If $m,n\in\mathbb N$ and $1<m<n$, is the dimension of $P\times \bf m$ equal to the ...
3 votes
1 answer
192 views

Reference Request for "Finite Semilattice with Top and Bottom is a Lattice"

Let $\mathcal{O}(P)$ be a finite, completely distributive lattice of all lower sets ordered by set inclusion. Moreover, let $K =\; \mathrel{\{} h(x) \mathrel{|} x \in \mathcal{O}(P) \mathrel{\}}$ be ...
5 votes
0 answers
204 views

Sperner property of a distributive lattice associated to a divisor poset and the free distributive lattice

Let $P_n$ denote the poset with elements $P_n=\{1,...,n\}$ ordered by divisibility and let $L_n$ denote the distributive lattice of order ideals of $P_n$, whose elements should correspond to primitive ...
4 votes
1 answer
305 views

If $P\times{\bf2}$ order-embeds in $Q\times{\bf2}$, does the poset $P$ embed in the poset $Q$?

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$. We partially order the Cartesian ...
1 vote
0 answers
45 views

Find an order-embedding of $S_3\times{\bf2}\times{\bf k}$ into a product of $3$ chains, one of size at most $k$

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$. We partially order the Cartesian ...
4 votes
1 answer
175 views

Find an order-embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$. We partially order the Cartesian ...
10 votes
4 answers
368 views

Universal poset for cardinals $\kappa \geq \aleph_0$

Given a cardinal $\kappa\geq \aleph_0$, is there a poset $(P,\leq)$ with $|P| = \kappa$ such that every poset of cardinality $\kappa$ can be order-embedded into $(P,\leq)$?
13 votes
1 answer
262 views

Can any poset of cardinality $\leq 2^{\aleph_0}$ be embedded in ${\cal P}(\omega)/(\text{fin})$?

We endow ${\cal P}(\omega)$ with an equivalence relation by saying that $A\simeq_{\text{fin}} B$ iff the symmetric difference $A\Delta B$ is finite. The resulting set of equivalence classes is denoted ...
5 votes
0 answers
187 views

Is this "trimming" of a supersolvable semimodular lattice known?

Let $L$ be a finite (upper) semimodular lattice. Recall that this means $L$ is graded and its rank function $\rho\colon L \to \mathbb{N}$ satisfies $$ \rho(x) + \rho(y) \geq \rho(x\vee y)+\rho(x \...
2 votes
0 answers
287 views

Does this monoid have a name?

Fix a positive integer $n \geq 1$. Let $M$ be the monoid with generators $S=\{x_0,x_1,\ldots,x_n\}$ and relations $R = \{ \alpha x_0 = \beta x_0\colon \alpha,\beta \in S^*, |\alpha|=|\beta|\}$, where $...
2 votes
1 answer
155 views

Ordering patterns of projecta by least witness

Let $J$ denote Jensen's modification of the constructible hierarchy. For an ordinal $\alpha$ and an $n\in\mathbb N^+$, let $\rho_n^{J_\alpha}$ denote the $\Sigma_n$-projectum of $J_\alpha$, the least $...
4 votes
1 answer
247 views

Largest antichain in partial ordering in OEIS

OEIS A109388 $\{a_n\}_{n\ge1}$ is an integer sequence with $a_n=\binom{n}{\lfloor \frac{n}{3} \rfloor}\times 2^{n-\lfloor\frac{n}{3}\rfloor}$, I noticed that OEIS says $a_n$ is the size of the ...
15 votes
4 answers
695 views

Unified framework for posets with order polynomial product formulas

One of the most celebrated results in algebraic combinatorics is the Hook Length Formula of Frame-Robinson-Thrall which counts the number of standard Young tableaux of given partition shape. Such SYTs ...
7 votes
1 answer
329 views

Forcing axiom for a single poset

Let $FA_\kappa (\mathbb{P})$ be the claim that for every family $\mathscr{D}$ of dense sets in the poset $\mathbb{P}$ with $\vert \mathscr{D} \vert = \kappa $ there is a filter $G$ such that for all $...
2 votes
0 answers
90 views

Can this order relation, defined in terms of all topological spaces, be defined in terms of the reals alone?

Let $K$ be the operator monoid under composition of Kuratowski's $14$ set operators generated by topological closure $k$ and complement $c.$ Kuratowski's 1922 paper gives the poset diagram of the ...
7 votes
1 answer
432 views

Geometric realization of a poset

Consider the finite Boolean lattice $B_n$ of subsets of $[n]:=\lbrace 1,\dots,n\rbrace$ ordered by inclusion, let $1\leq j,k\leq n$ and consider the poset: $$A_{j,k}=\lbrace\emptyset\neq U\in B_n\mid (...
10 votes
2 answers
940 views

Homotopy type of the geometric realization of a poset

Consider a set of $n$ elements $S=\lbrace 1,\dots,n\rbrace$ and $\mathcal{P}(S)$ to be the power set of $S$, which is a well-defined poset with respect to the inclusions. Now consider $\emptyset\neq T\...
1 vote
1 answer
164 views

Largest value of the Möbius function for subposet of product of chains

Given a product $P$ of chains of lengths $a_1, \dots, a_n$, what is an upper bound on the largest possible value of the absolute value of the Möbius function on a subposet of this poset? Perhaps in ...
4 votes
0 answers
165 views

Largest rank-selected Möbius function of a product of chains

Inspired by this question and the answer by Sam Hopkins, given a finite product $P$ of chains, which rank-selection gives the largest absolute value of the Möbius function? Equivalently, given a ...
8 votes
1 answer
293 views

What is the Möbius function for the lattice of partial partitions?

Let $n$ be a positive integer. Let $P$ be the set of partitions of subsets of $\{ 1, 2, \dotsc, n \}$ (so, for example, when $n=2$, the set $P$ contains $\emptyset$, $\{ \{1 \} \}$, $\{ \{2 \} \}$, $\{...
10 votes
0 answers
256 views

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$?

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$ as it relates to $n$? Obviously $2\le m\le 2^n$ and ...
6 votes
1 answer
349 views

Is every homogeneous poset a lattice?

A poset $(P,\leq)$ is homogeneous if $P\cong [a,b]$ for all $a,b\in P$ with $a<b$ (where $[a,b] := \{x\in P: a\leq x\leq b\}$). Examples of homogeneous posets include $[0,1]$, $[0,1]\cap \mathbb{Q}$...
7 votes
6 answers
1k views

Category = Groupoid x Poset?

Is it possible to split a given category $C$ up into its groupoid of isomorphisms and a category that resembles a poset? "Splitting up" should be that $C$ can be expressed as some kind of extension ...
1 vote
0 answers
102 views

Causal-net category and poset category

Order is a fundamental mathematical structure. There are two natural ways to represent order structures, by posets and by causal-nets (acyclic directed graph). How can we compare these two ways, and ...
1 vote
1 answer
79 views

Characterization of edge posets

Given an acyclic directed graph $G$, the set $E(G)$ of edges of $G$ equipped with the reachable order $\to$ is called the edge poset of $G$, where for two edges $e_1\to e_2$ means that there is a ...
4 votes
1 answer
235 views

Cofinal rectangles in poset

Suppose $(P, <)$ is a poset of cofinality $\aleph_2$ and additivity (least cardinality of an unbounded subset) $\aleph_1$. Can we conclude the existence of a cofinal subset of order-type $\omega_1 \...
1 vote
0 answers
160 views

Covering a poset by minimum number of chains and antichains

Covering a poset by minmum number of chains is given by Dilworth's theorem and covering a poset by minimum number of antichains is given by Mirsky's theorem. I was wondering what happens if we allow ...
4 votes
0 answers
511 views

How should the proof of the XYZ theorem be understood?

The XYZ Theorem of Shepp [1] states the following for a given poset $P$. Consider the probability space of all the linear extensions of $P$, where each possible extension is equally likely. Then for ...
14 votes
0 answers
326 views

Poset defined on pairs of subgroups

Let $G$ be a group. Consider the set $P(G)$ of all pairs $(H,N)$ of subgroups of $G$ such that $N$ is a normal subgroup of $H$. Consider the relation $\leq_G$ on $P(G)$ defined as follows: $(H,N)\...
36 votes
6 answers
12k views

The category of posets

I am trying to teach myself category theory and, as a beginner, I am looking for examples that I have a hands-on experience with. Almost every introductory text in category theory contains following ...
2 votes
1 answer
77 views

Request for literature recommendations on isotonic mappings

An isotonic mapping is a function between two partially ordered sets that preserves the ordering between the elements. Specifically, given two partially ordered sets $(X,\le)$ and $(Y,\le)$, a ...
1 vote
1 answer
134 views

Thinning directed sets ${\frak P}$ of partitions of $\omega$ with no ${\frak P}$-discrete subsets

This question branches from Taras Banakh's recent question on a cardinal characteristic connected to families of partitions that are directed in the ordering of partition refinement. A partition $\...
3 votes
0 answers
208 views

References for properties/examples of breadth in (semi)lattices

This is in some sense following up on my earlier question Is there existing terminology for this technical condition on semilattices? and the answer given by NN. I am currently revising the paper ...
1 vote
0 answers
62 views

Something like Dedekind-MacNeille completion

The Dedekind–Macneille completion of a poset $P$ can be represented as a complete lattice $\widehat P$ consisting of all lower subsets (order ideals) $I$ for which $I=(I^\uparrow)^\downarrow$, where $...
2 votes
1 answer
241 views

Posets with cardinality bounds on upward-closed subsets

Let $(P,\leq)$ be a finite poset that contains a (global) minimal element $0$ and a (global) maximal element $1$. We say that a subset $U \subset P$ is upward closed if $x \in U$ and $y \geq x$ forces ...
6 votes
1 answer
245 views

Poset as union of posets of lower cofinality

Let $ \mathbb{P}$ be any directed, well-founded poset of cofinality $ \aleph_{n+1}$, where $n$ is a natural. Can we write it as an increasing union $ \mathbb{P} = \bigcup_{\alpha < \omega_{n+1} } \...
11 votes
3 answers
651 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 order)...

1
2 3 4 5
9