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
3 votes
0 answers
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 ...
user avatar
17 votes
3 answers
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$ ...
user avatar
  • 18.8k
0 votes
1 answer
86 views

Partial orders on downward closed sets [closed]

Let $P = (V, \sqsubseteq)$ be a partial order and $\mathfrak{D}(P)$ denote the class of downward-closed subsets of the partial order $P$ (i.e, the class of $A \subseteq V$ such that $y\in A \;\&\; ...
user avatar
  • 617
6 votes
1 answer
144 views

Writing upper triangular 0-1 matrices as a product of a permutation matrix and an upper triangular matrix

Let $C$ be an upper triangular matrix with entries 0 or 1 such that every diagonal entry is equal to one. Let $M_C:=-C^{-1}C^T$. Question: Is there a nice direct criterion (or even classification) on ...
user avatar
  • 21.8k
3 votes
1 answer
84 views

Quiver algebras from semirings and posets as semirings

A semiring is a nonempty set $S$ such two binary operations + and * making S into a semigroup with + and * and such that a*(b+c)=ab+ac and (b+c)a=ba+c*a for all a,b,c in S. Assume in the following ...
user avatar
  • 21.8k
7 votes
0 answers
216 views

Interesting uniform posets

A sequence $(P_0,P_1,\ldots)$ of finite posets is called uniform if: each $P_n$ is graded of rank $n$ with a minimum $\hat{0}_n$ and a maximum $\hat{1}_n$; for any $p \in P_n$ with $\mathrm{rank}(p)=n-...
user avatar
  • 18.8k
4 votes
0 answers
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 ...
user avatar
  • 21.8k
6 votes
1 answer
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,...
user avatar
  • 21.8k
1 vote
0 answers
79 views

Connected posets $P\not \cong Q$ such that $\text{Hom}(P,P) \cong \text{Hom}(Q,Q)$

Given posets $A, B$, we denote by $\text{Hom}(A,B)$ the collection of order-preserving functions $f:A\to B$. We put a partial order $\leq_{\text{Hom}(A,B)}$ on $\text{Hom}(A,B)$ by setting $$f \leq_{\...
user avatar
1 vote
2 answers
157 views

Is the poset $\mathrm{Idl}_{\neq \emptyset, P}(P)$ of nonempty, proper ideals in a finite connected poset $P$ (empty or) weakly contractible?

$\DeclareMathOperator\Idl{Idl}$Let $P$ be a finite, connected poset with at least two elements, and let $\Idl_{\neq \emptyset, P}(P)$ be the set of downward closed sets $S \subset P$ such that $S \neq ...
user avatar
  • 49.2k
6 votes
2 answers
388 views

An equality for the reduced homology related to the comparability graph of a poset

$\DeclareMathOperator\width{width}$Let $P$ be a finite poset with $n$ elements (we can assume that $P$ is connected and has width at most $n-2$). The comparability graph $G_P=(V,E)$ associated to $P$ ...
user avatar
  • 21.8k
3 votes
2 answers
114 views

Is $(\omega+1)^\omega/{\cal U}$ complete for ${\cal U}$ free ultrafilter?

Let ${\cal U}$ be a free ultrafilter on $\omega$. Is the linearly ordered set $(\omega+1)^\omega/{\cal U}$ complete?
user avatar
4 votes
1 answer
158 views

(Higher) posets with non-binary comparisons: name? Axioms? (Looking for reference.)

I am looking for a name of a certain structure, which is a generalization of poset that admits non-binary comparisons. Let $P$ be a set equipped with operations, for $n\geq2$, $$ C_n: P^n \to \{True, ...
user avatar
0 votes
0 answers
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$?
user avatar
9 votes
1 answer
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 ...
user avatar
  • 21.8k
0 votes
1 answer
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\}$ ...
user avatar
3 votes
1 answer
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 1,064
6 votes
0 answers
146 views

Eigenvalues of symmetric matrices associated to posets

For a finite connected poset $P$ define the Cartan matrix $C$ as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in P$. Define the Frobenius-Cartan matrix of $P$ as $...
user avatar
  • 21.8k
10 votes
1 answer
373 views

A definition in poset theory

I am working on a article in poset theory. In that article, I am defining a subposet of a poset. The definition is following: Let $P$ be a finite poset. A subposet $P'$ of $P$ is called closed under ...
user avatar
  • 103
2 votes
1 answer
87 views

What property of ranked poset ensures that it is determined by its vertex-facet incidences?

For a convex polytope, its face poset is combinatorially determined by vertex-facet incidences. Now suppose we have an arbitrary finite poset that is ranked, so I can still speak of vertices and ...
user avatar
2 votes
0 answers
52 views

Common basis property

Let F be a field and let $U_1, \ldots, U_k$ be subspaces of $F^n$. Say that $U_1, \ldots, U_k$ has a common basis if there is a basis $b_1,\ldots,b_n$ of $F^n$ such that each $U_i$ is a span of some ...
user avatar
  • 833
4 votes
0 answers
100 views

Chains of length $2^\kappa$ in ${\cal P}(\kappa)$ [duplicate]

It is a fact that continues to boggle my mind: There is a set ${\cal C}\subseteq {\cal P}(\omega)$ such that $|{\cal C}|=\frak{c}=2^{\aleph_0}$ and for all $A,B\in{\cal C}$ we have $A\subseteq B$ or $...
user avatar
1 vote
1 answer
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 ...
user avatar
2 votes
1 answer
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$ ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1,119
4 votes
0 answers
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{...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 3,345
2 votes
1 answer
156 views

Seeking combinatorial interpretation of a quantity that comes up from central hyperplane arrangements

Let $\mathcal A$ be a central hyperplane arrangement in $\mathbb R^d$ and let's assume that it is essential, meaning the hyperplanes in $\mathcal A$ intersect in the origin. The intersection lattice $...
user avatar
3 votes
0 answers
103 views

"Slim" directed polytopes: any established name for them?

This is a "looking for context" question. Let's say that a polytope is directed if its 1-skeleton is an oriented graph with no cycles, one source, one sink. (Edit: let us additionally assume ...
user avatar
3 votes
0 answers
116 views

Partial orders on $\mathbb{N}^m$ compatible with addition

I'm looking for a classification (or just non-trivial examples) of partial orders on monoid $\mathbb{N}^{m}$ that are compatible with addition. That is, partial orders $\leq$ satisfying two additional ...
user avatar
0 votes
1 answer
387 views

Are there overwhelmingly more finite posets than finite groups? [closed]

A function $f:\mathbb{Z}_{\geq 1}\to\mathbb{Z}_{\geq 1}$ overwhelms $g:\mathbb{Z}_{\geq 1}\to\mathbb{Z}_{\geq 1}$ if for any $k\in \mathbb{Z}_{\geq 1}$ the inequality $f(n)\leq g(n+k)$ holds only for ...
user avatar
  • 25
1 vote
0 answers
111 views

Free monoids on posets

I've suddenly found myself working with some free monoids $F(S)$ in which the set $S$ is a poset, and the order extends to an order $F(S)$, satisfying if (but not only if) $s_1, s_2, \ldots, s_r, t_1, ...
user avatar
  • 12.2k
27 votes
1 answer
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 ...
user avatar
4 votes
0 answers
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 ...
user avatar
  • 229
2 votes
1 answer
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 ...
user avatar
8 votes
1 answer
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 ...
user avatar
6 votes
1 answer
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?
user avatar
6 votes
1 answer
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 ...
user avatar
3 votes
0 answers
150 views

Does every finite lattice embed into a finite Eulerian lattice?

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,...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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{...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $\| ...
user avatar
  • 21.8k
16 votes
1 answer
769 views

Suprema of directed sets

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 ...
user avatar
3 votes
0 answers
53 views

Is the outer automorphism group of a finite poset finite when the Coxeter matrix has finite order?

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 ...
user avatar
  • 21.8k

1
2 3 4 5
7