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$).
404
questions
10
votes
2
answers
464
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 ...
- 7,472
9
votes
1
answer
499
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\...
user33772
7
votes
0
answers
250
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$ ...
- 1,510
11
votes
2
answers
831
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 ...
- 33.2k
24
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 ...
- 5,181
7
votes
1
answer
360
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 ...
- 1,166
6
votes
0
answers
204
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 $f_{-1}=...
- 3,482
3
votes
4
answers
1k
views
Minimal (semi)lattice containing a given poset
For a given poset, (I think that) it is easy to construct the minimal join-semilattice containing that poset. I wonder whether the minimal lattice containing that poset is also easy to construct. I ...
- 2,444
3
votes
0
answers
208
views
References for properties/examples of breadth in (semi)lattices
This is in some sense following up on my earlier question Is there existing terminology for this technical condition on semilattices? and the answer given by NN.
I am currently revising the paper ...
- 25.5k
12
votes
1
answer
529
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 ...
- 6,664
3
votes
3
answers
489
views
Characterizing posets by functions into natural numbers
Let $P$ be a poset and denote by $\operatorname{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 ...
- 607
20
votes
1
answer
970
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 ...
- 2,681
3
votes
1
answer
337
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 ...
- 33.2k
36
votes
6
answers
12k
views
The category of posets
I am trying to teach myself category theory and, as a beginner, I am looking for
examples that I have a hands-on experience with.
Almost every introductory text in category theory contains following ...
1
vote
1
answer
529
views
Group of divisibility of a commutative domain
We know that the necessary condition for any partially ordered group to be a group of divisibility is that the group must be a directed group. What is the sufficient condtion for partially ordered ...
- 33
13
votes
1
answer
613
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$...
- 85.1k
3
votes
3
answers
2k
views
Well-ordered cofinal subsets [closed]
Let $(P, \leq)$ be a total ordering (some of you prefer the name linear order). Can we find a subset $R\subseteq P$ which is well ordered (with respect to $\leq\upharpoonright R$) and cofinal in $P$, ...
- 113
2
votes
1
answer
421
views
What are $n$-poset?
Yesterday I was wandering for the $n$-lab and I've found the definition of $n$-poset.
Following this post it seems that a $n$-poset should be a $(n,n+1)$-category.
Now an $(n,r)$-category should be a ...
- 3,299
11
votes
1
answer
2k
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 ...
- 31.5k
0
votes
0
answers
118
views
A search for optimal order ideals
At the behest of Gerhard Paseman I'll describe the problem that I alluded to in
name for a partial order.
Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers $\mathbb{N}$...
- 4,626
8
votes
0
answers
614
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 ...
- 4,626
1
vote
1
answer
2k
views
What is the number of maximal antichain in a poset?
This is a topic I am recently working on. Given a poset, how many different antichains are there?
I find little literature on it. And I am interested whether there is a closed formula, or a tight ...
- 133
9
votes
1
answer
942
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 ...
- 2,617
7
votes
1
answer
492
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}(...
- 1,670
3
votes
1
answer
337
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 ...
- 203
0
votes
0
answers
206
views
Ordering labellings of a fixed poset
Let $\{A_1,\ldots, A_m\}$ be a family of sets and $I=\{1, \ldots, m\}$. Assume for any $J\subset I$, $B_J=\bigcap_{i\in J}A_j$ satisfies $1\leq |B_J| \leq m-1$ as long as $|J|>1$.
We define a ...
- 1
13
votes
2
answers
2k
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 ...
- 879
5
votes
1
answer
1k
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 ...
8
votes
2
answers
825
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 ...
- 3,992
4
votes
1
answer
590
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
230
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,992
8
votes
1
answer
408
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 ...
- 3,992
0
votes
1
answer
464
views
Terminology for posets.
What should I call a poset with the property that each element has AT MOST ONE
predecessor?
(I'm actually interested in the special case in which there are no infinite descending chains.)
...
- 12.5k
1
vote
2
answers
3k
views
On the number of antichains of a poset
I am not an expert in combinatorics, but I need to count (or to approximate) the number of antichains of a poset.
The idea relies on approximating this number by embedding my poset into another one, ...
- 133
9
votes
1
answer
438
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 ...
- 301
8
votes
1
answer
602
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 ...
- 3,247
7
votes
3
answers
1k
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) ...
- 3,992
3
votes
2
answers
677
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,992
3
votes
2
answers
1k
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< ...
2
votes
1
answer
326
views
Count of lattices on finite set
Let $p(n)$ denote count of lattices on finite set $G$, $|G|=n$ (without isomorphism). It's know closed formula for $p(n)$?
It's clear, that $1 \leq p(n)$ and also that $p(n-1) \leq p(n)$ for $n \geq ...
- 125
3
votes
1
answer
355
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}$ ...
- 43.6k
5
votes
0
answers
617
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 $x$...
- 5,563
16
votes
3
answers
10k
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 ...
- 5,563
7
votes
2
answers
680
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 ...
- 16.4k
17
votes
3
answers
2k
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?
- 11.7k
2
votes
1
answer
356
views
Selecting k sub-posets
I ran into the following algorithmic problem while experimenting with classification algorithms. Elements are classified into a polyhierarchy, what I understand to be a poset with a single root ("...
- 123
86
votes
7
answers
20k
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 ...
- 109k
18
votes
4
answers
1k
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....
- 43.7k
2
votes
0
answers
130
views
non-degenarete tools to calculate a derived functor on a model category which is a poset?
Are there theorems (esp. computational tools) on model categories which survive and do not trivialise when its underlying category is a (quasi-)poset ? Are there tools
that may help to calculate a ...
- 1,299
1
vote
2
answers
1k
views
Proof of glb and lub of Lexicographic Product of poset
Is there a book, or a paper where the Lexicographic glb and lub are proven commutative, associative, idempotent and absorbing. I have already proven this, but would like to check proofs, and a short ...
- 71