Combinatorics, geometry, and optimization

01 / Posets and triangulations

When does lifting simplex facets suffice?

On the facets of the Cayley polytope of Stanley’s triangulation

Yushan Qu and Jon Lee

Manuscript · public link to be added

Stanley’s triangulation associates a staircase simplex with each linear extension of a poset. We characterize when lifting these simplices’ facet inequalities yields every facet of their Cayley embedding apart from the bounds on the indicator variables.

Try this: In the first example, deleting element 4 leaves a chain. Compare this with the three-element antichain A₃, where deleting any one element leaves two incomparable elements.

Hasse diagramSelect an element to preview its deletion

The lifting criterion

elements in the original poset

linear extensions, each indexing one simplex

ℓ(P): minimum number of deletions leaving a chain

The criterion and statistics refer to the original poset. Deleting an element previews the induced order on the remaining elements.

The criterion, the facet correspondence, and coefficient bounds

The Cayley embedding D attaches the indicator vectors 0, e₁, …, e_s−1 to the s simplices and takes the convex hull of these lifted copies. Here the e_j are standard unit vectors; the indicators record the choice of simplex.

Theorem 3.6. Every Cayley facet involving the original x-variables is obtained by full optimal big-M lifting of a facet inequality of one of the simplices if and only if deleting at most one element of P leaves a chain. Full optimal big-M lifting uses the support value on each simplex to choose the indicator coefficients. Equivalent conditions are that the linear-extension graph is acyclic and that M(P), the Minkowski sum of all linear-extension simplices, is alcoved. Here “alcoved” means that every facet normal is a positive multiple of ±e_i or e_i − e_j.

Corollary 3.7. The deletion condition is equivalent to excluding four induced subposets: A₃, 2 + 2, N, and K₂,₂. These are the minimal obstructions, and all four appear in the example selector.

Proposition 3.1 and Corollary 3.2. For α ≠ 0, lift the supporting inequalities with normal α using the support value of each simplex. The resulting face F^lift_D(α) satisfies

dim F^lift_D(α) = (s − 1) + dim F_M(P)(α).

Here F_M(P)(α) is the face maximizing α · x over M(P). Thus a facet normal of M(P) determines a facet of D. The supporting inequalities being lifted may expose lower-dimensional faces of every individual simplex.

Coefficient growth. Let H_ℓ(d) be the largest absolute entry of a primitive integer facet normal of M(P), maximized over d-element posets with ℓ(P) = ℓ. “Primitive” means that the entries have greatest common divisor 1. For every fixed ℓ ≥ 1, H_ℓ(d) = Θ_ℓ(d^ℓ−1). If ℓ(P) ≤ 2 and d ≥ 3, every entry has absolute value at most d − 2, and this bound is sharp over that class of posets. For a chain, ℓ(P) = 0 and the largest absolute entry of every primitive facet normal is 1.

Two ways to control coefficient size. The poset project bounds facet-normal coefficients using ℓ(P), the minimum number of deletions leaving a chain. The staircase project instead fixes the number of summands. These are different parameters: fixed ℓ gives polynomial growth in dimension, while three staircase summands already permit exponential growth.

Explore coefficient bounds ↓

02 / Minkowski sums

How large can facet-normal coefficients be?

Facet normals of Minkowski sums of staircase simplices

Yushan Qu and Jon Lee

Manuscript · public link to be added

How do dimension and the number of summands control the size of a facet normal? We establish coefficient bounds and construct normals with large entries. For primitive integer normals, two summands force entries in {−1, 0, 1}; three already allow exponential growth, and four yield coefficients exponentially larger than the three-summand maximum as dimension grows.

Coefficient bounds and large-normal constructions

A normal vector can be scaled without changing its direction. We therefore use primitive integer normals, whose entries have greatest common divisor 1, and measure their size by ∥α∥_∞ = max_i|α_i|. Write h_m(d) for the largest such size among sums of m staircase simplices in dimension d.

Dimension d12

Change the dimension to compare universal upper bounds with the sizes attained by explicit facet normals.

Two summands

h₂(d) = 1

Every primitive facet normal has entries in {−1, 0, 1}. This bound is exact.

Three summands

Pad_d−1 ≤ h₃(d) ≤ B(d − 2)

The Padovan construction supplies the lower bound. The display also uses the exact values h₃(4) = h₃(5) = 2 and h₃(6) = 3.

Four summands

N_d ≤ h₄(d) ≤ ⌊12^(d−1)/4⌋

The Narayana construction supplies the lower bound. For d ≤ 8, the display also uses the general zero-one determinant bound, which can improve the upper bound shown here.

