**60**

votes

**6**answers

14k views

### How many orders of infinity are there?

Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's ...

**34**

votes

**3**answers

1k views

### Is the fixed point property for posets preserved by products?

Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point.
Theorem. Suppose $P$ and $Q$ are posets ...

**22**

votes

**2**answers

1k views

### Does this poset have a unique minimal element?

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the ...

**19**

votes

**0**answers

312 views

### Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.
...

**17**

votes

**6**answers

3k views

### The category of posets

I am trying to teach myself category theory and, as a begginer, I am looking for
examples that I have a hands-on experience with.
Almost every introductory text in category theory contains following ...

**17**

votes

**1**answer

679 views

### Bruhat order and the Robinson-Schensted correspondence

The Robinson-Schensted correspondence is a bijection between elements of the symmetric group $S_n$ and pairs of standard tableaux of the same shape. The symmetric group is partially ordered by the ...

**16**

votes

**3**answers

1k views

### Banach and Knaster-Tarski fixed point theorems — are they related?

It there any known way of obtaining the Banach fixed-point theorem from the Tarski fixed-point theorem or vice-versa?

**15**

votes

**3**answers

4k views

### Proving that a poset is a lattice

I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...

**15**

votes

**3**answers

896 views

### Subposets of small Dushnik-Miller dimension

The Dushnik–Miller dimension of a partial order $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq_1},\ldots,{\leq_d}$ of total orderings of $P$ whose intersection is ${\leq}$, i....

**12**

votes

**1**answer

329 views

### Fastest algorithm to compute the width of a poset

An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out ...

**11**

votes

**1**answer

258 views

### Posets preserving stationary subsets of $\omega_1$ and no new $\text{cof}(\omega)$ ordinals, but without countable covering property

What are some examples of posets $\mathbb{P}$ which have the following properties? It's OK if the definition uses large cardinals or some other hypothesis.
$\mathbb{P}$ preserves stationary subsets ...

**11**

votes

**0**answers

397 views

### Asymptotic growth of antichains in divisibility posets

The following question is inspired by a problem that Erdős used to ask epsilons. It asks to prove that if one chooses a subset of $\lbrace 1,\dots,n\rbrace$ with more than $\lfloor\frac{n+1}{2}\rfloor$...

**10**

votes

**3**answers

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

**10**

votes

**2**answers

379 views

### Do operations generate well-ordered sets only?

I've read @TauMu's question about the set of functions $\mathbb N\rightarrow\mathbb N$ generated from the identity map by repeatedly applying exponentiation of two already ...

**10**

votes

**1**answer

816 views

### What is the size of a largest antichain in this poset?

Let $[n]:=\lbrace 1, \dots, n \rbrace$. We define a partial ordering on the set of subsets of $[n]$ as follows. We say that $X \preceq Y$ if there is an injective map $f:X \to Y$ such that $x \leq ...

**10**

votes

**2**answers

321 views

### Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...

**10**

votes

**1**answer

346 views

### When is the derived category of representations of a finite poset equivalent to its opposite?

If I have a finite partially ordered set $K$, I can look at its derived category of finite dimensional representations $D(K)$. Note that $D(K^{op}) \simeq D(K)^{op}$ by linear duality.
But when do ...

**9**

votes

**3**answers

239 views

### Is the homomorphism poset directed if the codomain is directed?

