**48**

votes

**6**answers

11k 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 ...

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

**15**

votes

**0**answers

216 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$.
...

**14**

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?

**14**

votes

**3**answers

2k 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 ...

**14**

votes

**1**answer

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

**14**

votes

**3**answers

807 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}$, ...

**13**

votes

**6**answers

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

**10**

votes

**2**answers

309 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

643 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

**1**answer

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

**10**

votes

**0**answers

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

**9**

votes

**2**answers

267 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

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

**9**

votes

**1**answer

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

**8**

votes

**2**answers

502 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

**1**answer

318 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

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

**7**

votes

**3**answers

567 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

368 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

**1**answer

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

**7**

votes

**1**answer

241 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

**1**answer

489 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

**0**answers

140 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: ...

**7**

votes

**0**answers

397 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

**2**answers

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

199 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

**1**answer

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

**6**

votes

**0**answers

127 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

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

**5**

votes

**1**answer

355 views

### Does “antichain” mean something different in set-forcing than in lattice theory?

On page 3 of Introduction to Lattices and Order, Davey and Priestley define an antichain in a poset $\langle P,\leq\rangle$ as a set of pairwise incomparable elements:
The ordered set P is an ...

**5**

votes

**1**answer

333 views

### Minimum set cardinality for a given partially ordered set

Let S be a finite set of cardinality k. I consider subsets of S that I order by set inclusion. For any given k, this defines the partially ordered set S_k.
To a given partially ordered set P, I ...

**4**

votes

**4**answers

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

**4**

votes

**1**answer

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

**4**

votes

**2**answers

424 views

### Is every lattice the fixed-point set of an order endomorphism of ⋄^n?

(Asked by Nathaniel Hellerstein on the Q&A board at JMM)
Let ⋄ be the 4 element lattice
τ
/ \
i j
\ /
f
Is every lattice isomorphic to the fixed point lattice of some ...

**4**

votes

**1**answer

308 views

### On the barycentric subdivision of a poset

Hi everybody,
I'm interested in the barycentric subdivision of a poset $P$, defined as the face poset of the corresponding order complex $\mathcal F(\Delta(P))$ (or alternatively, the poset of chains ...

**4**

votes

**1**answer

292 views

### Posets of finite sequences are highly connected

I need the following result for an example in a paper I'm writing. It's easy enough to prove, but I'd prefer to just give a reference. Does anyone know one?
Fix $1 \leq k \leq n$. Define $X_{n,k}$ ...

**4**

votes

**1**answer

164 views

### About subposet of Levy collapse

Let $\lambda>\kappa$ and $\operatorname{Coll}(\kappa, \lambda)$ be the poset collapsing $\lambda$ to $\kappa$. Pick a subposet $P$ which is $\lt\kappa$-closed and of size $\lambda$. Can we say that ...

**3**

votes

**2**answers

489 views

### A problem about posets similar to Suslin's problem

Suslin's problem is:
Given a complete dense linear order without endpoints, if it has the ccc must it be isomorphic to $\mathbb{R}$?
The answer is that it's independent of ZFC. The related ...

**3**

votes

**2**answers

621 views

### Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

Consider two partially ordered sets $A = \{a< b,a< c\}$, $B=\{x< z,y< z\}$.
Their linear extensions (here we allow equality in linear extensions) for $A, B$ are
$$A_L=\{A_1=\{a< b< ...

**3**

votes

**1**answer

273 views

### A compactness property of posets

Consider a poset $P$ and suppose that every finite subset admits a supremum. Call an ideal $I$ of $P$ minimal infinite if it is infinite and every ideal properly contained in $I$ is finite. I am ...

**3**

votes

**1**answer

154 views

### Decomposing a poset into directed subposets

Let us say that a poset $P$ is $\mathbf{\kappa}$-directed iff every collection of fewer than $\kappa$-many elements in $P$ has an upper bound in $P$. $P$ has the $\mathbf{\kappa}$ chain condition iff ...

**3**

votes

**1**answer

106 views

### Matching in the Boolean Algebra

We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show ...

**3**

votes

**1**answer

254 views

### Grading a non-graded poset as squeezed as possible

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage).
Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...

**3**

votes

**0**answers

154 views

### When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where ...

**3**

votes

**0**answers

124 views

### references for properties/examples of breadth in (semi)lattices

This is in some sense following up on my earlier question and the answer given by NN.
I am currently revising the paper which used the condition mentioned in my question. It was pointed out in NN's ...

**3**

votes

**0**answers

342 views

### a poset with small “cycles”

(a followup to this recent question)
I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that...):
Suppose that $z$ is covered by ...

**2**

votes

**2**answers

304 views

### Characterizing Posets by Functions Into Natural Numbers

Let $P$ be a poset and denote by $Hom(P, \mathbb N)$ the set of all monotone functions from $P$ to natural numbers $\mathbb N$. Under what conditions on $P$ Is it possible to recover the order on $P$ ...

**2**

votes

**1**answer

111 views

### Galois Connections: algorithmic generation

Given two finite posets $P,Q$, is it known any algorithm to count and/or generate every Galois Connection between $P$ and $Q$ ?
I'm looking for references about this problem.