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$).
275
questions
4
votes
0answers
49 views
Which posets can occur from commutative Frobenius algebras?
Let $A$ be a commutative Frobenius algebra. We can assume that $A$ is local and $A=K[x_i]/(I)$ for some variables $x_1,...,x_n$ and an admissible ideal.
Then the non-zero monomials $u_i$(including 1) ...
6
votes
2answers
286 views
Group structure for distributive lattices
On the (finite) Boolean lattice there is a group structure given by the symmetric difference and this group is an elementary abelian 2-group.
Question: Does there exist a natural group structure on ...
9
votes
0answers
196 views
Distributivity of certain infinite products
Suppose we have a sequence of posets $\{\mathbb P_n : n\in\omega\}$ such that for each $n$, $\mathbb P_{n+1}$ is $|\mathbb P_n|^+$-distributive. Is $\prod_{n>0} \mathbb P_n$ necessarily $|\mathbb ...
3
votes
0answers
83 views
Shellability and order filters in the partition lattice
Choose $n\in\mathbb N$. Let $B$ be a non-empty subset of $[n]:=\{1,2,\dots,n\}$. Consider the set of partitions of the set $[n]$ with exactly $|B|$ parts such that each part has exactly one member ...
2
votes
0answers
67 views
Non-commutative version of the order dimension of a poset
I view the order dimension of a poset $P$ as an inherently commutative notion. On the one hand, it can be defined via realizers, which I find fairly intuitive from an order-theoretic viewpoint. On the ...
4
votes
2answers
176 views
The average size of downward closed family of the subsets of $[n]$ is at most $n/2$?
I learned that the average size in any ideal of subsets of $[n]$ is at most $n/2$, but I think the downward closed family of the subsets of $[n]$ also satisfied. I want to know how to proof it or it ...
2
votes
0answers
57 views
Outer automorphisms of incidence algebras of distributive lattices
Let $L$ be a finite distributive lattice with incidence algebra $I(L)$ over a field $K$.
Then there is the result that any automorphism of $I(L)$ is given by the composition of an inner automorphism ...
1
vote
0answers
28 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
0answers
86 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
1answer
285 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
0answers
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
2answers
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
1answer
90 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 $...
8
votes
0answers
156 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
1answer
140 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
1answer
72 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
3answers
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
1answer
221 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
1answer
126 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
1answer
166 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
2answers
242 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
0answers
62 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
0answers
269 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
1answer
129 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
1answer
213 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
1answer
121 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 ...
10
votes
1answer
423 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
3answers
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
1answer
114 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
1answer
77 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
1answer
195 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
0answers
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
1answer
189 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
1answer
111 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
4answers
492 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
0answers
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
1answer
104 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
0answers
98 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
1answer
110 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
0answers
190 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
1answer
84 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
0answers
201 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
0answers
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
1answer
152 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
0answers
336 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
0answers
221 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
2answers
191 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
0answers
107 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
1answer
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
11answers
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 ...
