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

Filter by
Sorted by
Tagged with
1
vote
0answers
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
0answers
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
1answer
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
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
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
0answers
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
1answer
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
1answer
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
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
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
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
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
1answer
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
1answer
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
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
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
1answer
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
2answers
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
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
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
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
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
0answers
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
0answers
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
2answers
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
0answers
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
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 ...
9
votes
2answers
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
2answers
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
0answers
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
2answers
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
2answers
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
0answers
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
1answer
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) ...

1
2 3 4 5 6