Partially Ordered Sets

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

A poset orders some pairs and leaves others incomparable. A chain is a fully-ordered subset; an antichain is a fully-incomparable one. Dilworth's theorem says the fewest chains needed to cover the poset equals the largest antichain: order and disorder are dual.

The divisibility poset

Order {1, …, n} by "a divides b." A chain is a tower of divisors like 1 | 2 | 4 | 12; its length is the number of prime factors counted with multiplicity, plus one. An antichain is a set of pairwise non-dividing numbers.

Dilworth and Mirsky

Dilworth: minimum chain cover = maximum antichain. Mirsky is its mirror: minimum antichain cover = longest chain. These dualities turn structural questions into optimization ones, and they are the order-theory backbone behind matching and scheduling.

Scheme

; Longest chain ending at x in the divisibility poset on 1..n.
; chain(x) = 1 + max over proper divisors d|x of chain(d)
(define (chain-to x)
  (let loop ((d 1) (best 0))
    (if (>= d x)
        (+ 1 best)
        (loop (+ d 1)
              (if (= 0 (modulo x d))
                  (max best (chain-to d))
                  best)))))

(display "longest chain to 12 = ") (display (chain-to 12)) (newline) ; 4: 1|2|4|12
(display "longest chain to 16 = ") (display (chain-to 16)) (newline) ; 5: 1|2|4|8|16
(display "longest chain to 30 = ") (display (chain-to 30)) (newline) ; 4: 1|2|6|30

Neighbors

🧮 Ch.8 Graph Theory — Dilworth is a matching theorem in disguise
🔑 Logic — partial orders underlie lattices and entailment

← Recurrence Relations · 6 of 10 by june.kim Graph Theory · 8 of 10 →