Dilworth's theorem, with both sides computed

The largest antichain in a finite poset equals the fewest chains needed to cover it. Both are computed – the antichain exhaustively, the chain cover by a bipartite matching – and the equality is then CHECKED rather than assumed, since equality is the content.

Usage

morie_dilworth_decomposition(leq)

Arguments

leq

Square logical matrix; leq[i, j] when \(i \le j\).

Value

A list with antichain_size, chain_cover_size, dilworth_holds, antichain, warnings.

References

Dilworth RP (1950) Annals of Mathematics 51(1):161-166.

Examples

divisibility_poset <- function(n) {
    outer(seq_len(n), seq_len(n), function(i, j) j%%i == 0)
}
n <- 6L
morie_dilworth_decomposition(divisibility_poset(n))
#> $antichain_size
#> [1] 3
#> 
#> $chain_cover_size
#> [1] 3
#> 
#> $dilworth_holds
#> [1] TRUE
#> 
#> $antichain
#> [1] 2 3 5
#> 
#> $n
#> [1] 6
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Dilworth's theorem (1950)"
#>