Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
29 views

Embedding of Coxeter groups into product of trees - Relationship between partial orders

Let $(W,S)$ be a Coxeter system. A result by Ranishnikov and Januszkiewicz (see Every Coxeter group acts amenably on a compact space for the construction) states that $W$ can be isometrically embedded ...
5
votes
0answers
99 views

A monotone countably cofinal function from $\omega^\omega$ to $\omega^{\omega_1}$

For a set $X$ we endow the set $\omega^X$ of all functions from $X$ to $\omega$ with the natural partial order $\le$ defined by $f\le g$ iff $f(x)\le g(x)$ for all $x\in X$. A function $f:\omega^\...
1
vote
0answers
26 views

Posets which extend centered sets to filters

(Post cross-posted from math.se.) Suppose $(\mathcal O, \leq)$ is an arbitrary poset. Let us say that $\mathcal O$ is compact if every $\mathcal C\subseteq\mathcal O$ which is centered (any finite ...
6
votes
2answers
286 views

Class of lattices that excludes $M_3$?

It is well known that a lattice is distributive iff it excludes as a sublattice $N_5$ (the pentagon) and $M_3$ (three unordered elements with a top and bottom). Further, a lattice that only excludes $...
5
votes
1answer
108 views

Preserve unbounded sets between different cofinality

Working in ZFC, let $\kappa,λ$ be cardinals with $\kappa>λ$, and assume that $\kappa$ is regular. We say that a function $F:\kappa^n→λ$, for some finite $n$, is preserving unbound, if for all $a⊆\...
16
votes
1answer
616 views

Has the exponentiation of ordinals a nice geometric model?

It is well known that the sum $\alpha+\beta$ of two ordinals $\alpha,\beta$ can be defined "geometrically" as the order type of the sum $(\{0\}\times \alpha)\cup(\{1\}\times\beta)$ endowed with the ...
0
votes
2answers
110 views

The union of two cuts is a cut?

Every poset $\langle P, \leq \rangle$ has a Dedekind-Macneille Completion, a complete lattice that embeds $\langle P, \leq \rangle$. For $A \subseteq P$, the upset $U(A) = \{p \in P\ |\ \forall a \in ...
5
votes
0answers
44 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 ...
3
votes
2answers
100 views

Explicit lifting characterization of complete lattices among posets?

It's well-known that the complete lattices are characterized among all posets as the regular-injectives. That is, a poset $L$ is a complete lattice if and only if $L$ has the right lifting property ...
2
votes
1answer
74 views

Dubious matrix monotonicity

Coming from a problem in game theory, I arose at some dubious monotonicity like property for matrices of the following art. Let $H=\lbrace h\in\mathbb{R}^{n}\colon h_{1}+\dots+h_{n}=0\rbrace$. I'm ...
1
vote
2answers
71 views

Is this ordering on the set of all covers of $\omega$ a (complete) lattice?

Let ${\frak C} \subseteq {\cal P}({\cal P}(\omega))$ be the collection of all covers of $\omega$ (that is, ${\cal C} \in {\frak C}$ iff $\bigcup {\cal C} = \omega$.) We define the following binary ...
5
votes
1answer
302 views

Calculate the $\downarrow$, $\downarrow\uparrow$ and $\uparrow\downarrow$ cofinalities of the poset of nontrivial finitary partitions of $\omega$

Let $(P,\le)$ be a poset. For a point $x\in P$ let $${\downarrow}x=\{p\in P:p\le x\}\quad\text{and}\quad{\uparrow}x=\{p\in P:x\le p\}$$be the lower and upper sets of the point $x$, and for a subset $...
0
votes
0answers
59 views

Closed set in product topology implies convergence of monotonic sequences

Let $(X,\succsim)$ be a metrizable and connected, totally ordered topological space with the order topology. Let $\succeq$ be another order relation on $X \times X$ such that the two orders are ...
1
vote
1answer
70 views

Thinning directed sets ${\frak P}$ of partitions of $\omega$ with no ${\frak P}$-discrete subsets

This question branches from Taras Banakh's recent question on a cardinal characteristic connected to families of partitions that are directed in the ordering of partition refinement. A partition $\...
4
votes
1answer
220 views

Does the lattice of partitions map onto the lattice of subsets?

Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,...
6
votes
1answer
164 views

Self-embeddings of uncountable total orders, 2

Let $S = (\Omega,\leq)$ be an uncountable dense total order, such that for all positive integers $m$ and all finite ordered sequences $a_1 < a_2 < \ldots < a_m$ and $b_1 < b_2 < \ldots &...
4
votes
0answers
188 views

How can you order a free group?

A left order on a (discrete) group $G$ is a total order on $G$ satisfying $\forall g,h,k \in G: g < h \implies kg < kh$. A right order is defined symmetrically, and a biorder is an order that is ...
1
vote
0answers
74 views

Name for partial orders which are total on connected components

In my context, I encounter a lot of partial orders with the distinguished property that the order is total on connected components. Equivalently, they satisfy the condition $$x \le y,z \enspace \lor \...
10
votes
1answer
164 views

Is there a relation between type (maximum linearization) of a computable WQO and the ordinal strength of a theory needed to prove it?

Background: Given a well partial order $X$ (more commonly studied with antisymmetry dropped as well-quasi-orders, but I'm going to say well partial order to make this definition simpler, obviously ...
8
votes
1answer
992 views

Wikipedia article on forbidden graph substructures

I apologies if this is too trivial a question or if I am over complicating anything here. But I was hoping for some clarification in an article I was reading about forbidden graph substructures on ...
2
votes
3answers
485 views

Consistency of embedding cardinals in linear orderings

Background The fact that there is no suborder of $\mathbb R$ which is of type $\omega_1$ suggests (to me) that the continuum $c$ cannot be very far from $\omega_1$: How could $c$ be far away from $\...
0
votes
0answers
27 views

Linear maps that increase majorization order

Let $x$ a vector in $d$ dimensions with positive entries summing to one (a probability distribution). Is there a characterization of the linear operators $T:R^{d}_{+}\to R^{d}_{+}$ such that: $$ x\...
2
votes
1answer
120 views

Explicit calculation of the width of a product of chains (i.e. maximal rank size)

Given a poset $P$, I am interested in the width (size of the maximal antichain) of $\mathcal{O}(P)$, i.e. the poset of downsets in $P$, ordered by inclusion. As this is rather difficult, I'm starting ...
24
votes
3answers
1k views

When does a graph underlie the Hasse diagram of a poset?

For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
0
votes
0answers
24 views

Majorization for vector valued function: looking for literature

Let $x,y\in R^{d}$. A function $f:R^{d}\to R$ is called Schur convex if $$ x\prec y\;\;\rightarrow\;\;f(x)\leq f(y). $$ I am interested in functions $g:R^{d}\to R^{d}$ such that $$ x\prec y\;\;\...
11
votes
1answer
272 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. ...
0
votes
0answers
23 views

Entrywise matrix functions that preserve matrix majorization order

I am a beginner of majorization theory, reading the Olkin's book. Let $A,B\in R^{d\times k}$. By befinition $A\prec B$ iff there exists $D$ doubly stochastic such that $A=BD$. In this case $B$ is ...
1
vote
1answer
76 views

Are non-trivial interval-isomorphic posets lattices?

We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$. Suppose $(P,\leq)$ is interval-...
6
votes
1answer
194 views

Pairwise non-isomorphic interval-isomorphic lattices

Let us call a lattice $(L,\leq)$ interval-isomorphic if for all $a<b \in L$ we have $L \cong [a,b]$, where $[a,b]=\{x\in L:a\leq x\leq b\}$. Are there $2^{\aleph_0}$ pairwise non-isomorphic ...
1
vote
0answers
44 views

$\sigma$-fields as closure systems

Let $(\Omega,\mathcal A, P)$ be a probability space and let $\Sigma(\mathcal A) \subset 2^{\mathcal A}$ be the collection of all sub-$\sigma$-fields of $\mathcal A$. Then, $\Sigma(\mathcal A)$ is ...
2
votes
1answer
216 views

Generalizing König's Lemma

In some recent work, I need a strengthening of König's Lemma to "trees" of arbitrary ordinal heights. Trees, in this context, are really just well-founded partially ordered sets. See, for instance, ...
1
vote
2answers
167 views

Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube

Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...
6
votes
0answers
136 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$ ...
1
vote
1answer
99 views

Can we order random variables in a measurable way in a general setup?

Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space $(E,\mathcal E)$ be a measurable space $n\in\mathbb N$ $X_1,\ldots,X_n$ be $(E,\mathcal E)$-valued random variables on $(\Omega,\...
1
vote
2answers
97 views

Reference request: lower sets of a preorder form a lattice

Consider a set $S$ with a preorder $\preceq$ (a preorder is a reflexive and transitive relation). A lower set $A$ of $S$ is defined as a subset of $S$ such that for all $x \in S$ and $y \in A$, if $...
0
votes
0answers
46 views

Rewriting a set of integers to get rid of repetition but keeping subset sum ordering

Say, I have a set of 6 +ve integers sorted in ascending order: $A = \{2,4,4,4,5,7\}$ Now to make it easier to deal with (Minimum one starts with 1) I deducted one from all of them: $\therefore B= ...
2
votes
0answers
459 views

Braided lobsters

If $(X,m)$ is a median algebra, then for each $x\in X$, define an operation $\wedge_{x}$ by letting $y\wedge_{x}z=m(x,y,z)$. Then $(X,\wedge_{x})$ is a meet-semilattice with least element $x$. Define ...
1
vote
0answers
78 views

A question about pdfs with likelihood ratio order

Suppose $f_1,f_2,\dots$ are pdfs of absolutely continuous random variables with the same support (say an interval). Assume that $\{f_i\}$ are strictly positive in their support. Furthermore, $\frac{...
1
vote
1answer
127 views

Self-embeddings of uncountable total orders

A nice theorem of Dushnik and Miller (from 1940) states that if $(\Omega,\leq)$ is a countable total order, then either there is an element $\omega \in \Omega$ such that $(\Omega \setminus \{\omega\}...
5
votes
0answers
145 views

Infinitely many initial ideals for non-Artinian monomial orders?

Consider the polynomial ring $R=\mathbb Z[x_1,\ldots,x_n]$ and an ideal $I\subset R$. Let $<$ be a monomial order, i.e. a total order on the set of monomials in $R$ such that for any monomials $a$, ...
2
votes
2answers
176 views

Is the intersection of Boolean sublattices a Boolean sublattice?

Let $L$ be a boolean lattice, $A$ and $B$ sublattices of $L$ that are themselves boolean lattices, and suppose that $I = A \cap B$ is nonempty. Is $I$ a boolean sublattice of $L$? Is it a ...
2
votes
2answers
281 views

(Types of) induction on infinite chains

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So ...
1
vote
1answer
130 views

Countable union of well ordered sets [closed]

Assume I have a sequence $(A_i)_{i<\omega}$ of well-ordered subsets of an ordered set $S$. Assume that $A:=\underset{i<\omega}{\cup}A_i$ is also well-ordered. Let $\alpha$ be an ordinal upper ...
4
votes
1answer
701 views

Is this lemma equivalent to the axiom of choice?

Given any pre-ordering $\preceq$ of an arbitrary set $X$ is the following lemma: $$\text{There exists an inclusion minimal set }S\text{ satisfying }\{a\preceq b:b\in S\}=X\\\iff \text{ Every chain in ...
1
vote
0answers
82 views

Generalization of the linear extension theorem to directed acyclic graphs

Using Zorn's lemma one can prove a generalization of the order extension theorem, that states any acyclic digraph is always contained in another acyclic unilaterally connected digraph on the same ...
0
votes
1answer
41 views

Minimizing the set of “faulty” edges in a map between the vertex sets of $2$ graphs

The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$. ...
1
vote
1answer
122 views

Basis or subbasis for Scott topology

Let $X$ be a partially ordered set. A subset $S\subseteq X$ is called Scott-open if and only if it is: Upward-closed: $x\in S$ and $x\le y$ implies $y\in S$; Inaccessible by directed suprema: if $D\...
2
votes
1answer
60 views

Is the Scott topology generated by the ideals as the closed sets?

Let $X$ be a directed-complete partial order, or even a complete lattice. A subset $S\subseteq X$ is called Scott-closed if and only if it is: Downward-closed: $y\in S$ and $x\le y$ implies $x\in S$; ...
32
votes
11answers
3k views

Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
6
votes
2answers
344 views

Poset dimension and width (Dilworth's theorem)

For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...

1
2 3 4 5
10