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
2 votes
1 answer
182 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 ...
Gershom B's user avatar
  • 123
12 votes
1 answer
598 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 ...
Sam Hopkins's user avatar
  • 22.7k
26 votes
3 answers
2k 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 ...
Ethan Splaver's user avatar
1 vote
1 answer
123 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 $...
Leijie Wang's user avatar
1 vote
1 answer
96 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-...
Dominic van der Zypen's user avatar
6 votes
1 answer
207 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 ...
Dominic van der Zypen's user avatar
0 votes
0 answers
73 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 ...
Zach Hunter's user avatar
  • 3,393
2 votes
1 answer
354 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$ ...
rick's user avatar
  • 166
1 vote
1 answer
174 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 ...
Mario Román's user avatar
15 votes
4 answers
695 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 ...
Sam Hopkins's user avatar
  • 22.7k
1 vote
0 answers
65 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 ...
Anton Salikhmetov's user avatar
16 votes
1 answer
595 views

Universal locally countable partial order

Call a poset locally countable if the set of predecessors of every member of the poset is countable. Is the following consistent? There is no locally countable poset $P$ of size continuum such that ...
Ashutosh's user avatar
  • 9,771
1 vote
1 answer
179 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?
Nassima Kabyle's user avatar
4 votes
0 answers
128 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 ...
Sam Hopkins's user avatar
  • 22.7k
8 votes
1 answer
235 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 ...
Christian Stump's user avatar
3 votes
0 answers
258 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 ...
David Eppstein's user avatar
0 votes
1 answer
132 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.
Anton Salikhmetov's user avatar
7 votes
0 answers
223 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 $\...
user138266's user avatar
8 votes
0 answers
150 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$, ...
James Propp's user avatar
  • 19.4k
9 votes
1 answer
249 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 ...
Sam Hopkins's user avatar
  • 22.7k
4 votes
0 answers
511 views

How should the proof of the XYZ theorem be understood?

The XYZ Theorem of Shepp [1] states the following 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 ...
Hao's user avatar
  • 571
8 votes
0 answers
624 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 ...
Sam Hopkins's user avatar
  • 22.7k
5 votes
2 answers
229 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 ...
Fedor Petrov's user avatar
7 votes
0 answers
315 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 ...
María's user avatar
  • 171
0 votes
1 answer
51 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)$. ...
Dominic van der Zypen's user avatar
34 votes
11 answers
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
2 answers
334 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-...
Katie's user avatar
  • 93
6 votes
2 answers
893 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 = \...
Otto's user avatar
  • 1,006
2 votes
0 answers
213 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 ...
David Wang's user avatar
9 votes
2 answers
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 $...
Monroe Eskew's user avatar
  • 18.1k
2 votes
2 answers
182 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 ...
Dominic van der Zypen's user avatar
17 votes
1 answer
1k 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) \...
Tom Leinster's user avatar
  • 27.2k
6 votes
1 answer
291 views

Does there exist a full and faithful embedding of $\mathsf{Poset}$ in $\mathsf{Set}$?

Does there exist a full and faithful embedding of the category of posets into the category of sets? I suspect no, but I don't know how to prove or disprove this.
Jesse Elliott's user avatar
0 votes
3 answers
391 views

Is every graph an incomparability graph?

Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$ (We write $v||w$ in ...
Dominic van der Zypen's user avatar
13 votes
2 answers
355 views

Connected incomparability graph

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...
Nik Weaver's user avatar
14 votes
1 answer
550 views

"Scott completion" of dcpo

If $A$ is poset with all directed suprema, it is common to consider the Scott topology on $A$, whose open subsets are the $U \subset A$ such that $U$ is upward closed and if $\bigcup_I a_i \in U $ for ...
Simon Henry's user avatar
  • 39.9k
7 votes
2 answers
342 views

Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...
Dominic van der Zypen's user avatar
4 votes
1 answer
210 views

Embedding ordinals with the order topology into connected $T_2$-spaces

Is there a limit ordinal $\kappa_0$ with $\kappa_0 \lt 2^{\aleph_0}$ and such that for every limit ordinal $\lambda$ with $\kappa_0\leq \lambda\lt 2^{\aleph_0}$ there is a connected $T_2$-space $X_\...
Dominic van der Zypen's user avatar
3 votes
0 answers
155 views

The name for injective map $f:\mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$ property

What is the name for map $f:\mathbb{N}\rightarrow\mathbb{N}$ (from natural numbers into natural numbers) with the following propeties: 1) $f$ is injective 2) $f(n)\geq n$ for every $n$?
Lyudmyla Polyakova's user avatar
0 votes
1 answer
131 views

