# Tagged Questions

14 views

### Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
41 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 ...
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 ...
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 ...
13 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: ...
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 ...
18 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 ...
338 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.
133 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 ...
108 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 ...
163 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 ...
159 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 ...
49 views

539 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 ...
733 views

361 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$ ...
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 ...
639 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 ...