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$).
400
questions
1
vote
1
answer
103
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
28
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
189
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
60
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 ...
9
votes
1
answer
350
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
497
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 ...
3
votes
1
answer
191
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
303
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
367
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)$?
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 \...
13
votes
1
answer
260
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 ...
2
votes
0
answers
286
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 $...
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 ...
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
429
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
930
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\...
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 ...
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 ...
8
votes
1
answer
291
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}$...
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
157
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 ...
14
votes
0
answers
325
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)\...
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
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
240
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
244
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} } \...
28
votes
1
answer
6k
views
What is the cofinality of the co-infinite subsets of ${\bf N}$?
Let ${\mathcal A}$ be the family of subsets $A$ of the natural numbers ${\mathbf N}$ which are co-infinite (i.e., their complement is infinite). We partially order this family by set inclusion. A ...
3
votes
0
answers
106
views
Generalized Gaussian binomial and symmetric chain decomposition
Background
Let $\mu = (\mu_1, \ldots, \mu_k)$ be a partition, meaning that $\mu_1 \geq \ldots \mu_k \geq 1$. The Young diagram associated to $\mu$ is given by the set $(r,c) \in \mathbb{N} \times \...
6
votes
1
answer
216
views
Smallest ordinal $\mu$ not embeddable in ${\cal P}(\omega)$
The motivation for this question is the startling fact that there is an order-preserving injective map (embedding) from $\mathbb{R}$ into ${\cal P}(\omega)$. (Think Dedekind cuts.) I am wondering how &...
8
votes
0
answers
148
views
Partial order on graphs induced by homomorphism counts
For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
3
votes
0
answers
83
views
Is the face poset of a compact intersection of cylinders and half-spaces shellable?
Let the $n$-disk $D^n$ be stratified hemispherically (so there are two 0-dimensional strata at the poles, two 1-dimensional strata for the prime meridian and the international date line, two 2-...
0
votes
0
answers
38
views
Is the set of sub-dcpos a dcpo (directed-complete partial order)?
$\newcommand{\sub}{\mathrm{sub}}$Given a dcpo (directed-complete partial order) $\mathcal{X} = (\le, X)$, consider the set $\mathcal{X}^{\sub}$ of all sub-dcpos of $\mathcal{X}$. Can one define a ...
49
votes
7
answers
7k
views
Zorn's lemma: old friend or historical relic?
It is often said that instead of proving a great theorem a mathematician's fondest dream is to prove a great lemma. Something like Kőnig's tree lemma, or Yoneda's lemma, or really anything from this ...
5
votes
1
answer
204
views
Cofinal well-founded subset in mod finite order
The mod finite order on ${}^\omega \omega$ is defined as $f \leq^\ast g$ if and only if $f(n) \leq g(n)$ except for finitely many $n \in \omega$. My question is: can we always extract a cofinal well-...
4
votes
2
answers
182
views
Ordinal-universal linear order on $\kappa$ elements
The starting point of this question is the observation that if $\lambda$ is a countable ordinal, then there is an order-embedding $e:\lambda \hookrightarrow \mathbb{Q}$.
Given an infinite cardinal $\...
8
votes
1
answer
311
views
First inaccessible Suslin trees in L, an interesting detail
It's known (but quite nontrivial) that $V=L$ implies that if $\kappa$ is the 1st inaccessible cardinal then there are $\kappa$-Suslin trees $T$.
Such a tree $T$ can be considered as a forcing notion ...
2
votes
0
answers
113
views
Product-decomposition of ${\cal P}(\omega)/\rm{fin}$ [closed]
For $A,B\in {\cal P}(\omega)$ let us say that $A\simeq_{\rm{fin}} B$ if both $A\setminus B$ and $B\setminus A$ are finite. It is easy to see that this establishes an equivalence relation on ${\cal P}(\...
4
votes
1
answer
102
views
Searching for cofinal subsets of directed sets subject to finite constraints
Let $(P,\leq)$ be a directed set with uncountable cofinality. For every element $p\in P$, we are given a finite set $c_p\subset P\smallsetminus \{p\}$ of "incompatible elements". We say that ...
10
votes
4
answers
897
views
Are arbitrary nonempty intersections of principal filters principal?
Suppose $\langle L,\leq\rangle$ is a lattice with join $\sqcup$. Let $F_1$ and $F_2$ be principal filters on $L$. Thus, for $i\in I=\{1,2\}$ there are $x_i\in L$ so that $F_i=\{y\in L:x_i\leq y\}$.
In ...
4
votes
1
answer
199
views
Representation of $\mathrm{AGL}(V)$ on the homology of the poset of affine subspaces of $V$
Let $V$ be an $n$-dimensional vector space over a finite field $F$ (of order $q$). Denote by $\mathrm{AGL}(V)$ the group of invertible affine transformations of $V$; so $\mathrm{AGL}(V)$ consists of ...
2
votes
2
answers
221
views
Maximal uncountable chains in ${\cal P}(\omega)$
Let ${\cal P}(\omega)$ denote the power-set of $\omega$. We order it by set inclusion $\subseteq$ and say that ${\cal C}\subseteq {\cal P}(\omega)$ is a chain if for all $A, B\in {\cal C}$ we have $A\...
8
votes
1
answer
382
views
Which spectra arise from partially ordered commutative monoids?
Thomason showed how any connective spectrum arises from a symmetric monoidal category:
Robert W. Thomason, Symmetric monoidal categories model all connective spectra, Theory Appl. Categ. 1 (1995), 78–...