Upward generators of $[\omega]^\omega$

If $(P,\leq)$ is a poset and $S\subseteq P$ we let $$\uparrow S = \{p\in P: p\geq s\text{ for some }s\in S\}.$$ Let $([\omega]^\omega,\subseteq)$ denote the collection of infinite subsets of $\omega$,...
Dominic van der Zypen's user avatar
7 votes
1 answer
385 views

Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history

Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces. Counting the ...
Stefan Forcey's user avatar
5 votes
1 answer
262 views

Order convergence vs topological convergence in partially ordered sets

Short version of the question. If $(P,\leq)$ is a partially ordered set (poset), a topology denoted by $\tau_o(P)$ can be defined (see below). There is also another notion of convergence, called order-...
Dominic van der Zypen's user avatar
5 votes
0 answers
162 views

(When) is the Dedekind-MacNeille completion of a po-set Hausdorff?

Let $X$ be a p.o. Consider the topology on $X$ generated by $$U_{x}^{-}:=X\setminus (x\uparrow),\quad U_{x}^{+}:=X\setminus (x\downarrow), \quad x\in X$$ Throughout this discussion I shall refer to ...
Thomas's user avatar
  • 263
0 votes
1 answer
247 views

Ordered group acting freely on partially ordered set

Let $(G, <)$ be a totally ordered group, and let $<$ be left-invariant. Let $G$ act (freely?) on a partially ordered set $(S, <)$, such that this group action preserves the ordering: $$ s_1 &...
lunchmeat's user avatar
8 votes
1 answer
266 views

Is the measurable space $(\omega_1,\mathcal{P}(\omega_1))$ separable?

Here $\omega_1$ is the first uncountable ordinal, and $\mathcal{P}(\omega_1)$ denotes the power set of $\omega_1$. Separable means countably generated as a $\sigma$-algebra.
Héctor's user avatar
  • 515
0 votes
1 answer
192 views

$\text{Max}\big(\text{Sub}(\text{Sym}(\omega))\setminus \{\text{Sym}(\omega)\}\big)$

If $G$ is any group, then by $\text{Sub}(G)$ we denote the collection of all subgroups, ordered by $\subseteq$. If $(P,\leq)$ is a partially ordered set we let $\text{Max}(P)$ and the set of maximal ...
Dominic van der Zypen's user avatar
2 votes
1 answer
297 views

Boolean completion of a partially ordered set

Given a poset $(P, \leq)$, is there a complete Boolean lattice $B$ and an order-preserving map $i_P: P\to B$ such that for any complete Boolean lattice $B'$ and order-preserving map $f: P\to B'$ ...
Dominic van der Zypen's user avatar
6 votes
2 answers
349 views

Is an Eulerian lattice shellable?

The notion of Eulerian lattice generalizes the notion of face lattice of a convex polytope. (Bruggesse-Mani): The boundary complex of a convex polytope is shellable. (Björner-Wachs): A poset is ...
Sebastien Palcoux's user avatar
4 votes
2 answers
283 views

Order-embedding, but no lattice embedding between distributive lattices

Let $L$ be the power set lattice ${\cal P}(\{0,1,2\})$. It is clear that there is an order-preserving injective map from $M_3$ into $L$, but no injective lattice homomorphism (because $L$ is ...
Dominic van der Zypen's user avatar
9 votes
3 answers
404 views

Does the lattice of all topologies embed into the lattice of $T_1$-topologies?

Let $\kappa$ be an infinite cardinal, and let $\text{Top}(\kappa)$ be the lattice of all topologies on $\kappa$, ordered by $\subseteq$. Let $\text{Top}^{T_1}(\kappa)$ be the lattice of all $T_1$-...
Dominic van der Zypen's user avatar

1 2 3
4
5
9