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

106 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
23 votes
0 answers
482 views

Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. Is ...
Wade Hann-Caruthers's user avatar
14 votes
0 answers
326 views

Poset defined on pairs of subgroups

Let $G$ be a group. Consider the set $P(G)$ of all pairs $(H,N)$ of subgroups of $G$ such that $N$ is a normal subgroup of $H$. Consider the relation $\leq_G$ on $P(G)$ defined as follows: $(H,N)\...
Veronica Phan's user avatar
11 votes
0 answers
272 views

Does every finite poset have a rigid endomorphism?

Crossposted on Mathematics. In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
Pierre-Yves Gaillard's user avatar
11 votes
0 answers
244 views

Poset of nonvanishing minors of a matrix

This question was posed on MSE here three days ago, but hasn't gotten any answers or suggestions. I hope it's okay to ask it on MO, but if I should wait a little longer, please just let me know. Say $...
Zach Teitler's user avatar
  • 6,197
11 votes
0 answers
185 views

A family of posets

Consider the family of all (finite) posets that can be obtained by repeatedly applying one of the following three operations (starting e.g. with the empty poset): (O1) Disjoint union of one or more ...
Stephan Wagner's user avatar
10 votes
0 answers
256 views

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$?

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$ as it relates to $n$? Obviously $2\le m\le 2^n$ and ...
Sourav Ghosh's user avatar
10 votes
1 answer
300 views

Writing matrices deduced from 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 ...
Mare's user avatar
  • 25.8k
10 votes
0 answers
180 views

Ideals in strong Bruhat order

Recall that a (lower) ideal in a poset $(P, \le)$ is a subset $I\subset P$ such that $x\in I \Rightarrow y\in I$ for all $y\le x$. In am interested in ideals in finite Coxeter groups $W$ equipped ...
Misha's user avatar
  • 31k
10 votes
0 answers
345 views

Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it. A permutation on a $n$-...
Sam Hopkins's user avatar
  • 22.7k
10 votes
0 answers
270 views

Strength of claims about extensions of partial preorders and orders to linear ones

Consider these two axioms: Every partial order extends to a linear order. Every partial preorder (reflexive and transitive relation) extends to a linear preorder while preserving strict orderings: i....
Alexander Pruss's user avatar
9 votes
0 answers
343 views

Factorisation of a polynomial from the Boolean algebra

Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$. Let $M_n:=C_n+C_n^T$ and $...
Mare's user avatar
  • 25.8k
9 votes
0 answers
242 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 ...
Monroe Eskew's user avatar
  • 18.1k
9 votes
0 answers
314 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 ...
Sam Hopkins's user avatar
  • 22.7k
9 votes
1 answer
423 views

Structure of $Hom(L_1,L_2)$, where $L_i$ are distributive lattices

Is there known structures/ or has there been studies on $Hom(L_1,L_2)$ of distributive lattices? Could it be made into a lattice naturally? Is there any structure on the set of ring valued functions $...
mukhujje's user avatar
  • 281
8 votes
0 answers
149 views

Partial order on graphs induced by homomorphism counts

For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
David Roberson's user avatar
8 votes
1 answer
499 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 ...
მამუკა ჯიბლაძე's user avatar
8 votes
0 answers
154 views

Periods of Coxeter transformation associated to root posets

$\DeclareMathOperator\Co{Co}$Let $P$ be the root poset associated to a simple Lie algebra. Let $L=L(P)$ denote the distributive lattice of order ideals of $P$ and let $\Co_L$ denote the Coxeter matrix ...
Mare's user avatar
  • 25.8k
8 votes
0 answers
194 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. ...
Richard Stanley'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
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
8 votes
0 answers
270 views

Fixed points and universal maps for posets

In a recent post about f.p.p. for poset products, @M.Mirabi brought back an old-standing problem about the fixed point property of the product of two arbitrary posets which already enjoy the fixed ...
Włodzimierz Holsztyński's user avatar
8 votes
0 answers
614 views

The name for a partial order

In a recent paper of mine, my co-authors found that a partial order that we were using was contained in a paper by Kundgen. In it, he called it "right-shifted partial order". I was curious, and found ...
Victor Miller's user avatar
7 votes
0 answers
245 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-...
Sam Hopkins's user avatar
  • 22.7k
7 votes
0 answers
182 views

Classification of posets that are quotient posets of the Boolean lattice

Quotient posets of the Boolean lattice $B_n$ have interesting properties and are for example discussed in chapter 5 of Stanley's book on algebraic combinatorics. $B_n/G$ for a subgroup $G$ of the ...
Mare's user avatar
  • 25.8k
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
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
7 votes
0 answers
115 views

Dimension of a union of downsets

We have established the following result regarding the Dushnik–Miller dimension of posets. Let $P$ be a poset with downsets $C, D \subseteq P$. If the dimensions of $C$ and $D$ are $m$ and $n$, ...
Michael Engen's user avatar
7 votes
0 answers
165 views

Matroid Representation of the Antichains of a Poset

