Questions tagged [order-theory]

The tag has no usage guidance.

139 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19 votes
0 answers
765 views

A Linear Order from AP Calculus

In teaching my calculus students about limits and function domination, we ran into the class of functions $$\Theta=\{x^\alpha (\ln{x})^\beta\}_{(\alpha,\beta)\in\mathbb{R}^2}$$ Suppose we say that $...
Dmitry V's user avatar
  • 433
17 votes
0 answers
281 views

A conjecture about inclusion–exclusion

$\newcommand\calF{\mathcal{F}} \def\cupdot {\stackrel{\bullet}{\cup}} \def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
M.Monet's user avatar
  • 271
14 votes
1 answer
581 views

On certain order-automorphisms of the rationals

Consider the rationals $\mathbb{Q}$ with the usual order $\leq$. Now let $A$ be a subset of $\mathbb{Q}$, such that foreseen with the induced order $\leq$, $(A,\leq)$ is a dense linear order. ...
THC's user avatar
  • 4,313
11 votes
0 answers
240 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$. ...
Attila Joó's user avatar
11 votes
0 answers
269 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
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
0 answers
360 views

Can one define in ZFC a directed system of embeddings on the class of all linear orders realizing the surreal line as the direct limit?

Consider the surreal line $\langle\newcommand\No{\text{No}}\No,\leq\rangle$, in its order structure only. This is a proper class linear order, which is universal for all set-sized linear orders, as ...
Joel David Hamkins's user avatar
10 votes
0 answers
397 views

Computing the ordinal of a rational language well-partially-ordered by the subword relation

Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...
Gro-Tsen's user avatar
  • 29.8k
10 votes
1 answer
2k views

Order theory as a foundation of mathematics?

I know the followings kinds of formalization of mathematics: based on set theory (e.g. ZFC) based on type theory (e.g. the formalism of Coq proof assistant, as an advanced example) based on category ...
porton's user avatar
  • 739
9 votes
0 answers
291 views

Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
Wojowu's user avatar
  • 27.3k
9 votes
0 answers
205 views

Reference for sparseness of incomparability graphs implying sparseness of covering graphs

If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...
David Eppstein's user avatar
9 votes
0 answers
307 views

Higher-order dimension in posets: a reference request

Let $P = (X, \le)$ be a partially-ordered set. Then the dimension of $P$ is the minimum number of total orders over $X$ whose intersection yields $P$. Alternately, the dimension of $P$ is the minimum ...
Suresh Venkat's user avatar
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
1 answer
497 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
226 views

Is there a 'local' version of Near Coherence of Filters?

The axiom Near Coherence of Filters (NCF) is known to be independent of ZFC. Axiom (NCF I): For any two free ultrafilters $\mathcal D$ and $\mathcal E$ on $\mathbb N$, there exist finite-to-one ...
Daron's user avatar
  • 1,761
8 votes
0 answers
442 views

Product of Partial Orders

Define the transpose product of a partial order $P$ over a set $S$ in the following way. The direct product of a partial order $P \subseteq S \times S$ and its converse, $P^{op}$, gives a partial ...
Walter Bruce Sinclair's user avatar
8 votes
0 answers
167 views

Can $Ded(\kappa)$ be a supremum?

Definition If there is a dense linear order w/o endpoints of size $\lambda$ with a dense subset of size $\kappa$ then write $D(\kappa,\lambda)$. $Ded(\kappa)=\sup_\lambda \{D(\kappa,\lambda)\}$. It ...
Ioannis Souldatos's user avatar
7 votes
0 answers
138 views

poset of lattice properties

Is there a good overview of the dependencies between properties that a (finite) lattice poset can have? To give a practical example, I was looking for a property weaker than congruence uniform and ...
Martin Rubey's user avatar
  • 5,503
7 votes
0 answers
179 views

On thinking of spacetime as a local Scott domain

An observation of Martin and Panangaden links the study of Lorentzian manifolds and the semantics of programming languages via the theory of Scott domains. Background: Recall that if $M$ is a time-...
Tim Campion's user avatar
  • 60.5k
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
6 votes
0 answers
147 views

Natural bijection between join- and meet-irreducibles in modular lattices?

A well known property of finite modular lattices is that they have the same number of join-irreducible and meet-irreducible elements. I was wondering if there exists a natural bijection between these ...
Igor Makhlin's user avatar
  • 3,493
6 votes
0 answers
187 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, ...
Alex Ravsky's user avatar
  • 4,092
6 votes
0 answers
173 views

Generalized graph-minor theorem?

Consider the following generalized graph-minor theorem: GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ ...
user21820's user avatar
  • 2,734
6 votes
0 answers
115 views

Closedness of the partial order in complete Hausdorff semitopological semilattices

First some definitions. A semilattice is a commutative semigroup consisting of idempotents (i.e., elements such that $xx=x$). A typical example of a semilattice is the unit interval endowed with the ...
Taras Banakh's user avatar
  • 40.7k
6 votes
0 answers
165 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
689 views

What is the structure of a space of $\sigma$-algebras?

