Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
2answers
172 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 ...
3
votes
1answer
87 views

A closed subset of a Dedekind-complete order has subspace topology equal to order topology

Here's a fairly easy fact from point-set topology that I'm having trouble finding a reference for. Say $X$ is a total order satisfying the least-upper bound property, and $S$ is a closed subset of it....
2
votes
1answer
124 views

Is the set of "endomorphisms" of a directed set again a directed set?

Let $(I,\leq)$ be a directed set, that is $\leq$ is reflexive and transitive and for every $a,b\in I$ we find $c\in I$ such that $a,b\leq c$. Now consider the set $M$ consisting of all maps $\sigma:I\...
2
votes
0answers
93 views

In a constructive order/lattice theory are the arbitrary join and the weak suprema the same?

For a poset $X$ we define an upperbound $w \in X$ of a subset $S \subseteq X$ to be a weak-supremum if $(\forall a \in S (a \leq b)) \implies w \leq b$. While a supremum is defined more carefully (in ...
6
votes
0answers
146 views

A representation of a partial order by a slowly changing sequence of linear orders

We study visualizations of attractors, which occur in chaotic dynamic systems, and for a few years trying to prove or refute Conjecture [3]. It has an equivalent formulation in terms of order theory, ...
1
vote
1answer
84 views

Density and compactness of Boolean embeddings

Let A and B be Boolean algebras and $h:A\rightarrow B$ a Boolean embedding. If every element of $B$ can be expressed both as a join of meets and as a meet of joins of elements in $h(A)$, then the ...
4
votes
0answers
95 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 $...
1
vote
0answers
131 views

Is there an algorithm to merge $d$ chains into $\left\lceil\frac{d}{k}\right\rceil$ chains?

I've come up with a problem as follow: Given an integer $k > 1$, a queue $Q$ as a permutation of integers $1$ to $N$. You can apply an operation to the queue as follows: split the queue into no ...
1
vote
1answer
50 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 ...
4
votes
0answers
93 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 ...
3
votes
1answer
151 views

Obtaining an antichain from affine subspace

Suppose $a\in \{0,1\}^n$ and $S \subseteq \mathbb{F}_2^n$ is a subspace of dimension $d$. Define an affine subspace $S_a$ as follows: $$S_a=\{a+x \mid x\in S\}.$$ What is the largest possible size of ...
3
votes
0answers
82 views

When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?

This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
8
votes
1answer
623 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 ...
6
votes
1answer
171 views

Maximal independent sets in MAD families

We call ${\cal A}\subseteq {\cal P}(\omega)$ almost disjoint if ${\cal A}\neq \varnothing$, every member of ${\cal A}$ is infinite, and for $A_1\neq A_2\in {\cal A}$ we have that $A_1\cap A_2$ is ...
6
votes
1answer
101 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 ...
9
votes
1answer
263 views

Origin and context of adjunctions inducing equivalences between full subcategories

The following is well-known. Theorem. Let $F\dashv U$ be a pair of adjoint functors $$F\colon \mathcal C\to \mathcal D, \qquad U\colon \mathcal D\to\mathcal C$$ with unit $(\eta_A\colon A\to U(F(A)))_{...
1
vote
0answers
61 views

Monoids with three or more "natural" partial orders

For any given monoid $M$ there may exist lots and lots of compatible pre-orders $\leq$. Only few of these are usually any interesting though. I can find some examples of monoids that have two non-...
1
vote
0answers
71 views

Strongly graded rings

In Theorem 3.1 of Graded rings over arithmetical orders, the authors prove that for a strongly $\mathbb{Z}$-graded ring $R$, if $R_0$ is left and right Goldie and a maximal order in its (classical) ...
3
votes
1answer
108 views

Well-foundedness of divisibility vs well-foundedness of right- and left-divisibility

Say that a preorder (i.e., a reflexive and transitive binary relation) $\preceq$ on a set $X$ is artinian if there is no sequence $(x_n)_{n \ge 1}$ of elements of $X$ with $x_{n+1} \prec x_n$ for ...
4
votes
0answers
109 views

Cofinality without choice: can this coarse definition suffer badly?

This is a rephrased version of a question previously asked at MSE without success. Working in $\mathsf{ZF}$, it is no longer possible in general to give every linear order an ordinal cofinality. For ...
4
votes
0answers
132 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,...
0
votes
0answers
54 views

Is it true that the structure of a commutative ordered semiring is unique on a commutative ordered monoid?

Is it true that the structure of a commutative ordered semiring with identity is unique on a commutative ordered monoid (i.e., the structure of the monoid and the order are consistent)? I am not ...
3
votes
1answer
151 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$ ...
2
votes
0answers
49 views

closure operator on a complete lattice arising from adjunction on lattice itself

Define a closure operator on a complete lattice $L$ as a function $f:L \to L$ which is order preserving and idempotent and satisfies $x \leq fx$. Every closure operator arises from an adjunction ...
0
votes
1answer
40 views

Countable sup property of extended measurable functions

Let $(S,\Sigma,\mu)$ a $\mu$-finite measure space. Denote by $\bar{L}^0(\Sigma)$ the set of extended-real valued $\Sigma$-measurable functions. Does this set have the countable sup property when ...
1
vote
1answer
80 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
1answer
172 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{...
5
votes
1answer
216 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
1answer
243 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
1answer
123 views

Is the Rudin-Keisler ordering a continuous relation?

If $X, Y$ are topological, and $R\subseteq X\times Y$ we say that $R$ is continuous (from $X$ to $Y$) if for every $V\subseteq Y$ with $V$ open, we have $$R^{-1}(V) = \{u\in U: \exists v\in V:(u,v)\...
3
votes
1answer
118 views

Is there an explicit linear extension for the subsequence partial order?

Consider the set of finite sequences (of bounded length $\leq k$, if necessary) whose elements are taken from some finite alphabet $\Sigma$. We define a partial order on this set so that $X = (X_1,...,...
1
vote
1answer
80 views

A diffuse probability distribution in high dimensions with order constraints

Consider the following subset of the unit cube in $\mathbb R^n$: $$ \mathcal D = \{ p = (p_1,p_2,\dots,p_n) \in [0,1]^n:\; p_1 \le p_2 \le \cdots \le p_n\}. $$ We would like to construct a probability ...
7
votes
2answers
134 views

Constructing a $0/1$ polytope from an abstract simplicial complex

Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by: $$e_F := \sum_{i\...
0
votes
1answer
81 views

Ordering preserved by an inverse frame homomorphism

Recall that a frame homomorphism $h:L\to M$ is called ($L$ and $M$ are frames): Dense if, for any $x ∈ L$, $h(x) = 0$ implies $x = 0$. Codense if, for any $x ∈ L$, $h(x) = 1$ implies $x = 1$. ...
16
votes
1answer
644 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 ...
0
votes
0answers
19 views

When is a frame isomorphic to its downset completion?

The downset completion $DX$ of a semi-lattice $X$ is a functor from meet semilattices to frames, with a right adjoint given by the forgetful functor. This adjunction induces a monad on frames (let's ...
8
votes
2answers
184 views

Euler characteristic of the simplicial complex of sets of elements in a semilattice with non-zero meet

In a combinatorial computation, I came across the following quantity: Consider a finite meet semilattice $L$, that is, a finite poset which is closed under $\min$. Denote the least element of $L$ by $...
14
votes
1answer
730 views

Does there exist an ordering-functor?

This sounds like a very silly question which should have have a negative answer but I don't see an argument. The precise question is this: Does there exist a covariant functor $ord$ from the category ...
5
votes
2answers
340 views

Non-homeomorphic connected $T_2$-spaces with isomorphic topology poset

What are examples of non-homeomorphic connected $T_2$-spaces $(X_i,\tau_i)$ for $i=1,2$ such that the posets $(\tau_1, \subseteq)$ and $(\tau_2,\subseteq)$ are order-isomorphic?
5
votes
1answer
249 views

Complete Boolean algebras of subsets of $\mathbb N$

Let $\mathfrak A$ be a subset of $\mathrm{Pow}(\mathbb N)$, the powerset of $\mathbb N$. Assume that $\mathfrak A$ is a complete Boolean algebra in the induced order, i.e., the inclusion order. Does ...
18
votes
3answers
645 views

What is the minimum size of a partial order containing all partial orders of size 5?

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. ...
4
votes
1answer
292 views

How to define a function that has these specific properties?

Suppose $x = (x_1,x_2,\dots,x_K) \in \mathbb{Z}^K_{\geq 0}$. For $x,y \in \mathbb{Z}^K_{\geq 0}$, we write $x \succ y$ or $y \prec x$ if $x \neq y$ and \begin{align*} x_{i(x,y)} > y_{i(x,y)...
11
votes
0answers
213 views

Existence of a strong antichain

Call an antichain (set of pairwise incomparable elements) $A$ of a poset $P$ strong if for every $p,q \in P$ with $p \leq q$ there exists an $a\in A$ which is comparable with both $p$ and $q$. ...
11
votes
0answers
211 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 ...
5
votes
0answers
116 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 ...
4
votes
1answer
137 views

Maximal order of an order-preserving map

Let $X$ be a finite partially ordered set, let $f\colon X\to X$ be an order-preserving map [edit: meaning $x\le y\implies f(x)\le f(y)$], and let $x_0$ be an initial point. Define $x_n = f(x_{n-1})$ ...
23
votes
1answer
912 views

Expected height of a poset?

I am interested in any known results/empirical studies done on the average height of a poset with $N$ elements. Obviously this would depend on how that poset relation was randomly defined, however, at ...
8
votes
1answer
305 views

Generalising the Union-closed sets conjecture from lattice to a larger class of posets

(edit: I decided to simplify the question and only pose it for bounded posets first) The Union-closed sets conjecture is equivalent for lattices P to: There exists a join-irreducible element $a$ with ...
3
votes
0answers
193 views

Poset of antichains of given cardinality

Throughout all posets will be finite. Let $P$ be a poset, and let $\mathcal{A}(P)$ denote the set of antichains of $P$. We give $\mathcal{A}(P)$ a partial order whereby $A \leq A'$ iff for all $x \in ...
14
votes
1answer
306 views

Comparing sizes of sets of integers

Is there a total preorder $\lesssim$ on the power set of $\mathbb Z$ such that: $A<B$ if $A\subset B$ (proper subsets are smaller) $1+A\lesssim 1+B$ iff $A\lesssim B$ (where $1+C = \{1+c:c\in C\})...

1
2 3 4 5
11