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
182
views
Explicit calculation of the width of a product of chains (i.e. maximal rank size)
Given a poset $P$, I am interested in the width (size of the maximal antichain) of $\mathcal{O}(P)$, i.e. the poset of downsets in $P$, ordered by inclusion.
As this is rather difficult, I'm starting ...
12
votes
1
answer
598
views
Order polynomial of shifted double staircase
This question is related to my earlier question looking for posets with product formulas for their order polynomials.
Recall that the order polynomial $\Omega_P(m)$ of a finite poset $P$ is defined ...
26
votes
3
answers
2k
views
When does a graph underlie the Hasse diagram of a poset?
For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
1
vote
1
answer
123
views
Is there some characterization of $\omega^\omega$-base related to $S_\omega$?
For a topological space $X$ and one point $x\in X$, we call the cofinal type of neighborhood bases of $x$ are cofinally finer than $\omega^\omega$-base if for any neighborhood base $\mathfrak{N}$ of $...
1
vote
1
answer
96
views
Are non-trivial interval-isomorphic posets lattices?
We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$.
Suppose $(P,\leq)$ is interval-...
6
votes
1
answer
207
views
Pairwise non-isomorphic interval-isomorphic lattices
Let us call a lattice $(L,\leq)$ interval-isomorphic if for all $a<b \in L$ we have $L \cong [a,b]$, where $[a,b]=\{x\in L:a\leq x\leq b\}$.
Are there $2^{\aleph_0}$ pairwise non-isomorphic ...
0
votes
0
answers
73
views
Infimums of Poset of Unlabelled Subtrees
I will use $T$ to refer to the set of unlabelled, rooted trees, and use $(t,r)$ to denote a tree and its root. Let $(T, \preceq)$ be a poset where $(t_1,r_1) \preceq (t_2,r_2)$ means that $t_1$ is a ...
2
votes
1
answer
354
views
Is this poset shellable?
Let $V$ be a finite dimensional vector space over a finite field $F$. (The case $F = \mathbb{Z}/2\mathbb{Z}$ is the case I most care about.) Consider the poset of linearly independent subsets of $V$ ...
1
vote
1
answer
174
views
Structure of a poset of subcategories
Given a category $\mathbf{C}$, we can consider monomorphisms into it. These are the faithful and injective-on-objects functors (this violates the principle of equivalence). The idea is to try to get a ...
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 ...
1
vote
0
answers
65
views
Posets with two partial (self-)distributive operations
Let $(X, {\sqsubset}, {\circ}, {\ast})$ be a set $X$ with a strict partial order $\sqsubset$ and two partial binary operations $\circ$ and $\ast$ such that for any $a, b, c \in X$:
$a \circ b$ and $a ...
16
votes
1
answer
595
views
Universal locally countable partial order
Call a poset locally countable if the set of predecessors of every member of the poset is countable. Is the following consistent?
There is no locally countable poset $P$ of size continuum such that ...
1
vote
1
answer
179
views
What does it mean to be meet dense? [closed]
What does it mean that a set of principal ideals is meet dense in a lattice of all order ideals?
4
votes
0
answers
128
views
Panyushev's conjectured duality for root poset antichains
In his 2004 paper "ad-nilpotent ideals of a Borel subalgebra: generators and duality" (https://www.sciencedirect.com/science/article/pii/S0021869303006380), Panyushev conjectured (Conjecture 6.1) the ...
8
votes
1
answer
235
views
Finite posets for which all intervals are atomic
Let $P$ be a finite poset which is a lattice with $0,1 \in P$.
An atom in $P$ is an upper cover of $0$ and a coatom is a lower cover of $1$.
$P$ is atomic if every element is a join of atoms and ...
3
votes
0
answers
258
views
Reference request: Representing posets by integer divisibility
Does anyone know of an early published reference for the (very easy) fact that all finite posets can be represented as the poset of divisibility of a finite set of integers?
Page 1 of Birkhoff's ...
0
votes
1
answer
132
views
Confluent partial orders
Let $(P, \le)$ be a poset such that
$$
\forall a, b, c \in P: b \ge a \le c \implies
\exists d \in P: b \le d \ge c.
$$
I am looking for literature where such confluent partial orders are studied.
7
votes
0
answers
223
views
Automorphism group of poset of number fields
Consider the poset of number fields, partial order being defined by inclusion of fields. What is the group of order-preserving automorphisms of this poset? What if we take only Galois extensions of $\...
8
votes
0
answers
150
views
Continuous analogues of Schützenberger promotion
Has anyone studied continuous analogues of Schützenberger promotion, and in particular, a flow on (a suitable subset of) the order polytope of a poset?
Here’s what I have in mind: Given a poset $P$, ...
9
votes
1
answer
249
views
Matroidal simplicial posets?
A simplicial poset is a finite poset $P$ with minimial element $\hat{0}$ such that every interval $[\hat{0},x]$ is isomorphic to a Boolean lattice. Simplicial posets are generalizations of simplicial ...
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 ...
8
votes
0
answers
624
views
Formula for number of edges in Hasse diagram of Young's lattice interval
There is a determinantal formula for the number of elements of the interval $[\mu,\lambda]$ of Young's lattice between two partitions due to Kreweras and MacMahon in the case of $\mu=\varnothing$ (see ...
5
votes
2
answers
229
views
$r$-differential posets: current state of the art
In the nice paper "On the rank function of a differential poset" (2011) by Richard Stanley and Fabrizio Zanello a number of interesting questions was asked about such posets. I would like to know ...
7
votes
0
answers
315
views
Criteria for a poset complex to be contractible
I would like to know if there are nice criteria to know if the ordered complex $C$ induced by a poset is contractible. I am also interested in the same question for subcomplexes of $C$.
$C$ happens ...
0
votes
1
answer
51
views
Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs
The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...
34
votes
11
answers
3k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
9
votes
2
answers
334
views
Is the poset of affine subspaces of a vector space highly connected?
The question is in the title. Fix a field $k$. Let $P_n$ be the poset of proper nonempty affine subspaces of $k^n$ under inclusion. The geometric realization $|P_n|$ is $n$-dimensional. Is it $(n-...
6
votes
2
answers
893
views
Poset dimension and width (Dilworth's theorem)
For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...
2
votes
0
answers
213
views
The word modular in the notion ``modular lattice''
Does the notion of modular lattice have anything to do with the meaning of the word modular, in either English or mathematics?
A finite modular lattice is a finite graded lattice $L$ whose rank ...
9
votes
2
answers
1k
views
Terminology about trees
In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders $P$ such that for every $...
2
votes
2
answers
182
views
Infima and suprema in the "transfer" function ordering
Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...
17
votes
1
answer
1k
views
How is this fixed point theorem related to the axiom of choice?
I'm hoping the answer to this is well-known.
Let $X$ be an ordered set (i.e. poset). An inflationary operator $f$ on $X$ is a function $f: X \to X$, not necessarily order-preserving, such that $f(x) \...
6
votes
1
answer
291
views
Does there exist a full and faithful embedding of $\mathsf{Poset}$ in $\mathsf{Set}$?
Does there exist a full and faithful embedding of the category of posets into the category of sets? I suspect no, but I don't know how to prove or disprove this.
0
votes
3
answers
391
views
Is every graph an incomparability graph?
Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$
(We write $v||w$ in ...
13
votes
2
answers
355
views
Connected incomparability graph
Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...
14
votes
1
answer
550
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 ...
7
votes
2
answers
342
views
Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$
Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...
4
votes
1
answer
210
views
Embedding ordinals with the order topology into connected $T_2$-spaces
Is there a limit ordinal $\kappa_0$ with $\kappa_0 \lt 2^{\aleph_0}$ and such that for every limit ordinal $\lambda$ with $\kappa_0\leq \lambda\lt 2^{\aleph_0}$ there is a connected $T_2$-space $X_\...
3
votes
0
answers
155
views
The name for injective map $f:\mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$ property
What is the name for map $f:\mathbb{N}\rightarrow\mathbb{N}$ (from natural numbers into natural numbers) with the following propeties:
1) $f$ is injective
2) $f(n)\geq n$ for every $n$?
0
votes
1
answer
131
views
Upward generators of $[\omega]^\omega$
If $(P,\leq)$ is a poset and $S\subseteq P$ we let $$\uparrow S = \{p\in P: p\geq s\text{ for some }s\in S\}.$$
Let $([\omega]^\omega,\subseteq)$ denote the collection of infinite subsets of $\omega$,...
7
votes
1
answer
385
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 ...
5
votes
1
answer
262
views
Order convergence vs topological convergence in partially ordered sets
Short version of the question. If $(P,\leq)$ is a partially ordered set (poset), a topology denoted by $\tau_o(P)$ can be defined (see below). There is also another notion of convergence, called order-...
5
votes
0
answers
162
views
(When) is the Dedekind-MacNeille completion of a po-set Hausdorff?
Let $X$ be a p.o. Consider the topology on $X$ generated by
$$U_{x}^{-}:=X\setminus (x\uparrow),\quad U_{x}^{+}:=X\setminus (x\downarrow), \quad x\in X$$
Throughout this discussion I shall refer to ...
0
votes
1
answer
247
views
Ordered group acting freely on partially ordered set
Let $(G, <)$ be a totally ordered group, and let $<$ be left-invariant. Let $G$ act (freely?) on a partially ordered set $(S, <)$, such that this group action preserves the ordering:
$$ s_1 &...
8
votes
1
answer
266
views
Is the measurable space $(\omega_1,\mathcal{P}(\omega_1))$ separable?
Here $\omega_1$ is the first uncountable ordinal, and $\mathcal{P}(\omega_1)$ denotes the power set of $\omega_1$. Separable means countably generated as a $\sigma$-algebra.
0
votes
1
answer
192
views
$\text{Max}\big(\text{Sub}(\text{Sym}(\omega))\setminus \{\text{Sym}(\omega)\}\big)$
If $G$ is any group, then by $\text{Sub}(G)$ we denote the collection of all subgroups, ordered by $\subseteq$. If $(P,\leq)$ is a partially ordered set we let $\text{Max}(P)$ and the set of maximal ...
2
votes
1
answer
297
views
Boolean completion of a partially ordered set
Given a poset $(P, \leq)$, is there a complete Boolean lattice $B$ and an order-preserving map $i_P: P\to B$ such that for any complete Boolean lattice $B'$ and order-preserving map $f: P\to B'$ ...
6
votes
2
answers
349
views
Is an Eulerian lattice shellable?
The notion of Eulerian lattice generalizes the notion of face lattice of a convex polytope.
(Bruggesse-Mani): The boundary complex of a convex polytope is shellable.
(Björner-Wachs): A poset is ...
4
votes
2
answers
283
views
Order-embedding, but no lattice embedding between distributive lattices
Let $L$ be the power set lattice ${\cal P}(\{0,1,2\})$. It is clear that there is an order-preserving injective map from $M_3$ into $L$, but no injective lattice homomorphism (because $L$ is ...
9
votes
3
answers
404
views
Does the lattice of all topologies embed into the lattice of $T_1$-topologies?
Let $\kappa$ be an infinite cardinal, and let $\text{Top}(\kappa)$ be the lattice of all topologies on $\kappa$, ordered by $\subseteq$. Let $\text{Top}^{T_1}(\kappa)$ be the lattice of all $T_1$-...