Let $X$ be a compact metric space, and consider the Banach space $\Omega = C(X,\mathbb R)$ of continuous, real-valued functions on $X$, equipped with the supremum norm. Let $\delta_x \in \Omega^*$ be ...
Tom LaGatta's user avatar
  • 8,362
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.5k
5 votes
0 answers
122 views

Which monomials are "leadable"?

Question: Let $k$ be a field, let $f \in k[t_1,\ldots,t_N]$ be a nonzero polynomial. Which monomials $m_a = t_1^{a_1} \cdots t_N^{a_n}$ appearing in $f$ are leadable in the sense that they are the ...
Pete L. Clark's user avatar
5 votes
0 answers
195 views

Weak compactness is to trees as [?] is to lattices?

Let $\kappa$ be an inaccessible cardinal. Recall that $\kappa$ is weakly compact if every tree of height $\kappa$ has either a level of size $\kappa$ or a branch of size $\kappa$. So if $\kappa$ is a ...
Tim Campion's user avatar
  • 60.5k
5 votes
0 answers
177 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
100 views

Reference request: a survey of (linear) Krein-Rutman theory

I'm looking for a survey article or book chapter where a rather exhaustive treatment of the Krein-Rutman theory of positive linear operators an ordered Banach spaces is given. Motivation. Some ...
Jochen Glueck's user avatar
5 votes
0 answers
140 views

Self-additive posets

We say that a partially ordered set $(P,<)$ is self-additive if the two natural embeddings of $P$ in $P\oplus P$ (the linear sum of $P$ and itself) are elementary. We have the following. ...
tomasz's user avatar
  • 1,184
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
64 views

Characters on monotone functions

Characters on the semigroup $(C_{+}^{b}(\mathbb{R}^{d}),+)$, i.e. on bounded positive continuous functions with the ususal pointwise addition, are known to be of the form $C_{+}^{b}(\mathbb{R}^{d})\ni ...
Tobsn's user avatar
  • 289
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
141 views

Functoriality of $\mathsf{Cu}$

I have always been happy with the proof of the functoriality of the Cuntz semigroup $\mathsf{Cu}$ given in arXiv:0902.3381, where the isomorphism $$\mathsf{Cu}(A)\cong W(A\otimes K)$$ is used, $A$ ...
Phoenix87's user avatar
  • 417
5 votes
0 answers
301 views

When does $\operatorname{Aut}(M)$ preserve a linear order?

I have a general-type question: Let $M$ be a countable structure that is ultrahomogeneous, i.e. every (partial) isomorphism between finitely generated substructures of $M$ extends to an automorphism ...
Ioannis Souldatos's user avatar
5 votes
0 answers
614 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,503
4 votes
0 answers
102 views

Can we extend "every finite lattice is a sublattice of partitions of a finite set" to linear and/or finitary lattices?

Pudlák and Tůma https://link.springer.com/article/10.1007/BF02482893 proved that every finite lattice can be embedded as a sublattice of the partition lattice of a finite set. Can this be generalized ...
Dale's user avatar
  • 429
4 votes
0 answers
169 views

To whom is the classification of atomic, modular finite lattices due?

Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
Sam Hopkins's user avatar
  • 22.5k
4 votes
0 answers
57 views

Are the countable (rayless) trees with wqo labels wqo?

It has been proved by Corominas that the countable trees with vertex-labels coming from a better-quasi-ordered set are better-quasi-ordered. My question is whether this holds if we replace bqo by wqo ...
Agelos's user avatar
  • 1,844
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
122 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 ...
Noah Schweber's user avatar
4 votes
0 answers
109 views

Obtaining linear orderings on the classical Laver tables from large cardinals

If $k:V_{\lambda}\rightarrow V_{\lambda}$ is an elementary embedding and $R\subseteq V_{\lambda}$, then let $k^{+}(R)=\bigcup_{\alpha<\lambda}k(R\cap V_{\alpha})$. Recall that $\mathcal{E}_{\...
Joseph Van Name's user avatar
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
258 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
4 votes
0 answers
149 views

Maximality with respect to having no marriage

Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
Dominic van der Zypen's user avatar
4 votes
0 answers
150 views

Interval topology of the poset of all coverings

Let $(P,\leq)$ be a poset. The interval topology $\tau_i(P)$ on $P$ is generated by $$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$ where $\downarrow x = \{y\in P: y\...
Dominic van der Zypen's user avatar
4 votes
0 answers
95 views

Unique representability of bounded distributive lattices

Priestley Duality assigns to every bounded distributive lattice $L$ a compact totally order-disconnected topological space $P(L)$, also called a Priestley space. A poset $(P,\leq)$ is called (...
Dominic van der Zypen's user avatar
4 votes
0 answers
278 views

What is known about orbifolding ordered groups and sets? Who has been involved? Links to Lee metrics?

In mathematical music theory several ordered groups are considered. Some examples contain the frequency space or Tonnetzes. Other groups (commutative and non-commutative ones) are discussed by Dawid ...
Tobias Schlemmer's user avatar