Introduction I am studying a problem in which the antichains of a poset are of key importance. They are naturally geometrically embedded as vectors in the space $\mathbb{R}^P$, where $P$ is the poset,...
Tom Alberts's user avatar
7 votes
0 answers
250 views

"Double convolution" with the Mobius function on a poset

Let $f$ and $g$ be arbitrary (say integer-valued) functions on some poset $P$, and say $\mu$ is the Mobius function of $P$. I'm studying a quantity that's a sort of "double convolution" of $f$ and $g$ ...
Nicolas Ford's user avatar
  • 1,520
6 votes
0 answers
165 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 $...
Mare's user avatar
  • 25.8k
6 votes
0 answers
110 views

Probability of a maximal chain in a random subposet of a finite poset

Let $P$ be a finite poset, and let $0<p<1$. Choose a random subposet $Q$ of $P$ by letting each $t\in P$ belong to $Q$ with probability $p$. What is the best way to compute the probability that $...
Richard Stanley's user avatar
6 votes
0 answers
166 views

Katetov ordering on ideals on $\omega$

Recall that a nonempty set ${\cal I}\subseteq {\cal P}(\omega)$ is a (set) ideal if $B\in{\cal I}$ and $A\subseteq B$ imply $A\in{\cal I}$, and $A,B \in {\cal I}$ implies $A\cup B\in {\cal I}$. By $\...
Dominic van der Zypen's user avatar
6 votes
0 answers
203 views

When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where $f_{-1}=...
Patricia Hersh's user avatar
5 votes
0 answers
204 views

Sperner property of a distributive lattice associated to a divisor poset and the free distributive lattice

Let $P_n$ denote the poset with elements $P_n=\{1,...,n\}$ ordered by divisibility and let $L_n$ denote the distributive lattice of order ideals of $P_n$, whose elements should correspond to primitive ...
Mare's user avatar
  • 25.8k
5 votes
0 answers
187 views

Is this "trimming" of a supersolvable semimodular lattice known?

Let $L$ be a finite (upper) semimodular lattice. Recall that this means $L$ is graded and its rank function $\rho\colon L \to \mathbb{N}$ satisfies $$ \rho(x) + \rho(y) \geq \rho(x\vee y)+\rho(x \...
Sam Hopkins's user avatar
  • 22.7k
5 votes
0 answers
178 views

Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph

This question is very important for my research, which is why I ask it here. I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
mathlyfe'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
5 votes
0 answers
134 views

Face structures of chain polytopes

For a finite poset $P$ the chain polytope $\mathscr C(P)\subset\mathbb{R}^P$ consists of such $g$ that $g(p)\ge 0$ for all $p\in P$ and $$g(p_1)+\ldots+g(p_n)\le 1$$ for any chain $p_1<\ldots<...
Igor Makhlin's user avatar
  • 3,493
5 votes
0 answers
615 views

A poset with small "cycles"

(A followup to this recent question.) I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that…): Suppose that $z$ is covered by $x$...
Martin Rubey's user avatar
  • 5,533
4 votes
0 answers
165 views

Largest rank-selected Möbius function of a product of chains

Inspired by this question and the answer by Sam Hopkins, given a finite product $P$ of chains, which rank-selection gives the largest absolute value of the Möbius function? Equivalently, given a ...
Richard Stanley's user avatar
4 votes
0 answers
142 views

Rowmotion of matroids

If $Z$ is a finite poset, then we say that a collection $\mathcal{A}$ is an antichain if whenever $y,z\in\mathcal{A}$, if $y\leq z$, then $y=z$. If $R\subseteq Z$, then let $L(R)$ be the set of all $x\...
Joseph Van Name's user avatar
4 votes
0 answers
300 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{...
Dominic van der Zypen's user avatar
4 votes
0 answers
110 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 ...
tsm's user avatar
  • 229
4 votes
0 answers
158 views

Finite pre-orders embeddable in the Rudin-Keisler ordering

$\DeclareMathOperator{\NPU}{\operatorname{NPU}}\DeclareMathOperator{\RK}{\,\mathrm{RK}}$A pre-ordered set is a pair $(P, \leq)$ where $P$ is a set and $\leq\subseteq P\times P$ is a reflexive and ...
Dominic van der Zypen's user avatar
4 votes
0 answers
55 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) ...
Mare's user avatar
  • 25.8k
4 votes
0 answers
77 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 ...
Andrea Marino'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
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
4 votes
0 answers
408 views

Can infinite bounded distibutive lattices be "arbitrarily wide"?

I was always thinking, in an informal way, that the powerset lattices ${\cal P}(X)$ (where $X$ is an infinite set) are the "widest" bounded distributive lattices with respect to their height. (In ${\...
Dominic van der Zypen's user avatar
4 votes
0 answers
259 views

Whitney-like embedding theorem for posets?

The Whitney embedding theorem says that any finite-dimensional smooth manifold can be embedded into $\mathbb{R}^n$ for some $n$. Is anything like this true for posets? I'm looking for conditions on a ...
David Spivak's user avatar
  • 8,549