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
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 ...
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)\...
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 ...
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 $...
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 ...
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 ...
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 ...
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 ...
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$-...
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....
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 $...
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 ...
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 ...
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 $...
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_{\...
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 ...
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 ...
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. ...
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$, ...
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 ...
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 ...
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 ...
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-...
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 ...
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 $\...
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 ...
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$, ...
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,...
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$ ...
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 $...
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 $...
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 $\...
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}=...
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 ...
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 \...
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 ...
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 ...
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<...
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$...
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 ...
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\...
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{...
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 ...
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 ...
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) ...
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 ...
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 ...
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 ...
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 ${\...
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 ...