Let $P,Q$ be partially ordered sets (posets). We consider the set $\text{Hom}(P,Q)$ of order-preserving functions $f:P\to Q$. (We call a function $f:P\to Q$ order preserving if $x\leq y$ in $P$ ...

**9**

votes

**1**answer

172 views

### Are these two quotients of $\omega^\omega$ isomorphic?

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$. For $f,g\in\omega^\omega$ we say $f\simeq_{\text{fin}} g$ if there is $n\in \omega$ such that $f(k) = g(k)$ for all $k\geq n$.
...

**9**

votes

**2**answers

480 views

### How exactly does Schützenberger promotion relate to Striker-Williams promotion?

Schützenberger promotion, studied (for example) in Richard Stanley, Promotion and Evacuation, 2009, is a permutation of the set of all linear extensions of a finite poset. Since one can identify the ...

**9**

votes

**1**answer

449 views

### Does this property of a partially ordered set have a name?

What do you call a poset with this property? For any elements $a,b,c,d$ such that $\{a,b\}\le\{c,d\}$, there is an element x such that $\{a,b\}\le x\le\{c,d\}$. (Equivalently, for any finite sets $A\...

**9**

votes

**1**answer

337 views

### Set of maximal subfields not containing particular elements.

Instead of extending a field, by adjoining a new element, consider what happens if we remove an element or elements.
This started as a question on math.SE Field reductions where Pete L. Clark ...

**9**

votes

**1**answer

566 views

### Order homomorphism functions on $\omega_1$

Let $\omega_1$ be the first uncountable ordinal,
same as the set of all countable ordinals.
Let $F$ be the set of all functions
$f$ from $\omega_1$ minus singleton $0$ into $\omega_1$ that
are (a) ...

**9**

votes

**0**answers

83 views

### Ideals in strong Bruhat order

Recall that a (lower) ideal in a poset $(P, \le)$ is a subset $I\subset P$ such that $x\in I \Rightarrow y\in I$ for all $y\le x$. In am interested in ideals in finite Coxeter groups $W$ equipped ...

**9**

votes

**0**answers

121 views

### A family of posets

Consider the family of all (finite) posets that can be obtained by repeatedly applying one of the following three operations (starting e.g. with the empty poset):
(O1) Disjoint union of one or more ...

**8**

votes

**2**answers

647 views

### Statements forced by one condition of a poset, but not the whole thing

In order to get the relative consistency of some statement, it suffices to find a notion of forcing, and a condition $p$ in that forcing, such that $p$ forces the desired statement. It seems to be ...

**8**

votes

**2**answers

300 views

### Posets isomorphic to their endomorphism poset

Let $(P,\leq)$ be a poset. We set $$\text{End}(P)=\{f: P\to P: f\text{ is order-preserving}\}$$ and order $\text{End}(P)$ pointwise.
Is there a poset with more than 1 point such that $P\cong \text{...

**8**

votes

**1**answer

343 views

### Decomposing posets into countably many chains

A conjecture of Galvin's is that the following is possible (which I take to mean that the consistency of the following can be proven relative to the consistency of something like ZFC, or ZFC plus some ...

**8**

votes

**1**answer

147 views

### Optimal strategy for game of 'online sorting' into a poset

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution:
Each turn, the RNG produces a number, and the player must assign that ...

**8**

votes

**1**answer

173 views

### Extending subsets to supersets in different ways

We are given a collection of sets $A_1,\ldots,A_s$, pairwise different and each of cardinality $k$, and a collection of sets $B_1,\ldots,B_s$, pairwise different and each of cardinality $l>k+1$, ...

**8**

votes

**1**answer

513 views

### Ordered sum of posets

Let $I$ be a poset and for any $i$ let $P_i$ be a poset. Let $P$ be the sum over $I$ of the sets $P_i$, and let $<_P$ be the relation defined on $P$ by $q<_Pr$ iff $q$ and $r$ are members of the ...

**8**

votes

**0**answers

168 views

### Fixed points and universal maps for posets

In a recent post about f.p.p. for poset products, @M.Mirabi brought back an old-standing problem about the fixed point property of the product of two arbitrary posets which already enjoy the fixed ...

**7**

votes

**3**answers

718 views

### Characterizing forcings that don't add any dominating reals

Regarding reals as functions from $\omega$ to $\omega$, let's say a real $f$ eventually dominates $g$ iff $(\exists n)(\forall m > n)[ f(m) > g(m)]$. Let's say that a (non-trivial separative) ...

**7**

votes

**2**answers

425 views

### A sequence of generic filters that does not come from an iteration

Fix a countable transitive model $M$ of ZFC.
In my answer to this question I indicated that there are forcing iterations
$((Q_\alpha:\alpha\leq\omega),(\dot P_\alpha:\alpha<\omega))$ in $M$ and ...

**7**

votes

**2**answers

887 views

### Is every poset the poset of prime ideals of a ring?

The answer to this question, as it is, is trivially false, for one necessary condition is the existence of maximal element(s), i.e., maximal ideals exist and are prime.
My question was inspired from ...

**7**

votes

**1**answer

282 views

### Unique factorization of posets

Given two finite posets $P$ and $Q$, we can form the direct product poset $P \times Q$ whose elements are pairs $(p,q) \in P \times Q$ with $(p,q) \leq (p',q')$ if $p \leq p'$ and $q \leq q'$. Let us ...

**7**

votes

**1**answer

200 views

### Introducing meets while preserving directed closure

A poset $\mathbb{P}$ is called well-met iff every pair of compatible conditions in $\mathbb{P}$ has a greatest lower bound.
Question: Suppose $\mathbb{P}$ is a separative partial order which is $\...

**7**

votes

**1**answer

369 views

### Does this lattice have a name (and literature)?

The "lattice" in the title appears to be a lattice. At least it's a poset, which I define now.
Fix a partition $\lambda$ of $n$ and consider the set of all standard Young tableaux (each of $1,\dots,n$...

**7**

votes

**1**answer

387 views

### Posets of cosets and contractibility

For this question let $G$ be a group, perhaps infinite, and let $H_i$ for $i\in I$ be a (finite) family of subgroups closed under taking intersections. I am interested in the coset poset $\mathcal{C}(...

**7**

votes

**1**answer

310 views

### The category of categories and adjunctions

What is known about the category that has small categories as objects and adjunctions as morphisms? Obviously, it has neither terminal nor initial objects. But what about other kinds of limits? Are ...

**7**

votes

**1**answer

541 views

### Does ⋄ generate all De Morgan algebras?

(Asked by Nathaniel Hellerstein on the Q&A board at JMM)
This question is about De Morgan algebras (see also Wikipedia), which are something like Boolean algebras, but with a different weaker ...

**7**

votes

**1**answer

284 views

### Which of these relations on partial orders allows us to identify forcing equivalence?

Background
This question was inspired by Justin Palumbo's excellent question Cantor Bernstein for notions of forcing.
In his question, Justin considers a relation $\lhd$ on partial orders (defined ...

**7**

votes

**0**answers

237 views

### Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it.
A permutation on a $n$-...

**7**

votes

**0**answers

169 views

### Strength of claims about extensions of partial preorders and orders to linear ones

Consider these two axioms:
Every partial order extends to a linear order.
Every partial preorder (reflexive and transitive relation) extends to a linear preorder while preserving strict orderings: i....

**7**

votes

**0**answers

490 views

### The name for a partial order

In a recent paper of mine, my co-authors found that a partial order that we were using was contained in a paper by Kundgen. In it, he called it "right-shifted partial order". I was curious, and found ...

**6**

votes

**1**answer

234 views

### Terminology question for poset maps

Is there a standard name for order-preserving maps $f\colon P\to Q$ of posets with the property that the image of a lower set is a lower set, or equivalently if $q\leq f(p)$ then there exists $p'\leq ...

**6**

votes

**2**answers

261 views

### Is this algebra isomorphic to an incidence algebra?

This question is motivated by trying to establish a converse to Theorem 7.8 of our paper.
I have a finite poset $P$ with the following properties:
$P$ has binary meets (and hence a least element).
$...

**6**

votes

**0**answers

166 views

### “Double convolution” with the Mobius function on a poset

Let $f$ and $g$ be arbitrary (say integer-valued) functions on some poset $P$, and say $\mu$ is the Mobius function of $P$. I'm studying a quantity that's a sort of "double convolution" of $f$ and $g$ ...

**5**

votes

**5**answers

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

**5**

votes

**3**answers

1k views

### Constructing a metric over a lattice

Consider a lattice $({\cal L}, \wedge, \vee)$ with an antimonotonic function $f: {\cal L} \rightarrow {\mathbb R}$ defined on it (i.e $x \preceq y \implies f(x) \ge f(y)$).
$f$ is said to be ...