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$).
379
questions
8
votes
1
answer
214
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 \} \}$, $\{...
- 397
10
votes
0
answers
200
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 ...
- 307
6
votes
1
answer
324
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}$...
- 42.5k
1
vote
0
answers
67
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 ...
- 31
1
vote
1
answer
63
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 ...
- 31
4
votes
1
answer
213
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 \...
- 413
1
vote
0
answers
126
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 ...
- 1,245
14
votes
0
answers
299
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)\...
- 1,220
2
votes
1
answer
71
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 ...
- 21
1
vote
0
answers
42
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 $...
- 837
2
votes
1
answer
225
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 ...
- 15.1k
6
votes
1
answer
228
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} } \...
- 413
26
votes
1
answer
5k
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 ...
- 98.8k
3
votes
0
answers
86
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 \...
- 795
6
votes
1
answer
202
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 &...
- 42.5k
8
votes
0
answers
134
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_{\...
- 2,064
3
votes
0
answers
80
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-...
- 55.4k
0
votes
0
answers
33
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 ...
- 363
46
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 ...
- 17.3k
5
votes
1
answer
191
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-...
- 413
4
votes
2
answers
170
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 $\...
- 42.5k
8
votes
1
answer
243
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,281
2
votes
0
answers
109
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}(\...
- 42.5k
5
votes
1
answer
78
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 ...
- 345
10
votes
4
answers
868
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 ...
- 325
4
votes
1
answer
185
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 ...
- 35.9k
2
votes
2
answers
184
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\...
- 42.5k
8
votes
1
answer
353
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–...
- 20.6k
1
vote
1
answer
118
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 $...
- 514
4
votes
0
answers
125
views
Rowmotion of matroids
If $Z$ is a finite poset, then we say that a collection $\mathcal{A}$ is an antichain if whenever $y,z\in\mathcal{A}$, if $y\leq z$, then $y=z$. If $R\subseteq Z$, then let $L(R)$ be the set of all $x\...
- 25.5k
14
votes
5
answers
718
views
Birkhoff's representation theorem vs matroid-geometric lattice correspondence
This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says ...
- 3,173
1
vote
0
answers
99
views
Finite posets built by coning initial segments in an auxiliary ordering
Let $P$ be a finite poset, and let $p \in P$ be a maximal element. Then $P = (P \setminus p) \cup_{P_{<p}} P_{\leq p}$. Conversely, if $Q$ is a poset and $S \subseteq Q$ is downward-closed, then $P ...
- 55.4k
1
vote
2
answers
116
views
Embedding $^\omega\omega$ and $S_\omega$ with lexicographic order into $\mathbb{R}$
Let $^\omega\omega$ be the collection of all functions $f:\omega\to\omega$. We order $^\omega\omega$ lexicographically, that is: For $f\neq g \in \,^\omega\omega$ let $m(f,g):= \min\{n\in\omega:f(n)\...
- 42.5k
3
votes
1
answer
97
views
Digraph without "immediately isomorphic" vertices?
Say that a digraph $(V,E)$ is reducible if there exist $x,y\in V$ with $x\ne y$ and such that for all $z\in V$, $(x,z)\in E\leftrightarrow(y,z)\in E$ and $(z,x)\in E\leftrightarrow(z,y)\in E$. It is ...
- 403
17
votes
3
answers
695
views
Matrices of combinatorial sequences that are inverse in two ways
I'm interested in pairs $A=(a_{i,j})_{i,j=0,1,\ldots}$ and $B=(b_{i,j})_{i,j=0,1,\ldots}$ of infinite matrices for which:
They are uni-lower-triangular, i.e., $a_{i,i}=1$ for all $i$ and $a_{i,j}=0$ ...
- 20.6k
0
votes
1
answer
116
views
Partial orders on downward closed sets [closed]
Let $P = (V, \sqsubseteq)$ be a partial order and $\mathfrak{D}(P)$ denote the class of downward-closed subsets of the partial order $P$ (i.e, the class of $A \subseteq V$ such that $y\in A \;\&\; ...
- 629
7
votes
1
answer
245
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 ...
- 24.4k
3
votes
1
answer
95
views
Quiver algebras from semirings and posets as semirings
A semiring is a nonempty set $S$ such two binary operations + and * making S into a semigroup with + and * and such that a*(b+c)=ab+ac and (b+c)a=ba+c*a for all a,b,c in S.
Assume in the following ...
- 24.4k
7
votes
0
answers
232
views
Interesting uniform posets
A sequence $(P_0,P_1,\ldots)$ of finite posets is called uniform if: each $P_n$ is graded of rank $n$ with a minimum $\hat{0}_n$ and a maximum $\hat{1}_n$; for any $p \in P_n$ with $\mathrm{rank}(p)=n-...
- 20.6k
5
votes
1
answer
204
views
Classification of multiplicative lattices
Question 1:Is there a classification of finite lattices which admit a multiplication making them into a finite multiplicative lattices? (see https://encyclopediaofmath.org/wiki/Multiplicative_lattice ...
- 24.4k
6
votes
1
answer
182
views
Order ideals of positive root systems and avoiding group elements in the Weyl group
Let $X$ be the poset of positive roots of a finite root system of Dynkin type $Q$.
Question 1: In Dynkin type $A_n$, is it true that the poset of order ideals of $X$ is isomorphic to the poset of [2,...
- 24.4k
1
vote
0
answers
82
views
Connected posets $P\not \cong Q$ such that $\text{Hom}(P,P) \cong \text{Hom}(Q,Q)$
Given posets $A, B$, we denote by $\text{Hom}(A,B)$ the collection of order-preserving functions $f:A\to B$. We put a partial order $\leq_{\text{Hom}(A,B)}$ on $\text{Hom}(A,B)$ by setting $$f \leq_{\...
- 42.5k
1
vote
2
answers
192
views
Is the poset $\mathrm{Idl}_{\neq \emptyset, P}(P)$ of nonempty, proper ideals in a finite connected poset $P$ (empty or) weakly contractible?
$\DeclareMathOperator\Idl{Idl}$Let $P$ be a finite, connected poset with at least two elements, and let $\Idl_{\neq \emptyset, P}(P)$ be the set of downward closed sets $S \subset P$ such that $S \neq ...
- 55.4k
6
votes
2
answers
401
views
An equality for the reduced homology related to the comparability graph of a poset
$\DeclareMathOperator\width{width}$Let $P$ be a finite poset with $n$ elements (we can assume that $P$ is connected and has width at most $n-2$). The comparability graph $G_P=(V,E)$ associated to $P$ ...
- 24.4k
3
votes
2
answers
131
views
Is $(\omega+1)^\omega/{\cal U}$ complete for ${\cal U}$ free ultrafilter?
Let ${\cal U}$ be a free ultrafilter on $\omega$. Is the linearly ordered set $(\omega+1)^\omega/{\cal U}$ complete?
- 42.5k
4
votes
1
answer
164
views
(Higher) posets with non-binary comparisons: name? Axioms? (Looking for reference.)
I am looking for a name of a certain structure, which is a generalization of poset that admits non-binary comparisons.
Let $P$ be a set equipped with operations, for $n\geq2$,
$$ C_n: P^n \to \{True, ...
- 755
0
votes
0
answers
72
views
Is $(\omega+1)^\omega/{\cal U}$ "unique"?
If ${\cal U}_i$ free ultrafilters on $\omega$ for $i = 1,2$ , are the ultrapowers $(\omega+1)^\omega/{\cal U}_i$ necessarily isomorphic as lattices for $i = 1,2$?
- 42.5k
9
votes
1
answer
346
views
Which finite posets are Koszul self-dual?
Let $P$ be a finite connected poset with incidence algebra $A_P$.
For the definition and results on Koszul algebras for incidence algebras, see for example here
Question: Which posets have the ...
- 24.4k
0
votes
1
answer
164
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\}$ ...
- 81
3
votes
1
answer
126
views
Which Boolean lattices have a left-to-right symmetric drawing?
This question is inspired by a similar MSE question about partition lattices.
Question: Which finite Boolean lattices have a symmetric drawing on the 2D plane?
By a symmetric drawing of a lattice, I ...
- 3,204