# 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$).

269
questions

**1**

vote

**0**answers

25 views

### Posets which extend centered sets to filters

(Post cross-posted from math.se.)
Suppose $(\mathcal O, \leq)$ is an arbitrary poset. Let us say that $\mathcal O$ is compact if every $\mathcal C\subseteq\mathcal O$ which is centered (any finite ...

**1**

vote

**0**answers

84 views

### Do you recognise this setup of structure on a poset?

The setup is that we have a finite poset $P$, with a multiplicative rank function $r_{xy}:P\times P\rightarrow \mathbb{N}$, and a symmetric pairing $\langle\ ,\ \rangle:P\times P\rightarrow\mathbb{N}$....

**10**

votes

**1**answer

279 views

### Poset-troids …?

In many respects,
spanning tree : graph :: linear extension : poset
For instance, the number of spanning trees/linear extensions is a measure of the "richness" or "complexity" of the graph/poset. ...

**0**

votes

**0**answers

42 views

### Number of minimal elements of product order

Consider three sets: $A = \{1,2,\dotsc,n_A\}$, $B=\{1,2,\dotsc,n_B\}$, and $C=\{1,2,\dotsc,n_C\}$, where $n_A, n_B, n_C \ge 2$. Define a product order (which is a partial order) on the cartesian ...

**1**

vote

**2**answers

71 views

### Is this ordering on the set of all covers of $\omega$ a (complete) lattice?

Let ${\frak C} \subseteq {\cal P}({\cal P}(\omega))$ be the collection of all covers of $\omega$ (that is, ${\cal C} \in {\frak C}$ iff $\bigcup {\cal C} = \omega$.)
We define the following binary ...

**-1**

votes

**1**answer

89 views

### (maximal) antichains with respect to two different partial orders on the same set

In my recent work I stumbled across a problem of this type:
G with two partial oders $\leq$ and $\preceq$ on every set, i.e. for every $n \in \mathbb{N}$ $A_n \subset A_{n+1}$ and $(A_n, \leq) $ and $...

**7**

votes

**0**answers

119 views

### Is the order complex of open Bruhat intervals polytopal?

Let $P$ be the Bruhat order of a Coxeter group, and let $s<t$ in
$P$. The set $\Delta(s,t)$ of all chains of the open interval $(s,t)$
(called the order complex of $(s,t)$) is a simplicial complex. ...

**7**

votes

**1**answer

139 views

### Bounding and domination numbers for relation $\leq$ modulo $\omega$-nullsets

We say that $A\subseteq \omega$ is a nullset if $$\lim\sup_{n\to \infty} \frac{|A\cap n|}{n+1} = 0.$$
Let $\omega^\omega$ denote the set of functions $f:\omega\to\omega$. We define a pre-ordering ...

**1**

vote

**1**answer

70 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 $\...

**19**

votes

**3**answers

1k views

### Cyclic action on Kreweras walks

A Kreweras walk of length $3n$ is a word consisting of $n$ $A$'s, $n$ $B$'s, and $n$ $C$'s such that in any prefix there are at least as many $A$'s as $B$'s, and at least as many $A$'s as $C$'s. For ...

**4**

votes

**1**answer

220 views

### Does the lattice of partitions map onto the lattice of subsets?

Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,...

**2**

votes

**1**answer

122 views

### Poset filtrations

Consider a chain complex $C$ and a poset $P$ so that there is a filtration by subcomplexes $C^p$ of $C$ where $p\in P$ in such a way that $p<q$ implies $C^p \leqslant C^q$.
As a second option, ...

**10**

votes

**1**answer

164 views

### Is there a relation between type (maximum linearization) of a computable WQO and the ordinal strength of a theory needed to prove it?

Background:
Given a well partial order $X$ (more commonly studied with antisymmetry dropped as well-quasi-orders, but I'm going to say well partial order to make this definition simpler, obviously ...

**2**

votes

**2**answers

237 views

### A formula for a right adjoint in terms of a left

For those familiar with (covariant) Galois connections, you may have noticed that they can be viewed as categorical adjunctions. A Galois connection is a pair of maps between posets $X$ and $Y$
$$ f_{\...

**4**

votes

**0**answers

61 views

### Families that can arise as compacts wrt a topology

I was thinking to the following problem.
Take a set $X$. If you take a compact topology T (non necessarily Hausdorff) you get the subposet $K_T$ of $\mathcal{P}(X)$ made of compact sets with respect ...

**8**

votes

**0**answers

262 views

### Possible oversight in paper of Greene and Kleitman on chains in dominance order on partitions?

This question is about a possible lacuna in a paper of Greene and Kleitman which Zarathustra Brady made me aware of.
The paper in question is "Longest Chains in the Lattice of Integer Partitions ...

**3**

votes

**1**answer

127 views

### Map on class of all finite posets coming from maximal sized antichains

Let $P$ be a finite poset. Let $\mathcal{A}$ denote the set of antichains of $P$. Equip $\mathcal{A}$ with a partial order $\preceq$ whereby $X \preceq Y$ means for all $x \in X$ there exists $y \in Y$...

**12**

votes

**1**answer

210 views

### Permanent of the Coxeter matrix of a distributive lattice

Let $L$ be a finite distributive lattice with $n$ elements. Let $C=(c_{x,y})$ be the $n \times n$ matrix with entry 1 in case $x \leq y$ and 0 else.
The Coxeter matrix of $L$ is defined as the matrix $...

**2**

votes

**1**answer

120 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 ...

**7**

votes

**0**answers

256 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 ...

**24**

votes

**3**answers

1k 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

113 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

76 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

194 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

68 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 ...

**1**

vote

**1**answer

182 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

108 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 ...

**12**

votes

**2**answers

373 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

58 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 ...

**1**

vote

**1**answer

99 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

93 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 ...

**7**

votes

**1**answer

109 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

189 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

83 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

198 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

115 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

151 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

329 views

### How should the proof of the XYZ theorem be understood?

The XYZ Theorem of Shepp [1] states that 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 any three ...

**8**

votes

**0**answers

216 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

187 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

102 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

41 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)$.
...

**32**

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

234 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

344 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

106 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

158 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 ...

**2**

votes

**0**answers

77 views

### Obtaining the reduced incidence algebra in QPA

Given a finite poset $P$ (we can assume it is connected), the reduced incidence algebra of $P$ is the subalgebra of the incidence algebra of $P$ consisting of functions constant on isomorphic ...

**17**

votes

**1**answer

659 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) ...