These are selected proved bounds. A lower bound is attained by a construction; an upper bound applies to all normals in the class. They need not coincide, and the displayed lower bounds are not asserted to be the exact maxima.

Can four summands exceed everything possible with three?

Upper bound for every three-summand normal

Size attained by the four-summand construction: N_d

The bars use the same linear scale for the selected dimension.

Inspect a large primitive facet normal

This is a normal vector in dimension d. The geometric introduction below is a separate three-dimensional illustration.

How the upper bounds and constructions work

Upper bounds (Theorem 4.7). The zero-sum characterization produces d − 1 independent indicator vectors perpendicular to α. Cofactor formulas express the primitive normal through determinants. Grouping the zero-sum blocks by summand constrains their supports and yields bounds depending on m. Corollary 4.2 also gives ∥α∥_∞ ≤ δ_d−1, where δ_j is the largest absolute determinant of a j × j zero-one matrix; the display uses its known values for d ≤ 8.

Three summands (Theorem 5.1 and Corollary 5.2). Set Pad₀ = Pad₁ = Pad₂ = 1 and Pad_j = Pad_j−2 + Pad_j−3 for j ≥ 3. Alternating signs give a primitive facet normal with size Pad_d−1. Here B(r) is the maximum product of positive integers whose sum is at most r. Thus Pad_d−1 ≤ h₃(d) ≤ B(d − 2) ≤ 3^(d−2)/3. Proposition 5.6 sharpens the small-dimensional bounds to h₃(4) = h₃(5) = 2 and h₃(6) = 3.

Four summands (Theorem 5.3 and Corollary 5.4). Set N₁ = N₂ = N₃ = 1 and N_j = N_j−1 + N_j−3 for j ≥ 4. The alternating-sign normal has size N_d and is realizable with four summands. For d ≥ 9, N_d > B(d − 2), so its size alone rules out three summands. In small dimensions, Proposition 5.7 gives h₄(4) = 2 and h₄(5) = 3 > h₃(5) = 2. It also shows that this construction needs exactly four summands for every d ≥ 5.

Growth rates. The Padovan construction grows like θ^d, where θ ≈ 1.3247, while the three-summand upper bound has base 3^1/3 ≈ 1.4422. The four-summand construction grows like ψ^d, where ψ ≈ 1.4656 > 3^1/3. Consequently h₄(d)/h₃(d) grows at least exponentially. These bounds do not determine an exact exponential growth rate for h₃(d).

How two edges create a facet

A small example of the underlying geometry. These two tetrahedra illustrate how a sum acquires a new facet-normal direction. Their normal has entries only in {−1, 0, 1}, as every two-summand normal must. The bounds and constructions above address how large coefficients become as dimension and summand count increase.

Try this: Compare the two pairs of tetrahedra. One sum has two facet-normal directions absent from every staircase simplex; the other has none.

One objective α · x for all three figures

facets of the two tetrahedra

facets of their Minkowski sum

facet-normal directions outside the alcoved class

Drag any figure to rotate all three. Thick edges, filled dots, and shaded faces maximize the same objective α · x.

Δ_(1,3,2)first simplex

Δ_(2,3,1)second simplex

Δ + Δ′Minkowski sum

Explore the objective direction α

Azimuth · turn

Turn α around the z-axis: 0° points along +x and 90° along +y.

Elevation · tilt

Tilt α above the xy-plane: 0° lies in the plane, +90° points along +z, and −90° along −z.

Move the sliders to change α continuously and update the highlighted faces. Use the facet selector below to return to an exact facet-normal direction.

Drag a figure: “Rotate view” changes the camera while keeping α fixed. “Change direction α” changes α while keeping the camera fixed. Snapping applies to direction changes made by dragging.

New facet direction

F_Δ+Δ′(α) = F_Δ(α) + F_Δ′(α)

For a polytope K, F_K(α) is the face on which α · x is maximized. The highlighted faces illustrate this identity.

Two zero-sum blocks certify two summands

A zero-sum block is a set of coordinates whose α-entries sum to zero. Select a block to highlight the corresponding exposed edge and its translates in the sum.

A block’s indicator vector has entry 1 on the block and 0 elsewhere. Here the two indicators form a basis of the plane perpendicular to α. These are the only nonempty zero-sum blocks, and they intersect at coordinate 3, so their intersection graph requires two colors. By Theorem 3.1, κ(α) = 2: two staircase simplices are necessary and sufficient to realize α as a facet normal.

Zero-sum characterization, minimum summand counts, and the geometric example

A Minkowski sum consists of all vectors obtained by adding one point from each summand.

