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

346 questions
Filter by
Sorted by
Tagged with
81 views

### Digraph without "immediately isomorphic" vertices?

Say that a digraph $(V,E)$ is reducible if there exist $x,y\in V$ with $x\ne y$ and such that for all $z\in V$, $(x,z)\in E\leftrightarrow(y,z)\in E$ and $(z,x)\in E\leftrightarrow(z,y)\in E$. It is ...
603 views

### Matrices of combinatorial sequences that are inverse in two ways

I'm interested in pairs $A=(a_{i,j})_{i,j=0,1,\ldots}$ and $B=(b_{i,j})_{i,j=0,1,\ldots}$ of infinite matrices for which: They are uni-lower-triangular, i.e., $a_{i,i}=1$ for all $i$ and $a_{i,j}=0$ ...
86 views

88 views

### Classification of multiplicative lattices

Question 1:Is there a classification of finite lattices which admit a multiplication making them into a finite multiplicative lattices? (see https://encyclopediaofmath.org/wiki/Multiplicative_lattice ...
172 views

### Order ideals of positive root systems and avoiding group elements in the Weyl group

Let $X$ be the poset of positive roots of a finite root system of Dynkin type $Q$. Question 1: In Dynkin type $A_n$, is it true that the poset of order ideals of $X$ is isomorphic to the poset of [2,...
1 vote
79 views

66 views

### Is $(\omega+1)^\omega/{\cal U}$ "unique"?

If ${\cal U}_i$ free ultrafilters on $\omega$ for $i = 1,2$ , are the ultrapowers $(\omega+1)^\omega/{\cal U}_i$ necessarily isomorphic as lattices for $i = 1,2$?
313 views

### Which finite posets are Koszul self-dual?

Let $P$ be a finite connected poset with incidence algebra $A_P$. For the definition and results on Koszul algebras for incidence algebras, see for example here Question: Which posets have the ...
144 views

### coset poset of reflection subgroup

Fix a finitely generated Coxeter system $(W, S)$, and let $W_J$ denote the standard parabolic proper subgroup generated by a subset $J \subset S$. It is well known that the poset of cosets $\{xW_J\}$ ...
99 views

### Which Boolean lattices have a left-to-right symmetric drawing?

This question is inspired by a similar MSE question about partition lattices. Question: Which finite Boolean lattices have a symmetric drawing on the 2D plane? By a symmetric drawing of a lattice, I ...
207 views

### "Pseudo-Boolean" lattice (almost every element has several complements)

If $(L,\leq)$ is a lattice with bottom element $0$ and top element $1$ and $x\in L$ we say that $y$ is a complement of $x$ if $x\vee y = 1$ and $x\wedge y = 0$. Is there a lattice $(L,\leq)$ with more ...
1 vote
53 views

### Dimension of the cartesian product of a poset and a chain

Let $P$ be a finite poset and for $n\in\mathbb N$, let $\bf n$ denote the $n$-element totally ordered set. If $m,n\in\mathbb N$ and $1<m<n$, is the dimension of $P\times \bf m$ equal to the ...
146 views

1 vote
54 views

### inequivalent vertex weights on finite poset

Let $m\geq1$ and $P$ be an arbitrary poset with vertex set $V=\{v_1,\dots,v_n\}$, edge set $E,$ and set $O$ of orbits under $\text{Aut}(P).$ Can we efficiently generate all inequivalent nonnegative ...
113 views

### Number of elements in poset with same rank such that lower bound has a certain rank

I was wondering if anything is known about this problem. Fix $0\leq m\leq k$. We are given a graded poset and we fix an element $x$ of rank $k$. Is it possible to estimate the number of elements $y$ ...
59 views

### Linear extensions of divisor poset of a positive integer

Consider $n = p^k$ where p is prime and $k \ge 2$. Let $D_n =\{ p, \dots, p^{k-1}\}$ be the set of proper divisors of $n$. Now, the divisor poset in the set $D_n$ is linearly ordered and further ...
285 views

### Is the set of approximating sequences for irrationals dominating?

Let $r\in [0,1]\setminus\mathbb{Q}$, let $\mathbb{N}$ denote the set of non-negative integers and let $\mathbb{N}_+=\mathbb{N}\setminus\{0\}$. For $n\in\mathbb{N}_+$ let \alpha_r(n)=\min\{|r-\frac{...
105 views

### About finite posets without intervals of size 3

Let $P$ be a finite poset (partially ordered set). I am wondering whether the following condition on $P$ has been studied somewhere: (#) No interval $[a,b]$ in $P$ has $3$ elements. Note that ...
156 views

807 views

### Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?

Zorn’s Lemma applies to posets in which every chain has an upper bound. However, in all applications I know, the poset is also evidently chain-complete — chains have least upper bounds. A few ...
102 views

### What do you call such a relation between subsets in a poset

Consider a poset $(X, \geq)$. Let's define a new relation $\succsim$ on subsets of $X$: for $A, B\subseteq X$, say $A\succsim B$ if for any $a\in A$ and any $b\in B$, we have $a\geq b$. Does such a ...
222 views

### Objects in bijection with integer partitions (and lattices)

A partition of $n$ is a non-increasing sequence of positive integers of sum $n$. Several lattices are defined over integer partitions, in particular the dominance order and the Young lattice. Several ...
677 views

### What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...
388 views

### What is the Möbius function of substrings?

Define a poset on the set of all finite binary strings, defined by $a \le b$ whenever $b = uav$ for (possibly empty) binary strings $u, v$. What is the Möbius function of this poset?
105 views

### Tameable hypergraphs

Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$. We say that $H$ is tameable if every independent set is contained in a maximal ...
150 views

A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,... 10 votes 3 answers 1k views ### Listing all posets on 9 points? I'm looking for a list of all (non-isomorphic) posets on 9 points. I know there are 183231 of them (OEIS A000112), but in order to progress with a problem I'm working on, I'd need the posets ... 3 votes 1 answer 158 views ###${\frak b}$and${\frak d}$in the Rudin-Keisler preordering If$(Q,\leq)$is any preordered set (that is,$\leq$is a reflexive and transitive, but not necessarily anti-symmetric relation), then we say that$S\subseteq Q$is unbounded if for all$q\in Q$... 1 vote 1 answer 83 views ### Minimizing the set of monochromatic edges For sets$A, B$we write$B^A$for the set of all functions$f:A\to B$. Let$H = (V,E)$be a hypergraph such that$V,E\neq\varnothing$and$|e| \geq 2$for all$e\in E$. Let$\kappa>1$be a ... 6 votes 1 answer 176 views ### Sum of order polynomials of a set of posets Let$n\in \mathbb{Z}_{>0}$. For every subset$S\subseteq \left[ n-1\right]$we define a poset$P_S=\left([n],\le_{P_S}\right)$given by the covering relation$\lessdot$which is defined as \begin{... 6 votes 1 answer 277 views ### Can one characterize maximal antichains in terms of distributive lattices? This is inspired by the recent question Verification of a maximal antichain The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them ... 8 votes 1 answer 311 views ### Verification of a maximal antichain In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ... 1 vote 0 answers 104 views ### Complexity of a poset Let$M$be a an integer$s \times s$matrix. Define the complexity of$M$as$cx(M):= \inf \{ n \geq 0 | \exists C \in \mathbb{N} , \ \forall t \in \mathbb{N} : \| M^t \| \leq C t^{n-1} \}$. Here$\| ...
Let $(X, \le)$ be a partially ordered set. We call a subset $S \subseteq X$... ... a chain if each two elements in $S$ are comparable with respect to $\le$ (in other words, $S$ is linearly ordered ...
Let $P$ be a finite connected poset. The Cartan matrix $C_P$ of $P$ is defined as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else for $i,j \in P$. The Coxeter matrix of $P$ is ...