Shoes after socks, shirt whenever

Getting dressed has dependencies: socks before shoes; trousers before belt. Shirt and socks have no required order. Define $x<y$ when task $x$ must finish before task $y$. A chain is a set in which every pair compares; it is forced sequential work. An antichain is a set in which no pair compares; it is eligible to run together.

Do not confuse “no direct edge” with incomparable. If $a\to b\to c$, then $a<c$ even without an edge $a\to c$. Scheduling follows reachability, not adjacency—the edit shadow from Chapter 10 again.

The chain is an unavoidable bill

If the longest chain has $h$ tasks, every schedule needs at least $h$ rounds: two comparable tasks cannot share a round. This is the critical path lower bound from the dependency chapter.

The striking part is the converse. Assign each task a level

$$level(x)=1+\max_{y<x} level(y),$$

with minimal tasks at level 1. Tasks on the same level cannot compare: if $x<z$, then $level(z)>level(x)$. Each level is therefore an antichain. The maximum level is exactly the longest chain length $h$, so these levels partition the work into $h$ parallel rounds.

This is Mirsky's theorem. It gives a certificate on both sides: the chain proves no schedule can use fewer rounds; the antichain layering proves one can attain that count with unlimited workers and unit-time tasks.

Unlimited workers are a theorem assumption

Real tasks have durations, machines have capacities, and two mathematically independent jobs may contend for memory bandwidth or a database lock. The theorem answers a clean structural question: the fewest dependency layers for unit tasks with unlimited processors.

With $p$ workers, total work $W$ supplies another lower bound $W/p$. The completion time cannot beat

$$\max(critical\ path, W/p).$$

Scheduling heuristics decide how close a constrained system gets. The partial order still tells them which choices are legal.

Width answers a different scheduling question

The size of the largest antichain is the width of the order: the greatest instantaneous structural parallelism. Dilworth's theorem says that width equals the minimum number of chains needed to cover all tasks. Mirsky says height equals the minimum number of antichains.

Keep the pair straight:

Where the schedule runs out

• An antichain is defined by transitive reachability, not missing direct edges.
• The optimal-layer theorem assumes unit durations and unlimited processors.
• Side effects and shared resources can impose constraints absent from the declared DAG; that is a modeling defect, not a theorem failure.
• Minimizing rounds does not necessarily minimize cost, energy, or tail latency.

Lessons

• Chains are forced sequence; antichains are dependency-free batches.
• Height is an unavoidable round count and Mirsky layering achieves it.
• Width measures maximum structural concurrency and equals the minimum chain cover size.
• Parallel legality and realized speedup are separate claims.

Practice

1. Layer the divisibility order on {1,2,3,4,6,12} into antichains.
2. Exhibit a longest chain that proves your layering optimal.
3. Give a resource constraint that is not a precedence relation.
4. One week later, reconstruct the height/antichain and width/chain cross-pairing.

The next question is what machines are made of

Parallel layers decompose a schedule spatially. Finite machines admit a deeper decomposition by behavior. Some components merely forget distinctions; others perform reversible permutations. The next chapter shows that these two species are enough to build every finite machine.

References

1. Mirsky. “A Dual of Dilworth's Decomposition Theorem.” American Mathematical Monthly, 1971. — the height-equals-antichain-cover theorem
2. Dilworth. “A Decomposition Theorem for Partially Ordered Sets.” Annals of Mathematics, 1950. — the width-equals-chain-cover theorem
3. Lehman, Leighton, Meyer. “Mathematics for Computer Science.” MIT OpenCourseWare, 2024. — partial orders and scheduling foundations