Figure 1 and Example 3.2(ii). For σ = (1, 3, 2) and τ = (2, 3, 1), the sum Δ_σ + Δ_τ has 14 facets. Its new directions are ±(1, 1, −1). Each exposes an edge in each summand and a parallelogram facet in their sum.

A staircase simplex is Δ_σ = {0 ≤ x_σ₁ ≤ x_σ₂ ≤ x_σ₃ ≤ 1}. Its four vertices are the suffix-indicator vectors: they have ones on a final segment of σ and zeros elsewhere, including the all-ones and zero vectors. The figures are computed from these vertices and all pairwise vertex sums.

Theorem 3.1: for d ≥ 2, a nonzero vector α in dimension d is a facet normal of a sum of m staircase simplices if and only if there are d − 1 linearly independent zero-sum block indicators whose intersection graph can be colored with at most m colors. Two block vertices are adjacent when the blocks intersect.
Coefficient growth: every primitive facet normal of a sum of two staircase simplices has entries in {−1, 0, 1}. Entries can grow exponentially with dimension already for three summands, and allowing four gives an exponential separation from the three-summand maximum.
Minimum summand counts: κ(α) is the least number of staircase simplices whose sum has facet normal α, with κ(α) = ∞ if no such sum exists. The paper gives exact formulas when α has at most two distinct nonzero entry values.

A facet-normal direction is called “new” here when it is not a positive multiple of ±e_i or e_i − e_j. Such a direction cannot be a facet normal of any individual staircase simplex. The comparison pair is Δ_(1,2,3) and Δ_(1,3,2); every facet normal of its sum is alcoved. Opposite normals count as distinct directions. The exposed-face identity above is standard; the zero-sum characterization is a result of the paper.

All figures use an orthographic projection and the same scale. Objects are centered separately for display. Highlighted faces remain visible through the object; dashed edges are behind its visible surface. The displayed direction vector identifies a ray, so positive multiples select the same face.

Coordinates and keyboard controls. Azimuth is measured from +x toward +y in the fixed xy-plane; elevation is measured above that plane. These axes stay fixed when the view rotates. With snapping enabled, an α-drag within 5° of a facet-normal ray selects its exact integer normal. Focus a diagram and use arrow keys for the currently selected mode. Facet selections use exact normals; angle readouts are rounded.

From facet geometry to optimization formulations. A Cayley embedding records a choice among input polytopes using indicator variables. The next project studies when lifting the input facet inequalities gives the full disjunctive hull, how rounding can supply missing facets, and how the facets of generalized cross-polytope disjunctions can be characterized.

Explore disjunctive optimization ↓

03 / Disjunctive optimization

Which inequalities describe a disjunctive hull?

A disjunctive formulation models a choice among polytopes. These three papers study its convex hull in the original variables together with indicator variables: when optimal big-M lifting suffices, how additional facets arise, and how the geometry of generalized cross polytopes leads to complete descriptions.

General polytopes · lifting and rounding

When does optimal big-M lifting suffice?

On disjunction convex hulls by big-M lifting

Yushan Qu and Jon Lee

Published paper · 2025 ↗Preprint ↗

Discrete Applied Mathematics 371, 31–45

Optimal big-M lifting extends each input facet inequality to the other polytopes using the tightest valid coefficients. The question is whether these inequalities together describe the entire disjunctive hull.

Main results. Lifting the input facet inequalities with optimal big-M coefficients, together with indicator bounds, gives the hull when the continuous dimension is at most two. The paper also establishes higher-dimensional sufficient conditions for polytopes sharing a constraint matrix and proves polynomial-time facet enumeration for fixed continuous dimension. For a family where lifting is insufficient, one round of mixed-integer rounding (MIR) completes the hull.

Explore a three-dimensional counterexample. The two input simplices have a four-dimensional disjunctive hull. Each picture below is a three-dimensional slice at a fixed indicator value z.

Try this: Reveal a point admitted by all optimally lifted input facets. Add a missing facet, then all six MIR cuts.

Indicator slice z 0.50

Strengthen the relaxation

z = 0 selects P₀; z = 1 selects P₁. Fractional values reveal the continuous relaxation. Drag either picture to rotate both views; when a picture has keyboard focus, use the arrow keys.

Optimal big-M relaxation8 lifted input facets

Exact convex hullReference slice · unchanged by the cut buttons

Current relaxationExact hullSelected MIR boundary

Selected MIR inequality

x₁ + x₂ + 9z ≤ 10

At z = 0.50, its boundary is x₁ + x₂ = 5.5.

The example and its complete inequality description

