1
vote
1answer
26 views

Dilworths Theorem proof doubt

This is the proof I am talking about http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf When you take a maximal chain C in P and then obtain antichains in P\C, if the size of the ...
1
vote
1answer
42 views

Let $L$ and $L'$ be lattices. Prove that $L \times L'$ is also a lattice.

Can someone please verify my proof or offer suggestions for improvement? Some preliminaries: Let $A$ and $B$ be two posets. $A \times B$ is the poset on the cartesian product of $A$ and $B$ such ...
1
vote
0answers
28 views

Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
1
vote
1answer
12 views

Let $P$ be a finite poset. Show that the number of order ideals equals the number of antichains.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there are similar questions posted elsewhere, but I need help with my proof in particular. Some preliminaries: ...
2
votes
0answers
23 views

Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
1
vote
0answers
17 views

Small posets with prescribed number of linear extensions

Given a natural number $n$, I want to construct a (finite) poset $P_n$ such that $P_n$ has exactly $n$ linear extensions. This can always be done, for instance taking $P_n$ to be a chain of length ...
6
votes
2answers
316 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.
2
votes
2answers
122 views

Number of ways to interleave two ordered sequences. [duplicate]

Suppose we have two finite, ordered sequences $x = (x_1,\dots,x_m)$ and $y = (y_1,\dots,y_n)$. How many ways can we create a new sequence of length $m+n$ from $x$ and $y$ so that the order of elements ...
2
votes
2answers
107 views

Collection of independent sets equal to downset?

I have been struggling with the following problem. Every set here is supposed to be finite. If we have a closure $\lambda$ on $X$, we define the collection of independent sets of $X$ as $$ I_\lambda ...
4
votes
4answers
154 views

How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
2
votes
1answer
158 views

Counting certain partitions of integers

[Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting ...
1
vote
1answer
46 views

Counting Self-dual posets

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow ...
0
votes
1answer
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 ...
3
votes
0answers
71 views

Non-isomorphic posets

Is there any formula or counting algorithm for the number of non-isomorphic posets (defined on finite n-element set)? I'm interested how to solve task *5, p.4 in Birkhoff's "Lattice Theory" the book ...
6
votes
1answer
86 views

Enumerating all antichains in a finite poset

I have some reasonably small finite posets (on less than 20 points) and would like to iterate over all "downsets" in the poset, where a downset is a set closed under ≤ (so if x in X, and y ≤ x, then y ...
0
votes
0answers
81 views

Finite ordered sets and their isomorphism

This is a slightly strange question perhaps. How many ways are there to prove that if X and Y are two finite orders (total orders) on n elements, then X and Y are isomorphic? There is a direct proof ...
2
votes
2answers
54 views

Finding the number of $2$-element chains of $B_n$

I'm trying to calculate the number of $2$-element chains and anti-chains of $B_n$, where $B_n$ is the boolean algebra partially ordered set of degree $n$. I understand that I want to take all of the ...
1
vote
1answer
135 views

Width of a product of chains

Write $E_k = (\{0, \ldots, k-1\}, \leq)$ the total order on $k$ elements. If $(A, \leq_A)$ and $(B, \leq_B)$ are two posets, the product poset is $(A \times B, \leq_{A \times B})$ with the order ...
2
votes
1answer
50 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$ ...
5
votes
1answer
175 views

Extending a partial order to antichains

Let $(S, \leq)$ be a partial order. Let $T$ be the set of antichains of $S$ (i.e., subsets of $S$ whose elements are pairwise incomparable). Define a relation $\leq'$ on $T$ as follows: for all $A$, ...
3
votes
3answers
231 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 ...
0
votes
1answer
55 views

About the existence of a partition to a partially ordered set $A$.

Let $A$ be a countable set equipped with a partial order $\prec$. We all know that there are subsets $C\subset A$ with the property that the order $\prec$ in $C$ is total. In other words, any two ...
10
votes
0answers
488 views

How to find a total order with constrained comparisons

There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task? As ...
1
vote
1answer
189 views

Number of linear extensions of a finite partially ordered set

Let $N$ be a finite set and $\le$ be a partial order. Can you express the number of linear extensions $L(\le,N)$ of this partial order in terms of $b(k) := \#\{l \in N\ :\ k \le l\}$? My intuition ...
2
votes
1answer
162 views

Number of possible partial orderings on a finite set

I've been reading about lattices and partial orders (my reference: Applied Abstract Algebra by Lidl, Pilz) while this question struck me. Let X be a finite set. Is there any way to determine the ...
2
votes
4answers
125 views

“Down-Closed”, “Down Ideal”, Something Else?

Let $X$ be an a set and let $\mathcal{C}$ be a collection of subsets of $X$ satisfying the following property: If $A$ and $A^\prime$ are subsets of $X$ with $A \in \mathcal{C}$ and $A^\prime ...
1
vote
2answers
533 views

Prove König's theorem using Dilworth's theorem

I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then ...
18
votes
2answers
724 views

Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?

I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I ...
3
votes
3answers
355 views

Number of strict total orders on $N$ objects

Suppose you are given a set of $N$ objects and a strict total ordering relation $<$ satisfying the standard properties (from wikipedia): transitivity: $a < b$ and $b < c$ implies $a < c$ ...
3
votes
1answer
142 views

Alternating permutations with a specified descent set

say that we have two chains of length n, call them $C_1$ and $C_2$.Let us say that the smallest value in $C_1$ is $a_1$, and the smallest one in $C_2$ is b_1. Further, for each element in these ...
5
votes
1answer
632 views

(Extended) Hall's Marriage Theorem from Dilworth's Theorem

This question comes from Exercises III.4.5 and III.4.6 of Bourbaki's Set Theory. They are about using Dilworth's Theorem to prove Hall's Marriage Theorem (did it) and a mild extension of it (can't do ...
4
votes
2answers
192 views

Counting and Ordering of Numbers

Are there differences between 'counting' and 'ordering'? As such, the whole of rational number is countable, or they order-able too? In what cases counting and ordering are same or not?
5
votes
0answers
106 views

Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

This question was firstly posted on Mathoverflow. Two answers are pretty interesting. The potential counter-example given in the second answer is really interesting, but it is not surely a ...