# Tagged Questions

37 views

### All tree orders are lattice orders?

Say that a set is tree ordered if the downset $\downarrow a =\{b:b\leq a\}$ is linearly ordered for each $a$. In a comment, Keinstein says that such sets are also semi-lattices, provided they are ...
60 views

### Given a collection of ordered sets, find minimal order-preserving superset

Say I have some collection of ordered sets $C = \{S_i\}$. Is there an efficient way to determine the minimal ordered set $S^*$ such that each of the original $S_i \subseteq S^*$, with order ...
70 views

### Order of cycles in graph

In a school assignment, I am to use contradiction to prove that if a graph is bipartite then all of its cycles have even order. In this context, what does it mean for a cycle to have even order? I ...
336 views

### Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
13 views

### Which properties inherited when combining a set of strict orders

Assume having a set of irreflexive, transitive and total orders $R_1,R_2,…,R_n$. Let $R$ be an ordering resulted from combining them. Regardless of the combination strategy, what is known about the ...
29 views

### Does irreflexivity guarantee acyclicity?

Assume $R$ to be an irreflexive, transitive relation over a set $X$. Let $G=(X,E)$ be its directed graph where $(x,\hat{x})\in E$ if $xR\hat{x}$ is true. I know irreflexivity means $xRx$ cannot ...
36 views

### How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
46 views

### Definition of a linear extension (total order?) of a poset

Hey I have a question about the definition of a linear extension of a poset. If I was given a hasse diagram of a poset with relation <= (S, <=), how can I get the compatible total order of this ...
39 views

### Contractibility of topological spaces associated to posets

Suppose $\mathcal{P}$ is a partially ordered set. To $\mathcal{P}$ we can associate a simplicial complex $K(\mathcal{P})$ whose $n$-simplices are the chains of length $n+1$ in $\mathcal{P}$. Since ...
77 views

### How many possible DAGs are there with $n$ vertices

I am have $n$ vertices and trying to enumerate all possible DAGs $\theta$ over $n$. How many DAGs are there? For example when $n=2$, there are 3 possible DAGs and when $n=3$ I tried the following: ...
59 views

### unranking a sequence of all linear extensions of a partially ordered set

Let $P$ be a partially ordered set. Let $E$ be the set of all possible linear extensions of $P$. Let $S$ be the sequence formed by arranging elements of $E$ in lexicographic or graycode order. Does ...
24 views

### Order embedding and graph embedding of Hasse digraphs

If there is an order embedding from order A to order B, is there a graph embedding between their Hasse digraphs? What if we replace 'embedding' by 'order preserving' and 'homomorphism' etc?
68 views

### Is there a nice characterization of posets induced by trees?

Define that a tree in $X$ is a set of ordinal-indexed sequences with codomain $X$ that is closed under the operations of restricting to an ordinal. (I do not know if this definition is standard.) ...
77 views

### Prove that $\dim(X,\succsim)\leq|X^2|$ - A starting point for a journey into order theory

During the last week I kept on thinking about what looked an easy problem at a first glance. Let $(X,\succsim)$ be a preordered set, and define $\mathcal{L}(\succsim)$ as the set of all complete ...
50 views

### Visualizing directed preorders

I am trying to understand directed preorders, a.k.a. directed sets. Are they analogous to connected DAGs?
613 views

### Topological Sorting in Linear Order for Hasse Diagram

I have come across an exam review question that I am stuck on. The question states: Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram: This is ...
128 views

### Hasse diagram with maximal chain not counted in maximal anti-chain

Construct a post (Hasse diagram) that contains a maximal anti-chain of size $r$ and, after removing a chain $C$ of maximal size, it still contains an anti-chain of size $r$.
106 views

### Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision)

The Robertson-Seymour theorem says that the set of isomorphism classes of finite graphs, with the minor ordering ($G \le H$ if $G$ is a minor of $H$) is a well partial ordering (it is well-founded and ...
51 views

### Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
237 views

### Maximal and maximum (matchings)

Maximal and maximum matchings seem to be with respect to different partial orders, do they? In the set of all matchings in a graph, a maximal matching is with respect to a partial order defined by ...
234 views

### Counting directed acyclic graphs with the same partial ordering

We are given a partially ordered set $P$. Let $L$ denote the set of all linear extensions of $P$ (or equivalently, the set of all topological sortings of the nodes). We want to count the number of ...
77 views

### Conditional merge of a sequence of DAGs / partial orders

I have a sequence of directed acyclic graphs, $G_i$. The union of their edge sets may not be a DAG. I want to find an edge set that is maximal in some sense but still acyclic. Alternatively I have a ...
60 views

### Minimum size of a subset to know a complete total order

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. $<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$ Given that $<$ is transitive, it ...