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