What does the largest antichain of a 'must finish before' order over tasks tell you about that workload?

## Two shapes inside one order Order a set of tasks by `x <= y` meaning "`x` must finish before `y` starts, or is `y` itself". Two kinds of subset then matter: - a **chain** — every two members are comparable, so the whole subset is forced into one sequence; - an **antichain** — every two members are incomparable, so nothing inside it constrains anything else inside it. Note the strength of *every*. A set in which some pairs are unordered is not an antichain; one ordered pair anywhere disqualifies it. From these come two numbers: | Number | Definition | What it bounds | |---|---|---| | **Width** | size of the largest antichain | how many tasks can be unordered at once | | **Height** | number of tasks in the longest chain | how many must run strictly one after another | ## Why the width bounds simultaneity At any instant, call a task *runnable* if every task below it has finished and it has not finished itself. Any two runnable tasks must be incomparable: if `x < y` and `x` has not finished, `y` is not runnable; if `x` has finished, `x` is not runnable. So the runnable set is always an antichain, and no antichain can exceed the width. The ceiling follows from the order alone, with no reference to machines or durations. ## What Dilworth's theorem says, and in which direction **Dilworth's theorem**: in a finite partial order, the size of the largest antichain equals the minimum number of chains needed to cover every element. Both directions are worth reading: - **Easy direction.** Any antichain needs a distinct chain per member, since two members of one antichain can never share a chain. So chains needed `>=` largest antichain. - **Hard direction.** Exactly that many chains always suffice — the bound is achieved, never merely approached. The cover has a direct reading: it is the smallest number of strictly sequential tracks the whole workload can be divided into, where each track is internally ordered and requires no interleaving. Getting the direction wrong is the classic error here. Dilworth is about covering with **chains**; the dual statement — the minimum number of **antichains** needed to cover the order equals the length of the longest chain — is a different theorem, and it is the one that corresponds to level-by-level scheduling. ## What the width does not promise This is where the number gets misused. - **It is a ceiling, not an achievement.** Width 12 says no more than twelve tasks are ever mutually unordered. Whether twelve are ever simultaneously runnable depends on when their predecessors finish, which the order does not record. - **It ignores resources.** With three workers, a width of twelve buys nothing beyond three. - **It ignores duration.** An antichain of ten one-second tasks alongside one hour-long task gives a very different schedule from ten equal tasks, and both have the same width. - **Height is the complementary bound.** Even with unlimited workers, a chain of `h` tasks forces `h` sequential steps. Height bounds the time; width bounds the breadth. Neither substitutes for the other. ## Where the numbers actually help The useful question is not "how fast will this run" but "can restructuring help at all": 1. If height is large relative to the number of tasks, the order is nearly a chain, and adding workers cannot help — the dependencies must be broken instead. 2. If width is large but observed concurrency is small, the structure permits parallelism the runtime is not exploiting, and the problem lies in scheduling or resources. 3. If width is small and matches observed concurrency, the workload is running at its structural ceiling, and only changing the dependencies moves it. That is the value of the two numbers: they separate a dependency problem from a capacity problem before anyone buys more capacity.