P₀ = {x ∈ ℝ³ : xᵢ ≤ 5, ∑ᵢ xᵢ ≥ 14}, P₁ = {x ∈ ℝ³ : xᵢ ≥ 0, ∑ᵢ xᵢ ≤ 1}, and D = conv((P₀ × {0}) ∪ (P₁ × {1})). The exact slice is (1 − z)P₀ + zP₁.

The eight lifted input facets give 4(1 − z) ≤ xᵢ ≤ 5 − 4z and 14(1 − z) ≤ ∑ᵢ xᵢ ≤ 15 − 14z, with 0 ≤ z ≤ 1. The six additional facets are 9(1 − z) ≤ xᵢ + xⱼ ≤ 10 − 9z for i < j. These follow from MIR; adding all six gives D.

At z = ½, x = (3, 3, 2) satisfies all eight lifted inequalities but violates x₁ + x₂ + 9z ≤ 10: its left-hand side is 10.5. This test point is calculated from the paper’s example.

See the preprint’s Proposition 9 and Remark 10 for this example; Theorems 13–14 for the general reflected-simplex family. The higher-dimensional sufficient conditions require additional hypotheses beyond a shared constraint matrix (Theorem 15). The preprint uses the earlier title On disjunction convex hulls by lifting.

Generalized cross polytopes · facet structure

When do pairwise inequalities suffice?

On disjunction convex hulls for generalized cross polytopes

Yushan Qu and Jon Lee

Read paper · July 2026 ↗

More on Disjunctive Convex Hulls of Generalized Cross Polytopes

Yushan Qu and Jon Lee

Read paper · October 2026 ↗

The July paper gives a complete convex hull description for two generalized cross polytopes. The October paper extends this to arbitrary finite families. Explore an equality-graph criterion for facets and a three-polytope example in which pairwise inequalities are insufficient.

Try this: Start with the three-polytope example. Change one coefficient to break a support tie, then restore the facet normal. Watch the graph disconnect and reconnect.

Equality graph

Every displayed inequality is valid for the disjunctive hull. Its tight vertices span a facet exactly when the equality graph is connected. This view uses positive x-coefficients; coordinate reflections give the other sign choices.

Relative α₁

Relative α₂

Relative α₃

Relative α₄

Move the sliders to change the relative coefficients. The displayed inequality is normalized so that M₀ = 1. Free adjustments can break support ties; select a facet normal to restore them.

Why an additional facet is needed. The point below satisfies every pairwise inequality and all indicator bounds, yet violates a valid inequality of the full hull.

The hull, the equality graph, and the pairwise criterion

The inputs are P_k = {x : ∑_i a^k_i|x_i| ≤ 1}, with positive coefficients. The disjunctive hull is D = conv{(x, e_k) : x ∈ P_k}, where e_k is a standard unit vector in the indicator space for k ≥ 1 and e₀ = 0. The original x-space has dimension d; D has dimension d + m − 1 for m input polytopes.

For α > 0, set M_k = max_i α_i/a^k_i and normalize M₀ = 1. The valid inequality is α · x + ∑_k≥1(1 − M_k)z_k ≤ 1. A graph edge (k, i) marks a tight lifted vertex (e_i/a^k_i, e_k).

The two-polytope mode uses illustrative coefficient rows (1, 2, 4) and (4, 2, 1). The three-polytope mode uses Example 19 of the October paper: (1, 1, 10, 10), (10, ½, ½, 10), and (10, 10, ⅓, ⅓).

July paper, Theorem 13: pairwise inequalities and indicator bounds describe the two-polytope hull. The paper also characterizes when lifting only the input polytopes’ facet inequalities suffices. October paper, Theorems 6 and 16: connectivity characterizes facets; a facet is pairwise exactly when some two active sets intersect and cover all coordinates. Pairwise inequalities suffice for d ≤ 3; the d = 4 example shows the limit.

The facet selector uses the October paper’s feasible-spanning-tree construction. Each selected normal preserves its defining support equalities. Face dimensions are computed from the tight lifted vertices. Displayed decimals are rounded; the computations retain the underlying coefficients.

The fractional test point is x = (0, 3/2, 3/2, 0), z = (3/4, 1/8). It satisfies the indicator bounds and every signed pairwise inequality; their largest normalized left-hand side is 149/160. The non-pairwise inequality x₁ + x₂ + x₃ + x₄ − z₁ − 2z₂ ≤ 1 has left-hand side 2 at this point.

Interactive exhibits accompanying research by Yushan Qu and Jon Lee.

Selected linear extension

Coefficient bounds and large-normal constructions

Two summands

Three summands

Four summands

Can four summands exceed everything possible with three?

Inspect a large primitive facet normal

How two edges create a facet

When does optimal big-M lifting suffice?

When do pairwise inequalities suffice?