We find in the literature three distinct connections between combinatorial

isoperimetric problems and partially ordered sets:

1. The reduction of edge and vertex-isoperimetric problems on graphs (EIP and VIP) to maximum weight ideal (MWI) problems on the compressibility or stability order (see Chapters 3, 4, 5 and 6).

2. J. B. Kruskal's observation, in 1969 [66], that a graph may be looked upon as a two-dimensional complex and then its (incident) EIP has a natural extension to arbitrary complexes (hypergraphs). The extension is called the minimum shadow problem (MSP). Kruskal had already solved the MSP [65] for the simplex in all dimensions, a result discovered independently by G. O. H. Katona [58]. The Kruskal–Katona theorem is probably the most widely known and applied of all combinatorial isoperimetric theorems. Kruskal went on in [66] to conjecture that our solution of the EIP on Qd, the graph of the d-cube (see Chapters 1 and 3), could be extended to the MSP on the complex of faces of the d-cube. He also suggested looking for more such analogs of the Kruskal–Katona theorem.

3. Scheduling problems are standard fare in applied combinatorial optimization. If the steps of a manufacturing process must be carried out in some serial order subject to given precedence constraints, and we wish to order the steps so as to minimize some functional of the ordering, such as the average time between when a step is completed and its last successor is completed, then we have a scheduling problem.