Sharp bounds for indecomposable
summands of graphical zonotopes
Caius Folkerts
Abstract. In dimension , every indecomposable generalized permutahedron has at
least edge directions, and its direction graph has maximum degree at least . We
prove these sharp bounds, attain both with one lattice construction on the third
power of a path, and classify the direction graphs attaining the edge bound as the
-trees in which each triangle belongs to at most three maximal cliques. A gluing
theorem expresses indecomposability through positive relations among boundary
responses, giving sharp separator capacities that can grow exponentially even at
fixed clique number. For lattice summands without dilation, Boolean elemental
differences show that the -free graphs supporting full-dimensional indecomposable
summands of dimension at least three are precisely the complete four-partite graphs
with parts of size one or two. Allowing larger cliques, we construct graphical
zonotopes as sums of two indecomposable lattice polytopes in every dimension at
least three.
Indecomposability imposes a sharp minimum on the directions of a generalized
permutahedron. In dimension , at least directions are needed, and the equality cases are
governed by a local condition on the triangles of a -tree. We prove these bounds and
classify their equality cases, using a gluing principle that measures how many
independently deformable pieces a separator can hold together.
The extremal examples also resolve a question about clique size. Poullot [1] proved that
-free graphs allow only segments and triangles as indecomposable summands, and
conjectured that -free graphs allow full-dimensional examples in every dimension at least
three. The path construction below realizes these dimensions on planar graphs with the
fewest possible directions. Its lattice structure then makes it possible to determine exactly
when dilation is necessary.
For a graph on , put
A polytope is a weak Minkowski summand of if for some polytope and . It is
indecomposable if every Minkowski decomposition has summands homothetic to , up to
translation. Modulo translations, the indecomposable weak summands are the extreme
rays of the graphical deformation cone. We write for their largest dimension, with value
zero when is edgeless. The direction graph of a generalized permutahedron has an edge
for each actual edge direction .
1.1. Sharp direction bounds.
Every indecomposable generalized permutahedron of dimension , , has a direction graph
satisfying
Both bounds are sharp, with no restriction on clique number. Equality in the edge
bound forces to be a -tree. The common reason is a positive decomposition indexed by
interacting cliques, which forces the support of an indecomposable summand of dimension
at least three into a triangle-connected family of tetrahedra.
The third power of a path attains the two bounds simultaneously. For , define
Its lower base polytope is a lattice indecomposable summand of , has dimension , and
uses every direction of the planar, -free graph . Its elemental differences count components
in edge-link trees, while their zero equations propagate a single scale along the
path.
The equality cases are governed by one local condition. A -tree supports a
full-dimensional indecomposable weak summand if and only if every triangle lies in at
most three maximal ’s (Theorem 6.1). The necessity comes from the number of
independent branches that a triangle can support; the converse constructs all six
nonconstant triangle responses on rooted branches. This gives a complete classification of
actual direction supports in partial -trees and a linear-time algorithm for their maximum
dimension. Among planar graphs on vertices, a full-dimensional indecomposable weak
summand exists exactly for stacked triangulations.
1.2. Separators and exact capacities.
A separator limits how independently deformable pieces can combine into one extreme
ray. Suppose the graph splits into branches meeting along an induced boundary graph ,
with no edges between their private vertices. The deformation coefficients outside then
fall into independent blocks before the boundary equations are imposed. Put
An extreme ray has at most nonzero private coefficient blocks across this boundary.
Each boundary edge and conditioning pattern imposes at most one equation on the
independent branch scales; the boundary coefficients account for the subtraction of
.
The construction that attains this bound records, for each branch, the conditional
minima of its boundary slacks and the equalities between minimizing rows. When the
private equations leave one scale per branch, the linear span of the minimal face of
the glued deformation is isomorphic to the relation space among its boundary
responses (Theorem 5.4). Extreme rays therefore arise from positive relations whose
space is one-dimensional. This turns the separator bound into a construction
principle.
For a clique boundary of size , the capacity is
Boolean branch functions attain every count up to , and hence, for ,
where is an independent set. We also determine the least number of actual directions
at saturation.
The same principle gives exponential capacities while keeping the clique number equal
to four; the boundary has capacity . For , writing , we obtain
These dimensions can exceed those attainable on spanning admissible -trees. A related
construction gives, for every , an edge-minimal supporting graph of treewidth four with
edges. Thus the equality classification is the first case of a broader separator
theory.
1.3. Lattice summands and dilation.
Within the -free class, dilation becomes necessary in large dimension. If is -free and a
lattice indecomposable summand of the unscaled has dimension at least three, its actual
directions form the edges of
and every such graph occurs, so there are at most eight active coordinates. Here
integrality turns the elemental differences into Boolean functions; their quadratic
interaction graphs then force the supporting tetrahedra to complete to a join of four
parts.
Together with the path construction, this determines the least dilation; among -free
graphs on vertices, the smallest factor admitting a full-dimensional lattice indecomposable
summand is one for and two for .
For general graphical zonotopes, both members of a complementary pair of lattice
summands can be indecomposable in every dimension at least three. Boolean quadratic
phases produce such pairs on with parts. Restricting one part to a singleton preserves
both indecomposabilities and supplies the even dimensions at least six; the smaller
four-partite cases complete the range (Corollary 9.11).
The path formula also has a graphic-matroid interpretation, in which a spanning-tree
determinant explains its elemental differences (Appendix A). The alternative path joins
proposed by Poullot admit an optimal-dilation construction as well, developed in the final
appendix; the path powers have the additional property of minimizing the maximum
direction degree.
2. Deformation cones
For a function with , define its elemental differences by
It is supermodular if and only if all these quantities are nonnegative. For such a
function put
Lemma 2.1.Let be a graph on . Modulo translations, its graphical deformation cone
consists exactly of supermodular set functions with Möbius expansion
supported on cliques of of size at least two. Its complete inequalities are
The association preserves addition and nonnegative scalar multiplication.
Integral coefficients give an integral polytope. If all edge slacks are at most , then
Proof.This is the clique-coordinate description of the graphical deformation cone [2].
We recall its relation to support functions.
For an ordering , write and define . Increasing marginal differences give for every
, with equality for the prefixes , so is nonempty; the coordinate bounds make it
bounded. If a linear functional increases in the order , summation by parts shows
maximizes it. Consequently is the convex hull of the greedy points and is integral
when is integer valued. This support-function calculation also proves .
Swapping adjacent after a prefix changes the greedy point, up to sign, by . Hence
the support function is linear across all braid walls for a nonedge exactly when for
every . This is exactly the condition that its normal fan coarsen the graphical fan. A
positive difference is an actual root edge direction; at a generic point of that braid
wall, the exposed face is the nondegenerate segment between the two greedy points.
In the Möbius expansion, the difference is the sum in (2.3). Vanishing of this
sum for all for a fixed nonedge implies by Möbius inversion that every coefficient
containing the nonedge is zero. Thus only clique coefficients remain, and conversely
clique support makes every nonedge difference vanish. Removing singleton coefficients
amounts to a translation. The remaining support also shows that an edge difference
depends only on the common neighbors of its endpoints.
Any weak summand of has a normal fan coarsening the graphical fan, and
therefore the braid fan; on a chamber where the support function of is linear, the
convex support functions of its two summands must both be linear. To see directly
that such a summand has the required set function, put . A vertex maximizing a
functional increasing in the order simultaneously minimizes every prefix sum, since
is in the closure of that braid chamber. Its coordinates are consequently the greedy
differences above. For the order beginning with , its inequality at gives . Thus is
supermodular, and equality of the greedy support functions gives . Adjacent braid
chambers separated by a nonedge wall lie in one graphical chamber, so their greedy
vertices coincide and the nonedge differences vanish. Hence this is the whole closed
deformation cone.
has edge differences all equal to and nonedge differences all . Thus is
supermodular whenever the slacks of lie in , and the stated Minkowski identity
follows. □
In particular, if and , then and . Every decomposition of therefore stays in this same
positive cone. We write for this cone with all singleton coefficients normalized to
zero.
Lemma 2.2 (Tight equations).The common kernel of the inequalities tight at is
the linear span of the minimal face containing . A nonzero spans an extreme ray if
and only if this kernel is a line. It suffices to find any collection of tight inequalities
whose common kernel is .
Proof.If with , every inequality vanishing at vanishes at both summands, by
nonnegativity. Conversely, a vector in the common kernel permits a sufficiently small
perturbation of in either direction; the tight inequalities remain zero, and the finitely
many other inequalities remain positive. This proves the assertion about the minimal
face. The cone is pointed, since vanishing of every elemental difference leaves only a
modular function, whose normalized coefficients are zero. Its one-dimensional faces
are therefore exactly its extreme rays. □
In the constructions that follow, nonnegative elemental differences produce a summand,
and their zero equations must then leave only its scalar multiples. Positive differences
record which directions actually occur, and an upper bound on the differences specifies a
dilation of containing the summand.
We use and interchangeably for Möbius coefficients, and for elemental differences. A
root direction occurs in precisely when is positive somewhere. The graph of these
directions is denoted by . Its connected components determine the variation space, so a
connected direction graph on vertices gives dimension .
3. An extremal path family
Let . On the vertex set take
Its maximal cliques are the consecutive four-sets. Give each of them coefficient ,
give coefficient to every consecutive triple and to every triple , and set all other
coefficients to zero. The consecutive triples are shared by neighboring four-sets;
their common coefficients will force the local scales to agree. Thus, for and , set
Define
Theorem 3.1.The polytope is integral and Minkowski indecomposable, has
dimension , and is a summand of with complement . Its actual direction graph is ,
a planar -free graph with edges and maximum degree .
3.1. Elemental differences.
The nonzero coefficients are supported on cliques of , and the links of its edges
explain why the elemental differences are nonnegative. For an edge , let be the
graph on its common neighbors, with an edge when is a four-clique. Successive
four-cliques attach leaves to , so it is a tree. The triangles with coefficient zero
are precisely ; they are pairwise edge-disjoint, since for each edge length the
endpoints determine uniquely. Thus at most one vertex of corresponds to such a
triangle. For , let indicate whether that vertex exists and belongs to . Then
The first two terms count components of an induced forest, and the subtraction occurs
only when that forest is nonempty.
For the quantitative bound, put , with when lies outside . The exact edge slacks are
The first expression counts transitions from one to zero along a four-bit word, hence is
at most two; the two terms in the second cannot both be one, so the second and third
expressions are at most one. Together with the vanishing nonedge differences, this proves
supermodularity and gives
Since the coefficients are integers, both polytopes are integral. Also , as used
in (3.3).
3.2. Extremality.
The zero equations first remove all coefficients that were set to zero in the construction.
On each consecutive four-set, the remaining equations identify its nonzero coefficients up
to one scalar. The shared consecutive triples then identify the scalars of neighboring
four-sets. We give the equations explicitly so that this propagation also covers the two
ends of the path.
For a general point of the graphical cone, abbreviate all its clique coordinates as follows
The indices run over the ranges for which all labels are in . These are all the cliques,
since every clique has largest and smallest labels at distance at most three. There are
coordinates.
At the constructed vector, the following cone inequalities vanish
The first family uses the empty conditioning set on every edge. The second uses edge
with subset . The last three equalities use, respectively, edges , , and , with conditioning
sets , , and .
The first two lines force all pair coefficients and all to vanish. The remaining equations
then reduce to
The overlapping consecutive triples propagate one scalar ; every and equals , and
every equals . These account for every coordinate, so the common kernel of the selected
equations is exactly one-dimensional. The edge inequality conditioned on gives ,
identifying its intersection with the cone as the ray of . Lemma 2.2 therefore proves
Minkowski indecomposability.
3.3. Dimension and the graph.
For , choosing gives . For the last adjacent pair, use . Therefore belongs to the
difference space of . These vectors are independent, while (3.3) puts in one affine
hyperplane. Hence .
Every distance-two direction has slack at . For a distance-three pair , take in (??),
giving slack . Thus the actual direction graph is exactly .
Five distinct integer labels have range at least four, so cannot form a clique in . Its
number of edges is , and its maximum degree is . It is planar; start with the tetrahedral
graph on and insert each successive vertex inside the triangular face , joining it to that
face’s vertices. The triangle needed for the next insertion is one of the three new faces.
This completes Theorem 3.1.
4. Sharp bounds on the direction graph
The path-cube construction uses the minimum possible number of edge directions and has
the smallest possible maximum vertex degree among all indecomposable generalized
permutahedra of the same dimension. Both bounds follow from the way its supporting
four-cliques must be joined, without any restriction on the clique number of the ambient
graph.
For a generalized permutahedron , its direction graph has vertex set and an edge
whenever an edge of is parallel to . Throughout this section is full-dimensional in its
affine hyperplane, so . In particular, its direction graph uses all coordinates.
Theorem 4.1.Let , and let be a Minkowski-indecomposable generalized
permutahedron of dimension . Its direction graph satisfies
If , then is a -tree. The family on attains both bounds for every .
The -trees attaining equality are classified in Theorem 6.1.
4.1. A positive decomposition indexed by triangle classes.
By Lemma 2.1, the normalized coefficients of are supported on cliques of its actual
direction graph. Partition its triangles by declaring all triangles in each clique with
and equivalent. For every nonzero higher coefficient, let denote its class. One
may also use the coarser partition generated by all four-cliques of . The same
argument applies to either partition; the refined one will be useful for lattice
summands.
Simply separating these coefficient classes need not preserve supermodularity; a
negative higher coefficient may need positive edge coefficients to compensate for it. The
variables belonging to different classes are disjoint in each elemental difference. Their
minima therefore tell us exactly how much of each edge coefficient to assign to each class,
leaving only nonnegative segment summands.
Lemma 4.2.Every generalized permutahedron whose direction graph is contained
in has, modulo translation, a Minkowski decomposition
where the higher Möbius coefficients of are exactly those of belonging to the class
. Every is a generalized permutahedron with nonnegative elementary differences. If is a singleton triangle class, has dimension at most two.
Proof.Fix an edge . Its common-neighbor variables are partitioned into the disjoint
sets
Every nonconstant monomial in the elemental difference at uses variables from
one . Indeed, a coefficient with puts every triangle , , in the same class. Thus
The summands have disjoint variable sets and satisfy . Set
Since the variables are disjoint, their minima add. The complete positivity
condition at is therefore equivalent to
For each class , retain the original coefficient on every clique of size at least three
with , set the other higher coefficients to zero, and give edge the coefficient . The
resulting set function has elementary differences
It is consequently supermodular and defines a generalized permutahedron . The
residual coefficient
is nonnegative. The decomposition follows coefficientwise from Lemma 2.1.
For an isolated triangle with coefficient , the three edge coefficients in its piece
are all . This piece is, modulo translation, when and when . It has dimension at
most two. □
Lemma 4.3.If is Minkowski-indecomposable and , then the graph has a family
of subgraphs, connected through shared triangles, whose union contains all vertices.
Proof.Apply Lemma 4.2 to the actual direction graph. Each nonzero summand must
be a positive homothetic copy of . Since segments and isolated-triangle pieces have
dimension at most two, a nonzero piece comes from a class containing a .
Using the coarser partition, such a class corresponds to a connected component of
the graph of four-cliques joined across common triangles. Every higher coefficient of
the chosen piece belongs to a clique in this component. Its allocated edge coefficient
vanishes on any edge contained in no such clique, because the corresponding is
identically zero. Thus the piece can vary only in coordinates belonging to the union
of the component’s s. Since it is a positive homothetic copy of the full-dimensional ,
that union contains all vertices. □
Corollary 4.4.Let be indecomposable of dimension at least three, and suppose its
actual direction graph is -free. The family
is nonempty, is connected through shared triangles, and satisfies .
Proof.Use the refined partition in Lemma 4.2. A nonzero piece of dimension at
least three must contain a nonzero four-clique coefficient and be homothetic to .
Comparing higher coefficients shows that all nonzero four-clique coefficients belong
to that piece. Its triangles and allocated edge coefficients are supported on their
union. Conversely, each edge in a four-clique with nonzero coefficient has a nonzero
elemental polynomial and hence a positive value somewhere. □
4.2. The minimum number of directions.
Choose a connected family as in Lemma 4.3, and order its s so that every member after
the first shares a triangle with an earlier member. The first contributes six edges on four
vertices. Each later member introduces at most one new vertex; whenever it introduces
one, its three edges to the old shared triangle are new. A member introducing no
vertex can only add further edges. Hence the union, and therefore , has at least
edges.
Suppose equality holds. Since the component’s union covers all vertices and has at
least edges, it equals and every step of the count is an equality. In particular,
a with no new vertex adds no edge. Such steps may safely be ignored; their
edges were already present, so omitting them loses no triangle needed for a later
attachment. Every remaining step adds one vertex and exactly its three edges to an old
triangle. Starting from the initial , these are precisely the defining operations of a
-tree. This proves both the direction-count bound and its necessary equality
condition.
4.3. The minimum maximum degree.
Lemma 4.5.In a graph of maximum degree at most , where , every
triangle-connected family of subgraphs has at most vertices.
Proof.For , all vertices of the initial are already saturated, so no new vertex can
attach along a triangle.
For , upon introducing a fifth vertex the graph induced on the five vertices is
minus a possible edge. The three common vertices have degree four. Only two vertices
remain available to receive another neighbor, so there is no triangle along which a
sixth vertex can attach. If the missing edge is present, all five vertices are saturated.
Consider , and suppose a component has reached five vertices. The first two s
which introduce them have union minus one possible edge. Thus the induced graph
on these five vertices is either or . Intervening s using only these vertices introduce no
third possibility. A sixth vertex is adjacent to a triangle on the first five. We show that
afterward no triangle on these six vertices can have all its vertices of degree at most
four. This excludes a seventh vertex, because its attachment would require precisely
such a triangle. All degrees used below are already lower bounds from the displayed
six-vertex subgraph; neighbors outside it can only strengthen the obstruction.
If the first five vertices induce , the three attachment vertices already have degree
five. The only remaining possible available triangle uses the two other old vertices
and the new vertex. Both old vertices had degree four in , so making this triangle
gives each of them degree five, and gives the new vertex degree five as well. Thus
this triangle cannot receive another neighbor.
Otherwise write the first five vertices as a central triangle and two tips , with
missing. Up to symmetry, the attachment triangle of the sixth vertex is either or .
If it is , those three vertices have degree five. The only possible available triangle
is . Each of its vertices already has three neighbors in , so if is a triangle all three
have degree five.
If the attachment triangle is , then have degree five. Among the remaining vertices,
the required edges form the path . Its internal vertices already have degree four, and
its ends have degree three. Every missing edge except touches an internal vertex,
thereby giving that vertex degree five. Adding only makes a four-cycle, which has no
triangle. Consequently no additional edges can create a triangle all of whose vertices
remain of degree at most four.
These cases include every added edge on the six vertices. Steps through s with no
new vertex therefore cannot allow a seventh vertex to enter. □
By Lemma 4.3, the component must cover all active vertices. The three cases
of Lemma 4.5 therefore give the lower bounds three, four, five, and six for ,
, , and , respectively. Finally, has exactly edges and maximum degree . The
full-dimensional indecomposable family attains both bounds, completing the proof of
Theorem 4.1.
5. Gluing across a boundary
The direction bounds show that four-cliques must be linked through triangles, but do not
yet say which such assemblies support an indecomposable summand. A separator imposes
a further restriction; each branch can be rescaled independently until a tight equation on
the boundary relates it to the others. We first count the available boundary equations,
then describe exactly what information a branch contributes to them. This will
turn the classification and the later constructions into finite-dimensional relation
problems.
5.1. Separator capacity.
Lemma 5.1 (An arbitrary induced separator).Let , let , and put
For an extreme ray of the graphical deformation cone, let be the number of
components of on which some private Möbius coefficient is nonzero. Here a coefficient
is private to a component if its clique meets that component. Then
Proof.Normalize singleton coefficients to zero. Since every clique not contained in
meets only one component of , we can scale the nonzero private coefficient blocks
independently while allowing all boundary coefficients to vary. This gives a space
of variations of dimension . A zero slack on an edge not contained in remains zero
under these variations, because all its coefficients belong to one private block.
Fix a boundary edge and the membership pattern of its common neighbors
inside . Conditional on these bits, the full slack is a boundary constant plus a sum of
functions on disjoint sets of component-private variables. At a zero slack each private
function must attain its conditional minimum, since minimizing that function alone
would otherwise make the slack negative. Thus all zero rows of this fixed boundary
type give the same equation on the proposed variations, namely the varied boundary
constant plus the sum of the scaled conditional minima. There is at most one such
equation for each of the boundary types. The common zero space therefore has
dimension at least .
An extreme ray has a one-dimensional common zero space after translations are
removed. Hence , as required. □
Corollary 5.2 (Every separating set contains a triangle).If a graph on vertices
supports an indecomposable weak summand of dimension , every vertex separator of
contains a triangle. In particular, is -vertex-connected.
Proof.Full dimension implies that every component outside the proposed separator
has a nonzero private coefficient, for otherwise all coordinates in that component are
fixed, after the singleton translations have been removed. Thus in Lemma 5.1 is
the number of components. If the induced boundary graph is triangle-free, it has
only edge cliques and every edge has no common neighbor. Hence , and the lemma
gives . This excludes every triangle-free separating set. Sets of at most two vertices
are triangle-free, proving the connectivity assertion. The same conclusion applies
to the actual direction graph of any indecomposable generalized permutahedron of
dimension . □
Corollary 5.3 (Triangle separators).Across a triangle separator, an extreme ray
has at most three nonzero private coefficient blocks. In particular, a full-dimensional
ray requires at most three components after deleting the triangle.
Proof.For , the boundary dimensions are and . Apply Lemma 5.1. □
5.2. The space of boundary relations.
The separator bound counts equations without specifying the branches. To attain it, we
construct branches whose private equations leave one scalar each, then use the
boundary to determine their ratios. A branch contributes its minimum slack
for each fixed boundary context, since these are the values at which a global
boundary inequality can become tight. Differences between minimizing rows carry
additional private equations; when these and the internal tight rows leave one scalar,
extremality becomes uniqueness of a positive relation among the vectors of conditional
minima.
Let a graph be the union of induced branches , where are distinct components of , and
put . There are no edges between different . Normalize singleton coefficients to zero. Let
be the number of cliques of of size at least two, and index the boundary types by
The boundary slack map
is injective. Indeed, the empty-context differences first determine the pair coefficients.
For a larger clique , a difference on any pair , conditioned on , determines once the
coefficients of its proper subcliques are known. Induction therefore recovers all normalized
boundary coefficients from .
For a branch function , require all its slacks on edges not contained in to be
nonnegative. For each boundary type, let
Its private equations consist of its tight internal slacks and the differences between
any two boundary rows attaining the same conditional minimum. They involve
only coefficients of cliques not contained in . The ambient private space includes
every such graphical clique, including those whose chosen coefficient is zero.
The minimizing rows are fixed at the chosen function ; these are ordinary linear
equations, with no assumption that a minimizer remains optimal under a signed
variation.
Adding an arbitrary boundary function to changes neither its private coefficients nor
its private equations, but replaces by . Thus the response class in is independent of
the chosen boundary lift; the corresponding change in the closing function is
.
Theorem 5.4 (Positive response gluing).Suppose each branch has a nonzero
private coefficient vector and its private kernel is the line spanned by that vector. Let
and suppose a boundary function satisfies
Then
belongs to the graphical deformation cone. Modulo translations, the dimension of
its complete common zero space is exactly
In particular, spans an extreme ray if and only if this relation space is
one-dimensional, in which case it is spanned by the strictly positive vector . The
number of branches is then at most .
Proof.Internal-edge inequalities belong to their own branch and retain its
nonnegativity under positive scaling. Conditional on a boundary type, the
private-variable sets are disjoint. Hence
This proves all inequalities. Because every is positive, a boundary row is tight
exactly when every branch independently attains its conditional minimum. Thus the
boundary minimizer set is the Cartesian product of the individual minimizer sets.
Let lie in the complete common zero space of . Every internal zero equation of a
branch is a global zero equation. To obtain a branch boundary-minimizer difference,
fix minimizing choices in all the other branches and subtract the two resulting global
zero rows. Thus all private equations of every branch survive. By hypothesis the
private part of in branch is times the private part of . Subtracting leaves a function
supported on . The remaining global zero equations are exactly
Conversely, every solution of this equation produces a vector in the complete
common zero space; all internal tight rows vanish, and all boundary tight rows
evaluate to the displayed aggregate expression. The nonzero, disjoint private blocks
determine the scalars uniquely, and injectivity of makes unique when it exists.
The common zero space is therefore isomorphic to the stated quotient-relation space,
proving the dimension formula. Lemma 2.2 identifies this dimension with that of the
minimal face and gives the extremality assertion. Finally, the quotient has dimension
, so a one-dimensional relation space among vectors requires . □
The relevant boundary dimensions in the present constructions are
Each displayed capacity is attained by a positive construction below. The -tree
induction supplies all needed triangle-response states, the four-clique books use Boolean
modules, and the complete four-partite classification uses cube-cell indicators. In each case
the retained equations come from actual conditional minima of nonnegative elemental
slacks.
5.3. Restriction gluing.
When the restrictions themselves are extreme, a nonzero overlap identifies their scales
directly, without computing boundary responses. The following criterion makes this
observation precise; the four-element example afterwards also supplies one of the
complementary unit lattice summands used in Section 9.3.
Proposition 5.5 (Restriction gluing).Let , and suppose cover every clique of size
at least two. Assume that each restriction is nonzero and spans an extreme ray of .
If the graph joining and whenever is nonzero is connected, then spans an extreme
ray of .
Proof.Suppose with . Restriction preserves supermodularity and normalization, so
local extremality gives
If is nonzero on , evaluating the two identities at a subset on which it is nonzero
gives . Connectivity therefore gives one common scalar . Möbius inversion on each
shows that for every clique covered by . The covering hypothesis accounts for every
possible nonzero coefficient; nonclique coefficients and coefficients of size at most one
already vanish. Thus . Applying the same argument to proves the assertion. □
Without fixing normalization, the overlap requirement says that the common restriction
is nonmodular, so it still identifies the local scaling parameters. This criterion addresses
extremality once global supermodularity is known; agreement of extreme local restrictions
alone does not imply the latter.
5.3.1. A four-element block.
On define by the following nonzero Möbius coefficients
In particular . If denotes membership of in the conditioning set, the six pair
differences are
Every entry is nonnegative for zero-one arguments, so is supermodular. In fact every
entry is either zero or one.
To prove extremality, let be any normalized supermodular function that satisfies all
pair-difference equalities satisfied by . Write its pair, triple, and quadruple coefficients as ,
, and . The zero differences for pair at , , and give
The zero differences
give , while
give . Finally,
gives . Consequently every coefficient of is determined by the single parameter , and .
Supermodularity gives . Thus the common zero set cuts out exactly the ray in the
nonnegative supermodular cone.
The restrictions to and have all three pair coefficients equal to and their triple
coefficient equal to . Their base polytopes are
respectively, in the corresponding coordinate subspaces. In particular they are
nonmodular, so either triangle can synchronize the scale with the next four-element
block.
Geometric identification. The base polytope is the thirteen-vertex polytope called the
persimmon in [3, Section 3.3]. Indeed, let , so
The set functions and agree on every subset except , where and . Indeed their
difference is the Boolean function
Therefore
The four-cycle zonotope has fourteen vertices; its acyclic orientations are the
orientations of the cycle except the two directed cycles. The cut removes the unique vertex
at which . Every edge from that vertex is a translate of one of the four unit generating
segments and meets the cutting hyperplane at its other endpoint. Hence the cut creates no
new vertices and leaves thirteen vertices.
6. A complete classification for -trees
A -tree is obtained from by repeatedly adding a vertex whose earlier neighbors form a
triangle, so it is -free and has edges. The triangle-separator bound gives a necessary
condition for such a graph to support a full-dimensional indecomposable summand. It is
also sufficient.
Theorem 6.1.Let be a -tree on vertices. The following are equivalent
(i)
has a Minkowski-indecomposable weak summand of dimension ;
(ii)
every triangle of belongs to at most three maximal ’s;
(iii)
deleting any triangle of leaves at most three connected components.
When these conditions hold, there is an integral coefficient vector on such an extreme ray with
every maximal-clique coefficient equal to . Its polytope uses every direction of and is an
actual summand of . Every triangle coefficient is , , or .
The proof uses the entire conditional boundary response. A branch which is
decomposable when its boundary coordinates are considered in isolation can still be rigid
after its boundary minimizer equations are retained.
6.1. Rooted branches and their boundary equations.
The bipartite incidence graph whose nodes are the maximal ’s and the triangles
of a -tree, with containment as incidence, is a tree. Indeed, the initial gives a
four-leaf star. Each added vertex attaches a new clique node to one existing
triangle node and creates three new triangle leaves. A clique node always has
degree four; the degree of a triangle node is the number of maximal ’s containing
it.
Deleting a triangle node from this incidence tree gives one branch for each incident
maximal clique. The corresponding graph branches meet exactly in , and their
vertices outside form the connected components of . This also follows directly by
induction; every new vertex in one branch attaches to a triangle containing an
earlier vertex outside , and there are no edges between different branches. This
proves the equivalence of (ii) and (iii). Corollary 5.3 proves the necessity of these
conditions.
We prove sufficiency by constructing a branch with a prescribed response. Use the
private coefficients and equations of Section 5.2. Normalize the coefficient of the boundary
triangle to zero, leaving its pair coefficients free. For a boundary edge and its third vertex
, write
The induction retains the minimizer differences for both values of ; this is what allows
the branch scales to be recovered after gluing.
There are six boundary types, two for each edge of . A boundary pair coefficient shifts
both values on its edge equally, so after removing pair coefficients the response is the
vector of three differences . A boundary triangle coefficient shifts all three differences
equally, giving the response quotient . Complementary nonconstant bit vectors for two
branches, or the three unit vectors for three branches, have the unique positive relation
required by the gluing theorem. The induction must produce all six nonconstant bit
vectors, since the state needed by a child depends on the other children at its
parent.
Lemma 6.2 (A module with any prescribed nonconstant response).Suppose a rooted branch has at most two child branches at every triangle. For every
nonconstant vector
there is an integral branch function with the following properties
(i)
every maximal-clique coefficient is and the boundary triangle coefficient is zero;
(ii)
every internal elemental slack is nonnegative;
(iii)
for all six boundary choices;
(iv)
the common kernel of the private equations is precisely the line spanned by the
private coefficient vector of ;
(v)
each internal edge has a positive slack, and each boundary edge has a value
strictly above its conditional minimum for some conditioning set.
Every nonboundary triangle coefficient is , where and ; here is its maximal-clique
multiplicity in the branch.
Proof.We give one induction which also covers a branch consisting of a single
maximal clique. Its first clique is . Label the three vertices of by , put
and let be the number of child branches on . Call occupied when .
The bits chosen next have two purposes. Each occupied face must have a
nonconstant row, so its children can be forced to the core’s scale. On edges shared by
occupied faces, the rows must agree, so that the reduced slack has enough zeros to
expose both boundary states of every child. These requirements explain the following
choices.
First choose a bit for each of the three edges of . Its coordinate on is always . If is
unoccupied, take its entire row to be the constant vector . At an intersection of an
occupied and an unoccupied face, copy the bit of the unoccupied face to the occupied row.
If exactly two faces are occupied and is unoccupied, assign their common edge the bit in
both rows. If all three faces are occupied, assign the intersection the bit , where . Every
occupied row is nonconstant. With one occupied face it is a permutation of ; with two, it
contains both and ; with three, each row is again a permutation of . Moreover,
We now complete each occupied row to a constant vector by adding one or two child
responses. Prescribe a nonconstant response to each child branch as follows. For an
unoccupied face set . For one child set
For two children, a nonconstant three-bit row is either a unit vector or the complement
of a unit vector. If is one unit vector, give the children the other two unit vectors and set .
If is one complementary unit vector, give them the other two complementary unit vectors
and set . Write for the sum of the prescribed child responses, taking when there is no
child. In every case,
Apply the induction hypothesis separately to the child branches.
Sum their complete normalized functions and add the following core terms; coefficient
on , coefficient on , and pair coefficients
The coefficient on remains zero. These are integer coefficients; children contribute no
coefficient on their boundary triangle, so each triangle coefficient is assigned exactly
once.
For positivity, minimize a core-edge slack over all child-private variables. Contributions
from different branches use disjoint variables, so their minima add. On , put and . After
inserting (6.2)–(??), the result is
For this is , for it is , and for unequal bits it is after relabeling. Every case is
nonnegative, has a zero, and has a positive value. Internal edges lying strictly inside a
child branch retain their child’s slacks. This proves internal nonnegativity and the internal
part of (v).
On a boundary edge , after minimizing child variables the slack is
Its minimum over is , as required. It also has a value strictly above that
minimum; use when , and when . This proves (iii) and the remaining part of
(v).
We next prove the one-dimensional kernel assertion. The first point is that all six
conditional minimizer equations of every child are retained. Consider an occupied face .
On an edge , equality (6.1) makes (6.4) either or . Its zero set contains both values of the
third vertex of . Fixing either such value, choose a reduced zero and minimize all
child contributions independently. Any two minimizers of the chosen child then
give two zero rows of the parent; their difference is precisely the child’s private
equation.
For the remaining edge of , set in (6.5). Both values of attain its conditional
minimum. Thus both child boundary types are again exposed, now as differences of parent
boundary minimizers. Child internal zero rows are retained directly. Consequently, any
vector satisfying the parent’s private equations restricts on each child-private block to a
scalar times that child’s vector.
Subtract these scaled normalized child functions from the variation. The remaining
coefficients are supported on the core . Denote its quadruple coefficient by , its negative
triangle coefficient on by , and the child scales on this face by . Define the effective row
On a core edge adjacent to an occupied face, the effective slack of the variation has the
form
If the chosen bits are zero, the values at vanish. If they are one, the zero rows are .
Substitution gives, respectively,
Thus both effective coefficients are times their chosen bits. On , set as above and
subtract the rows for and . Their difference is , so the root coordinate satisfies the same
rule. Therefore, for every occupied face,
For an unoccupied face the boundary equation alone gives .
If there is one child, substitute into (6.6). Because has both a zero and a one, it gives
and . With two unit responses, the coordinate of the third unit gives , and the other
coordinates give both child scales equal to . With two complementary unit responses, the
three coordinates give and again both scales equal to . Thus every child scale is , every
core triangle coefficient is times its chosen coefficient, and each internal core pair
coefficient is fixed by one of its zero rows. Only the boundary pairs remain free, and these
are not private coordinates. Hence the entire private variation equals times the
constructed vector. Conversely that vector satisfies all its private equations, proving
(iv).
When there are no children, the same argument uses the boundary-minimizer ties to fix
the three triangle coefficients and the internal zero rows to fix the three internal pairs;
thus it supplies the base case as well. Finally, a nonboundary face with children
has multiplicity . The displayed choices of give the stated coefficient bounds.
□
6.2. Closing the boundary and proving extremality.
Sufficiency in Theorem 6.1. For , use the simplex coefficient , with all other
coefficients zero. Suppose has at least two maximal cliques. Choose a shared triangle
; its multiplicity is two or three. Removing its node from the incidence tree gives two
or three rooted branches of the type in Lemma 6.2.
For two branches, prescribe a nonconstant response to one and to the other.
For three branches, prescribe the three unit vectors. Sum the resulting normalized
branch functions, add coefficient on each of the three edges of , and add coefficient
on . Every internal-edge slack is nonnegative by the module lemma. On a boundary
edge and for either third-vertex bit , the minimum slack is exactly
since the prescribed responses sum to . This proves all elemental inequalities.
For a triangular boundary, quotienting by boundary pair coefficients leaves
the three differences ; the boundary triangle coefficient changes all three by
the same amount. Thus the response quotient is , and the branch classes are
represented by their prescribed vectors. Two complementary nonconstant vectors
have a one-dimensional relation space in this quotient, as do the three unit vectors.
Theorem 5.4therefore proves extremality.
Every internal graph edge has a positive slack by the module lemma. For an edge of
, keep all but one branch at a conditional minimum and use the strict excess supplied
by part (v) in the remaining branch. This gives a positive global slack on that edge
as well. Thus every edge of occurs as a polytope direction. Since is connected, these
directions span the -dimensional zero-sum subspace. The polytope has dimension ,
and extremality gives Minkowski indecomposability.
All coefficients are integral, all quadruple coefficients are , and every triangle
coefficient lies in by construction. Integral supermodular data have integral greedy
vertices, so the resulting polytope is a lattice polytope up to translation.
For the dilation bound, fix a graph edge . Its link has one vertex for each triangle
containing , and one edge for each maximal containing . It is a tree because the -tree
construction starts its link as one edge and adds only leaves. Write . The constructed
slack is
Every edge has a zero slack, as is explicit in the construction.
At each link vertex , mark any of its incident edges. On a link edge , let indicate
whether it was marked at . The nonconstant part of the slack is the sum, over link
edges, of
Each such function has range of length one on its four binary inputs. The whole
slack therefore has range of length at most . Its minimum is zero, so every elemental
slack lies between and . There are maximal cliques, hence . The elemental slacks
of equal one on every graphical edge and zero on nonedges. Consequently has
nonnegative elemental slacks and is represented by a polytope. Thus is an actual
Minkowski summand of . □
Remark 6.3.The construction traverses the clique–triangle incidence tree and uses
integer arithmetic. The coefficient at a triangle of multiplicity three is what permits
all six response directions to propagate; restricting every triangle coefficient to or
would unnecessarily exclude some of the required boundary states.
Corollary 6.4 (Complete criterion for planar graphs).Let be a simple planar
graph on vertices. Its graphical zonotope has a Minkowski-indecomposable weak
summand of dimension if and only if is a planar -tree, equivalently a stacked
triangulation.
Proof.Suppose such a summand exists and let be its actual direction graph.
Theorem 4.1 and Euler’s planar bound give
Equality in the first bound forces to be a -tree, and equality throughout forces .
Conversely, in a planar -tree no triangle can belong to three distinct maximal
s; its three vertices and the three distinct opposite vertices would contain a
subgraph. Every triangle therefore belongs to at most two maximal s, so Theorem 6.1
supplies the required full-dimensional indecomposable summand. The usual stacked
triangulation description is also immediate; start with an embedded tetrahedron and
attach each new vertex inside its attachment face; the multiplicity bound two ensures
that no face is reused. □
Corollary 6.5 (Maximum dimension and the full spectrum for planar graphs).Let be any simple planar graph. Form the graph whose vertices are the subgraphs
of , joining two when they share a triangle. For each connected component , let be
the union of the vertices in its tetrahedra. Then
If this maximum is , the positive dimensions of Minkowski-indecomposable weak
summands are exactly . Every one of these dimensions is attained by a lattice
polytope.
Proof.Consider the union of a triangle-connected family of s on vertices. Start
from one tetrahedron and traverse a spanning tree of the triangle-adjacency graph.
Each newly encountered vertex brings at least three new edges, so . Since is planar,
Euler’s bound forces equality. The equality argument in Theorem 4.1 shows that
is a -tree; steps adding no vertex add no edge, and every new vertex attaches to
exactly its shared triangle. It is a planar -tree and hence admissible by the preceding
corollary.
The positive triangle-class decomposition (Lemma 4.2) says
that an indecomposable summand is supported either on a segment direction, on
an isolated triangle class, or on one triangle-connected component. Its dimension is
therefore bounded by the corresponding value in the formula. Conversely, each such
component is a planar -tree and has a full-dimensional lattice indecomposable ray,
which embeds in the deformation cone of . A triangle simplex and an edge segment
give the lower-dimensional cases.
Finally, a planar -tree on vertices has construction prefixes on every number
of vertices from four through . These prefixes are again planar -trees, so their
full-dimensional rays attain every dimension from three through . Their triangles and
edges supply dimensions two and one. This proves the no-gap assertion, including
the cases with no . □
6.3. All possible direction supports and the maximum dimension.
A partial -tree is a graph contained in a -tree on the same vertex set; equivalently, it
has treewidth at most three. The usual small-vertex cases are understood separately. This
class includes every chordal -free graph.
Corollary 6.6.Let be a partial -tree. After isolated vertices are deleted, the actual
direction graphs of its Minkowski-indecomposable weak summands of dimension at
least three are exactly the induced subgraphs which are -trees and in which every
triangle belongs to at most three maximal ’s. Such a summand has dimension .
In particular, for a partial -tree has a full-dimensional indecomposable weak
summand if and only if it is itself a -tree satisfying the triangle condition of
Theorem 6.1.
Proof.An indecomposable generalized permutahedron has only one nontrivial
connected component in its actual direction graph; distinct components separate the
coefficient function and give a Minkowski decomposition. Let be that component’s
vertex set. The sharp direction bound, Theorem 4.1, gives at least actual directions
when the dimension is at least three. On the other hand, an induced subgraph of
a partial -tree on vertices has at most edges. Equality is therefore forced. The
actual graph equals , and the equality case in the direction bound makes it a -tree.
Theorem 6.1 supplies its triangle condition.
Conversely, apply that theorem on any such and fix all coordinates outside .
The resulting polytope remains indecomposable, since any Minkowski summands of
a polytope in an affine subspace can be translated into the parallel subspace. It is a
weak summand of , since unused graphical segments can be added to its complement.
Its dimension is . □
For a -tree , call a nonempty collection of its maximal cliques admissible if it is
connected through shared triangles and uses at most three cliques at any triangle. A
connected clique collection is itself a -tree; order its clique nodes outwards from any one
node in the incidence tree. Each subsequent clique meets the earlier union in its
attachment triangle and introduces one new vertex. The running intersection property, or
the original -tree construction, excludes any repeated new vertex. If it contains cliques, its
union has vertices and edges. There cannot be an additional edge of between these
vertices, since that would exceed the partial--tree bound . Thus this union is an induced
-tree.
Corollary 6.7 (Dimension spectrum and a tree algorithm).For a -tree , let be the
largest number of maximal cliques in an admissible collection. Then the maximum
dimension of an indecomposable weak summand of is
Every integer dimension from through occurs. Both and a maximizing support
can be found in linear time on the clique–triangle incidence tree.
Proof.Corollary 4.4 says that the actual directions are the union of a
triangle-connected family of nonzero four-clique coefficients. In a -tree this is a
connected clique collection of the kind just described. By Corollary 6.6, its triangle
multiplicities are at most three. Conversely every admissible collection supports the
full-dimensional ray constructed above. A collection of cliques has dimension ,
proving the formula.
Starting with a maximizing collection and repeatedly removing a leaf clique yields
admissible collections of every size from down to one. They give all dimensions from
three through . A graphical segment and a triangle simplex give dimensions one and
two.
The dynamic program has the following form. For an incidence edge , let be the largest
number of selected cliques in the branch on the side, requiring to be selected.
Let be the largest contribution on the side when is already selected. Then
Use all available numbers if there are fewer than two. Choosing a root clique gives the
value
and the maximum of these values is . A bottom-up pass followed by a top-down pass
computes all directed messages. At a triangle node it is enough to retain the three largest
incoming values, so excluding any one neighbor and taking the best two is constant-time
work per incidence. The incidence tree has linear size. Retaining the maximizing children
also returns the clique collection and hence a concrete coefficient construction on that
support. □
Corollary 6.8 (An intrinsic algorithm for partial -trees).Let be a partial -tree.
Its bipartite incidence graph between its ’s and its triangles is a forest. If contains a
, let be the maximum number of clique nodes in a connected selection in this forest
which uses at most three clique nodes at each triangle. Then
If there is no , the maximum is two when a triangle exists, one when there is an
edge but no triangle, and zero when there are no edges. These values and a maximizing
support can be computed in linear time directly from , without constructing a -tree
completion.
Proof.For all assertions are immediate. Otherwise choose any -tree completion only
for the proof. Every of is a maximal clique of the completion, and every triangle
of is one of its triangle nodes. The asserted incidence graph is therefore a subgraph
of the completion’s incidence tree, hence a forest. A connected clique selection gives
a -tree union, and the partial--tree edge bound forces that union to be induced in
. Corollary 6.6 gives both directions of the dimension formula. Without a , that
corollary excludes dimension at least three, and the stated simplices or segments
attain the remaining bounds.
Run the top-two-message dynamic program of Corollary 6.7 separately on every
component of the incidence forest and take the best answer. Its size is linear in .
Indeed, a partial -tree is -degenerate; from an elimination order in which each vertex
has at most three later neighbors, enumerate every clique by its earliest vertex and
a subset of those later neighbors. There are at most eight candidates per vertex,
and all edge checks take constant time using the bounded lists of later neighbors.
The order itself is obtained by the usual degree-bucket elimination in time. Thus
clique enumeration, forest construction, the dynamic program, and recovery of a
maximizing support all take linear time. □
6.4. Books, tree joins, and Hamiltonian graphs.
Several graph families now follow from the same triangle criterion. For a tree , let be
the largest number of vertices in a connected subtree of maximum degree at most
three.
Corollary 6.9.For and every nonempty tree ,
Thus supports a full-dimensional indecomposable weak summand exactly when has maximum degree at most three. Every Hamiltonian -tree also supports such a
summand.
Proof.The maximal cliques of share one triangle, so an admissible collection has
at most three members. In , with hubs , the maximal cliques are for . A connected
clique collection corresponds to a subtree , and the multiplicity of is . The dimension
formula of Corollary 6.7 gives both assertions. If has one vertex, its join is a triangle
and the formula is immediate. Finally, deleting three vertices from a Hamiltonian
cycle leaves at most three paths. Every triangle of a Hamiltonian -tree therefore
satisfies the component condition of Theorem 6.1. □
In particular, the common-triangle book on six vertices has an indecomposable
summand of dimension five. This corrects the computational claim in [1, Example 4.3,
version 5]; the first book without a full-dimensional ray has seven vertices.
The support classification also explains the linear ray counts in [1, Example 4.2]. Write
for the number of -dimensional rays on , and put . For ,
Indeed, a -dimensional direction support consists of the two hubs and an interval of
path vertices. There are such intervals. For each one, setting every omitted edge slack to
zero identifies its deformation cone with a face of the full cone. Its full-dimensional rays
remain extreme in that face and use the entire interval, so this counts each ray exactly
once. Poullot’s enumeration gives
The segment and triangle counts are respectively and .
7. Clique books
A clique book is a join , with the independent outer vertices forming branches over the
central clique. We now construct their responses so that the separator bound is attained
for every admissible number of branches.
Theorem 7.1 (Exact clique-book classification).For every and , let
Then
In particular, has a full-dimensional indecomposable weak summand if and only
if . A maximum-dimensional summand can always be chosen to be a lattice polytope
and an actual summand of
The upper bound follows immediately from separator capacity. For the reverse
inequality, each outer vertex will carry a monotone Boolean function on the
hubs. Its zero spoke equations leave one scale, and its boundary response is an
explicit vector. We construct positive circuits of these vectors of every size up to
.
7.1. Clique separators and Boolean response modules.
Theorem 7.2 (A clique-separator bound).Let be a clique of size in a graph . If
an extreme deformation ray has nonzero private coefficient blocks in components of
, then
Here is the capacity in Theorem 7.1; in particular, , , and .
Proof.There are boundary clique coefficients and boundary edge/context types.
Apply Lemma 5.1. In a book, each outer vertex is a component. An outer vertex
whose private block is zero has fixed coordinate after translation, giving the upper
dimension bound in Theorem 7.1. □
7.1.1. Boolean modules and positive response circuits.
Let be monotone, with and . For an outer vertex , the function
has clique support in . Its spoke slacks are .
The zero spoke equations force every private variation to be a scalar multiple of ; the
zero-valued sets form a downward-closed family connected to in the Boolean cube, while
the one-valued sets form an upward-closed family connected to . The zero cover differences
make the variation constant on each family; normalization sets the first constant to zero,
leaving one scalar on the second family. This argument includes every unused private
coefficient.
Index central elemental slacks by and . Put
Because is monotone Boolean, . Let be the injective map from central Möbius
coefficients to their elemental slacks.
Lemma 7.3 (Positive circuits of Boolean modules).Suppose the classes of in have a one-dimensional relation space spanned by a strictly positive vector , with
Then
spans an extreme ray of the deformation cone of . If the essential spoke directions form
a connected spanning graph, its dimension is . In particular, this holds when every depends on every hub.
Proof.Every spoke slack is nonnegative. A central edge slack, at fixed central context, is
Each summand is , , or . This proves all inequalities and makes every central
conditional minimum zero.
The spoke zeros already leave one private scale per module, so each private kernel is a
line. The conditional response of is . Theorem 5.4 therefore identifies the complete zero
space with the stated positive relation, proving extremality. Each essential spoke has
a positive slack, and connected essential spokes span the full zero-sum space.
□
7.1.2. The response quotient and pure signed coordinates.
For the constructions, we need coordinates in which boundary compatibility can be
checked one subset of hubs at a time. Expanding each response in monomials does this;
the same clique coefficient appears in several edge differences, and compatibility requires
those copies to agree. After quotienting out their common value, different hub subsets
become independent blocks.
Write each pair response as a multilinear polynomial in its remaining hub bits.
Its monomial on is indexed by . A central coefficient contributes that same
coefficient to every pair . These are exactly the integrability conditions. Consequently
Write for the class of a coordinate vector in the block. Then
and omitting any one coordinate gives a basis of the block.
Lemma 7.4 (Both signs of a pure coordinate).For , , define
Here is Boolean disjunction. Their response classes are and , respectively. Both
functions depend essentially on every variable of and ignore the other hubs.
Proof.The only negative second difference of is on its own pair , when all other
variables of are one. Thus its negative response is the monomial for that one
coordinate.
The minimal winning sets of have complements given by the block and the
singleton blocks of . Their pairwise unions are . A negative second difference can
therefore occur only in a full context, and there precisely on pairs joining distinct
blocks. Those are all pairs except . The resulting class is . The displayed formulas
show essentiality. □
When a positive relation among these integer response vectors is specified, its central
lift is constructive and integral; expand the weighted response sum in each pair coordinate
and take the common coefficient in every block. Formula (7.2) then bounds every slack by
the sum of the positive weights. This gives an actual lattice Minkowski complement in that
integer multiple of the graphical zonotope.
7.2. Constructive intervals for clique books.
The number of outer vertices is the number of columns in a positive response circuit.
We must therefore vary that number without enlarging the relation space. For small
counts, one full-context Boolean response cancels a chosen set of pure coordinates.
Threshold functions then reach many blocks at once, and splitting the cancelling columns
fills larger intervals. Near capacity, several threshold functions are needed to reach every
block; connector blocks first fix their relative scales. We construct these families in that
order, then check that their ranges cover every . All modules are monotone Boolean
functions, so their private kernels and positivity are controlled uniformly by
Lemma 7.3.
7.2.1. Every count up to the number of hub pairs.
Theorem 7.5.For every and , the graph has a full-dimensional lattice
Minkowski-indecomposable weak summand. The construction for is an actual
summand of .
Proof.We first note that every integer is the number of edges of a complete
multipartite graph on some subset of an -element set ; vertices outside that subset are
isolated. This follows by induction on . Counts at most use the induction hypothesis.
For a larger count, put , so . Write , with . Partition into blocks of size three,
blocks of size two, and singleton blocks for all remaining vertices. This uses vertices
before the singletons are added, and the sum of the numbers of within-block pairs is
exactly . Its complete multipartite graph therefore has the required edges.
The case is the simplex on the vertices of the complete graph . Suppose and put
, so . Choose a complete multipartite graph on a subset with exactly edges, and
let be its nonempty independent parts. Since , there are at least two parts. Define
the monotone Boolean function
Its minimal winning sets have pairwise union , with pairwise disjoint complements
. Hence its negative second differences occur precisely on the edges of , and only
when every other hub is present. In response coordinates,
This also follows directly by considering the two missing hubs; removing one vertex
from each of two different destroys every winning set, while either single removal
leaves one winning set.
Use one outer module and one outer module for every , all with weight one. Their
total negative response is on the full context of every hub pair and zero in every
other context; a pair in receives one contribution from and from the modules, while
every other pair receives from the modules. Thus the central function is explicitly
All conditional minima vanish after adding , and the complete slacks are sums of
nonnegative zero–one literals.
The response relation is unique. Let be the scale of and that of . Choose a
hub pair outside , which exists because . Comparing its full-context response with
that of forces . Thus the relation space is exactly the positive line with all scales
equal. The Boolean private-kernel lemma now proves extremality in the nonnegative
deformation cone.
Finally, every variable is essential in ; variables outside occur in every winning
set, and a variable in can be made pivotal by omitting one variable from a different
block. Every is also essential in all hubs. Their positive spoke directions connect all
vertices, so the dimension is . All coefficients are integral and every slack is at most
, proving the asserted actual lattice summand. □
7.2.2. Signed-star interpolation.
A single threshold module reaches many response blocks at once. Once its scale is fixed,
cancellation in a block of independent columns determines every other scale there. We can
therefore add branches by splitting a column into independent columns with the
same sum, preserving the unique positive relation. The following interpolation
performs these splittings within each block and fills the required intervals of branch
counts.
Lemma 7.6 (The threshold-star response).On a hub set of size , let
This function depends essentially on every hub. In the response block indexed by , , its
quotient class is
Proof.On a pair containing , the negative second difference is the indicator that
exactly one other hub is present. On a pair not containing , it is
The coefficient of a monomial of positive degree in an exactly-one indicator is ;
its constant coefficient is zero. Consequently, if , the -block coefficients are
Subtracting the common coefficient leaves the signed star in (7.4). If , every pair
coefficient is , so the quotient class is zero. Finally, is pivotal when all other bits are
zero, and any other hub is pivotal when and exactly one further hub is present. □
Lemma 7.7 (Every positive basis size for a signed star).Let have vertices, fix ,
and write
For either sign, and every , the vector is a sum of linearly independent pure
Boolean response columns, all with coefficient one. Every chosen module depends
essentially on every vertex of .
Proof.We use two basic pure response graphs. A partial star with center and
nonempty neighbor set is realized by
A clique on a subset , , is realized by
In both cases the minterm complements are disjoint, so the negative response is
exactly the indicated full-context graph. Variables outside that graph occur in every
minterm and remain essential. We also have the pure negative-edge module , with
response .
For , begin with its single star module. Split its neighbor set into nonempty parts,
one at a time, until all individual edges are separate columns. At every stage these
partial stars have disjoint supports and are independent, since their union omits
every pair inside , so no nonzero combination can be a constant vector on all pairs.
This realizes every count from one to .
Fix one reference pair inside . Regard the individual edge as a partial star
centered at . For every other pair inside , assign it to one endpoint, say , and perform
the replacement
The first new column is still a partial star centered at ; the second is . The sum
is unchanged and all coefficients remain one. The current span is the span of the
original star edges and the pairs already activated. Since the reference pair is always
omitted, the individual pair vectors in this span are independent. Each new pair
therefore adds exactly one rank and one column. At the end every pair except is in
the span, so the number of columns is . This fills all remaining counts.
For , use
The right side is one pure clique module. Split a clique into the star of one vertex
and the remaining clique, and split partial stars into smaller partial stars. Continuing
to the individual edges realizes every count from one to . The supports form a
partition of the clique edge set, so all these columns are independent.
Fix . For each , use the distinct seed edge , centered at , and replace it by
These are again a partial star and a negative-edge module. Every step increases
rank by one, because the reference pair remains omitted. After steps the count is .
This completes both signs and all counts. □
Proposition 7.8 (One distinguished threshold module).For , put
Every book with has a full-dimensional lattice indecomposable weak summand.
It can be chosen as an actual summand of .
Proof.Use just one distinguished function , with weight one. Its response is zero in
every block not containing , and by (7.4) is in every block containing . In each of
those blocks, independently choose between one and pure columns from Lemma 7.7
to cancel this signed star.
Each block’s columns are independent. Therefore, once the scale of is fixed, every
other scale is uniquely determined; they are all that same positive scale. The complete
response relation is a positive line. The Boolean circuit lemma proves positivity and
extremality, and its literal formula bounds every slack by the number of weight-one
modules. Essentiality of connects all hubs, and the other modules connect their outer
vertices, proving full dimension.
The minimum count is
The maximum is
The interpolation lemma changes one block count at a time, so every integer
between these endpoints occurs. □
Proposition 7.9 (A two-threshold bridge).The books have full-dimensional
lattice indecomposable weak summands for , and the books have such summands for
. These constructions are actual summands of .
Proof.The construction works on any hub set of size at least three. Choose distinct
hubs and use , both with weight one. In a block containing neither nor , their
combined quotient response is zero. In a block containing exactly one, it is a signed
star, so the preceding interpolation lemma supplies any count from one to .
In a block containing both, before the common parity sign the pair values are two
on , one on pairs meeting exactly one of , and zero on pairs meeting neither. The
value on is unique. Omitting that reference pair therefore expresses the opposite
response in the independent columns , , with strictly positive weights one or two.
The sole exception occurs in the connector triple , where we use just . If the two
distinguished scales in an arbitrary relation are , the connector’s three pair values
force , and then fix its own scale. Every other selected block has independent columns,
so all remaining scales are uniquely determined. Thus the complete relation space
is exactly the displayed positive line. As before, the Boolean circuit lemma gives
positivity and extremality, all coefficients are integral, and all weights are at most
two. Both distinguished modules depend on all hubs, giving full dimension.
For , the blocks containing both contribute one column from the connector triple,
two from the other such triple, and five from the whole four-element block. Together
with the two distinguished modules this is ten columns. The two exactly-one triples
each contribute one or two, giving every total from to .
For , the both-containing blocks contribute five columns from the three triples,
fifteen from the three quadrilaterals, and nine from the whole five-element block.
Including gives columns. There are six exactly-one triples and two exactly-one
quadrilaterals; they contribute any total from to . Thus every count from to occurs.
□
7.2.3. An interval ending at the separator capacity.
To reach the full capacity, one threshold module is no longer enough; we must reach
every response block. We use threshold modules and force their scales to be in the ratios .
A small set of quadrilateral blocks imposes those ratios. All other blocks then serve only to
cancel the fixed response, and can be filled to their full dimensions by the same splitting
operation.
Theorem 7.10.For , put
For every integer , the book has a full-dimensional lattice
Minkowski-indecomposable weak summand. The construction is an actual summand
of .
Proof.Label the hubs . Introduce the distinguished modules , , with intended weights
, and set . By the threshold-star lemma, their combined response in block has pair
values
modulo a common constant.
We first connect all their scales using quadrilateral blocks. Use the following three
blocks and equal-sum pair choices
For , also use with reference pair and other omitted pair . These connector
blocks are distinct. In each, introduce a pure column for each of the four retained
pairs . If
use when and when , with positive weight . These columns cancel the
distinguished response in that block, whose parity sign is minus. Exactly the two
omitted pairs have the reference sum, so all four weights are nonzero.
For an arbitrary relation, write for the distinguished scales and set . The two
omitted pairs in each connector must have the same value. The first three equations
are
They give . The remaining equations are , so every scale is . Once these scales
are fixed, the four retained pure pair columns in each connector are independent and
uniquely determined.
For an ordinary block , write
These star vectors satisfy . Any of them are independent; if an endpoint-sum
vector is constant over all pairs, then all are equal, and setting one forces all of
them to vanish. If is odd, let have the largest in ; if is even, let have the smallest.
The response needed to cancel the distinguished modules is, respectively,
Thus independent star columns suffice, with all weights strictly positive integers
at most .
A star, or any nonempty partial star, is a pure Boolean response module. For
center and nonempty , use
The minterm complements are and , so the negative response is exactly the
full-context partial star . Every variable of is essential.
We can increase the number of independent columns in this block one at a time,
until it reaches the full block dimension . Initially the selected stars cover every pair
of . Suppose their current partial-star columns span a proper subspace of the block.
Some pair vector lies outside . It belongs to a current partial star with at least two
edges, since a singleton would already put it in . Split that column into and the
remaining nonempty partial star. Both are available Boolean modules and inherit
the old positive weight. Their sum is the old column, and makes the new columns
independent, increasing rank and count by exactly one. Their supports still cover
every pair, so this continues to full block dimension and realizes every intermediate
count.
At every stage the ordinary columns remain independent and their span
contains the original star subspace. Hence they impose no further condition on the
distinguished scales, and their own scales are uniquely fixed once . The entire response
relation remains one-dimensional and strictly positive.
Initially the number of modules is
Each connector is a quadrilateral, so its three initial stars are replaced by four fixed
columns. At the end every ordinary block has full dimension and every connector
has one fewer. Write for the dimension of the response quotient. The final count is
Performing the splits one at a time realizes every integer between these endpoints.
The Boolean circuit lemma now proves positivity and extremality in the actual
nonnegative cone. The central coefficients, recovered from the weighted negative
responses, are integral. Every weight is at most ; this holds for the stars and
distinguished modules, while the connector differences are at most . Splitting
preserves a weight. Thus the literal formula bounds all slacks by . The distinguished
modules connect all hubs, and every other module connects its outer vertex to the
essential variables in . The dimension is therefore . □
7.2.4. Completion of the classification.
Proof of Theorem 7.1. The clique-separator bound gives the upper bound. We prove
existence in full dimension for every by induction on . The case , with , is the triangle
simplex. For , the small-count theorem already covers . For , the small-count theorem
covers through , the single-threshold interval covers through , and the two-threshold
bridge covers through .
For , first observe that is a spanning subgraph of ; move one of the hubs into the
independent part and delete its edges to the old outer vertices. An indecomposable
deformation supported on that subgraph remains an extreme ray in the larger
graphical deformation cone, since every extra edge has identically zero slack and
these zero equations define a face. The already-proved case therefore covers every
for . The single-threshold interval is , the two-threshold bridge is , and Theorem 7.10
gives . These intervals cover every count through .
For , the same embedding and induction cover every . The single-threshold
construction covers , and the arithmetic upper interval covers . These three ranges
overlap. Indeed,
and
This proves full-dimensional existence for every .
We also track the asserted dilation. The small-count and single-threshold
constructions use weights one, the two-threshold bridge uses weights at most two,
and the arithmetic upper interval uses weights at most . Their bounds are therefore
at most . In an inductive embedding, the bound is whenever ; all smaller counts are
covered directly by the small-count theorem. Thus the same bound holds in every
case, with integral coefficients throughout.
Finally, if , embed the saturated ray on any outer vertices. The other outer
coordinates are fixed up to translation. Its dimension is , and its dilation is . Together
with the upper bound this proves both formulas. □
Corollary 7.11 (Dimension spectrum and prescribed coordinate sets).The
positive dimensions of indecomposable weak summands of are exactly
More precisely, let be a prescribed set of at least two coordinates, containing hubs
and outer vertices. There exists an indecomposable weak summand of dimension fixing all coordinates outside exactly in the following cases
This is a statement about the varying coordinate set; it does not require every
ambient graph edge on that set to be an active direction.
Proof.Simplices on hubs and, if needed, one outer vertex give every dimension from
one to . For , embed the full-dimensional ray on the induced subbook ; it gives
dimension . The maximum-dimension theorem excludes every larger dimension.
For the refined statement, the induced graph on is . If , use its simplex. If , it
is a star, whose graphical zonotope has only segment rays, so full dimension occurs
precisely when . If , the exact clique-book theorem applies. With no hubs and at
least two outer vertices there is no nonzero direction. Finally, any summand fixing
the outside coordinates has all its active directions in this induced graph, so the same
cases are necessary as well as sufficient. □
7.3. Sharp direction counts at saturated clique capacity.
At the maximal branch count, the separator bound also controls the number of actual
directions by limiting how many outer vertices can be nonneighbors of a given
hub. The ambient book may still contain additional edges with identically zero
slack.
Theorem 7.12 (Minimum directions in a saturated book).Let and let be as in
Theorem 7.1. Put and, for ,
Among all full-dimensional Minkowski-indecomposable weak summands of , the
minimum number of actual edge directions is
Equality is attained by a lattice polytope. In every such full-dimensional summand
the actual hub graph is complete when , and each hub has at least active outer
neighbors. The equality construction has exactly active outer neighbors at every hub.
7.3.1. A lower bound from the actual hub graph.
For a graph on a fixed hub set, write
Here is the common-neighbor set of the ends of . These are precisely the response and
boundary-coordinate dimensions in Lemma 5.1.
Lemma 7.13.If and is a proper subgraph of on the same vertices, then .
Proof.Add a missing edge . Let and . The new cliques are exactly , where is a clique
of , including the empty clique. Their number is at most . The new edge contributes
to . For each , the existing edges and each gain one common neighbor, increasing
their contributions by and , respectively. No other edge’s common-neighbor set
changes. Therefore does not decrease, and it strictly increases whenever . Complete
to in any order. The last added edge has common neighbors, so at least that increase
is strict. □
Proof of the lower bound. Let be the actual direction graph of a full-dimensional
indecomposable summand, and let be its hub vertices. Every outer vertex has a
nonzero private coefficient block, since a zero block would fix that coordinate. The
components of are its outer vertices. Apply the general separator bound to the
boundary graph
For , the preceding lemma forces .
Fix a hub . In , every outer nonneighbor of is an isolated component, and the hub
together with its outer neighbors is one further component. All these components
have nonzero private blocks, again by full dimension. The separator is a clique of
size , so
Thus has at least outer neighbors. Summing over hubs counts every spoke once;
the complete hub graph contributes another directions.
For , the saturated book is . If an actual direction were missing, its
clique-supported function would be a sum of at most two edge segments.
A full-dimensional such sum is decomposable. Hence an indecomposable
two-dimensional summand has all three directions, which is the claimed value . □
7.3.2. A full-block matching circuit.
The direction bound imposes a different requirement from the branch count alone. To
attain it, each proper block will contribute exactly modules, essential only on . The
distinguished module scales must therefore be coupled entirely inside the full hub block.
The matching construction below supplies that coupling, leaving every proper block free to
use a basis.
Its negative response on a pair not containing is , and it is zero on pairs containing .
The same monomial calculation gives
in every response block. Both functions are monotone Boolean and essential in every
hub variable.
For a matching in a hub set , partition into the matched pairs and the remaining
singleton parts. The Boolean function whose minimal winning sets are the complements of
these parts has negative response graph , only in its full context. Therefore its quotient
response is
We call this a negative-matching module. A nonempty submatching has the same type
of realization. These functions are essential on whenever the partition has at least two
parts, as it always does in our construction below.
Equality for . Label the hubs . For , choose
In a block containing , its response is , where . In particular, the response in the
full block is .
For , let
These are nonempty matchings which partition all hub pairs, and . Omit and
take a negative-matching module for each , , with positive weight . Together with
the distinguished modules of weights , these have a zero response class in the full
block; on a pair with , the response is
and it is also one on the omitted pair . A constant pair vector is zero in the
quotient.
This full-block relation is unique. Write for the distinguished scales, for the
matching scales, and . The common pair value is , read from . Pairs in the same
matching must have equal endpoint sums. In particular,
using the pairs , then , then . These force for . For , the pairs and give , proving
the same formula for all . Finally for every matching. The relation space is exactly
the specified positive line.
Initially this circuit has columns and rank . We enlarge it inside the full block
until its rank is . The negative matching columns partition every pair except . If
the current total span is proper, some pair vector , , lies outside it, since these pair
vectors form a basis. Its current matching piece has at least two edges; otherwise
would already be a column. Split that piece into and the remaining nonempty
submatching, giving both new modules the old positive weight. Their response sum is
unchanged, while outside the span increases rank and column count by exactly one.
This preserves the unique positive relation and can continue until full block rank. At
the end there are full-hub modules, including the distinguished ones.
For every proper block , , use exactly pure signed pair modules. Choose as
reference pair the two largest hub labels in , whose endpoint sum is unique. The
combined distinguished response has pair values . Subtract its reference value and
cancel every remaining coordinate with or of the appropriate sign, with weight
equal to the nonzero absolute difference. All these weights are positive integers, and
the selected columns are a basis of that block.
The full-block circuit fixes every distinguished scale. Each proper block then
fixes all of its own scales uniquely. Thus the global response relation is a positive
line. The Boolean circuit lemma gives an integral indecomposable deformation with
nonnegative slacks. Its module count is
The distinguished modules connect every hub and all remaining modules have
essential spokes, so its dimension is . Every weight is at most , so, for example, is
an explicit integral dilation bound.
A proper-block module is essential exactly on , while every full-block module is
essential on all hubs. Therefore the number of outer nonneighbors of any hub is
The actual hub graph is complete by the already-proved lower-bound argument.
Each hub consequently has exactly outer neighbors, so the construction attains the
asserted number of directions. □
7.3.3. The smaller clique sizes.
For , the saturated book is . The complete clique-book classification supplies a
full-dimensional lattice ray, and the lower bound already forces every ambient direction to
be active. Its twelve edges equal . For , use the triangle simplex.
For , the following structural circuit attains directions. Use distinguished functions ,
both with weight one. In the full four-hub block, use the four additional positive pure
columns
The first two are partial stars and the last two are individual pairs. Their sum is ,
cancelling the distinguished full-block response .
This six-column full-block relation is unique. The pair has coefficient zero in every
column, so the common quotient constant is zero. The pairs fix the first two pure
scales to the scale of ; the pairs fix the last two to the scale of . The pair then
equates the two distinguished scales. All six scales are therefore the same positive
scalar.
In each of the four triple blocks the distinguished response is a nonzero signed star; if
exactly one of belongs to the triple, it is that star; if both belong, their sum is the
negative star of the third vertex. Use two independent positive pure columns from
Lemma 7.7 to cancel it. The entire response relation is again a positive line, with all
weights one. There are eight modules essential on triples and six essential on all four hubs,
hence fourteen outer vertices and
active spokes. The actual hub graph is complete, giving directions. The Boolean circuit
lemma proves positivity, lattice integrality, and indecomposability; the essential spokes
give full dimension. This completes all cases of Theorem 7.12.
8. Four-partite constructions
A bound on clique size does not bound separator capacity. For a boundary , the hub edge
has conditioning patterns, and the capacity is . We first treat , where a sparse
construction also gives edge-minimal supporting graphs beyond -trees, and then realize the
general capacity.
8.1. An exact bound for a nonclique separator.
The boundary need not be a clique for the response construction to attain the separator
bound. The diamond provides the first example in which the resulting full-dimensional ray
cannot be supported on any spanning -tree; its modules will also give an edge-minimal
family just above the sharp direction bound.
For a complete boundary on vertices the bound is . For the diamond , with other
vertices , it is
Theorem 8.1.For , let , with singleton parts and other parts and . Then
In particular has a nine-dimensional lattice indecomposable summand of . Its
actual direction graph has edges. However, has no spanning -tree which supports a
full-dimensional indecomposable deformation.
8.1.1. Six private modules and their positive closure.
The diamond response quotient has dimension five, so attaining its capacity requires a
positive relation among six branch responses. We use four modules depending
on only three boundary variables and two depending on all four, thereby also
controlling the number of actual directions. The last two modules are integer-valued
rather than Boolean, but their connected level sets still leave only one private
scale.
Use also for zero–one indicator variables. Define
Put
Every monomial of is a clique of .
Each is nondecreasing in its four Boolean variables. For it is a monotone Boolean
function; respectively it is , , , and . For the two remaining functions the four first
differences are
and lie in . Thus all slacks on edges incident with a private vertex are nonnegative, and
are at most two after weighting.
For a boundary edge , put . The negative responses are
Their weighted sum is exactly the boundary slack of
and both sides vanish on . Consequently
and every boundary conditional minimum is zero. The maximum of this expression over
the private bits is . On it equals
on it is two, and on it is respectively . Thus all boundary slacks are at most four.
Together with the spoke bounds, this makes a lattice summand of .
8.1.2. Private level sets and the boundary relation.
The zero first differences of leave one scale per module, by the Boolean-level-set
argument in Lemma 7.3. The same principle applies to the two integer-valued modules.
Their values at fixed are
Each level set is connected along cube edges on which the function is constant. For , the
middle level joins the face ; its bottom and top levels are a down-set and an up-set. For ,
the two middle levels join respectively through and , as the table shows; the extreme
levels are singletons.
A private variation with the same zero spoke rows is therefore a function , with . The
absence of the edge forces its mixed difference to vanish. For , the slice gives . For , the
slices and give
Thus the variation is a scalar multiple of in both cases, including all unused private
coordinates.
It remains to identify the relations among the six negative responses. Give them scales
and ask when their sum is a boundary slack vector. Its row is zero, so the central
coefficients on and vanish. Comparing the and coefficients in its row then gives
The row gives . Agreement of the coefficient in the rows gives
Hence the response relation space is exactly . Its central lift is , so Theorem 5.4 proves
extremality.
All five boundary edges have positive slacks somewhere. Modules use , modules
use , and modules use all four boundary variables. There are therefore actual
directions, forming a connected graph on all ten vertices. The polytope has dimension
nine.
8.1.3. Maximum dimension and the obstruction to a spanning -tree.
Apply Lemma 5.1 with . Every indecomposable ray has at most six active private
vertices, so its dimension is at most , as well as at most . For , the construction above,
using six private vertices and setting the remaining coefficients to zero, attains
nine.
For , take a spanning tree of as follows. Use one private vertex to form the path , and
attach the remaining at most four private vertices to , with at most two additional
leaves at each. This is a subcubic tree. The graph is a spanning -tree contained
in , and every triangle has multiplicity at most three. Theorem 6.1 supplies a
full-dimensional indecomposable weak summand, proving the formula for all
.
Finally, every of consists of , one of , and one private vertex. Any spanning -tree
contained in is consequently for a spanning tree of . Such a tree has seven edges. If it
supported a full-dimensional indecomposable deformation, the triangle-capacity criterion
would force . But every edge of has one endpoint in , giving , a contradiction. Thus no
spanning admissible -tree occurs. All graphs used in this theorem are -free, since is
complete four-partite.
8.2. An edge-minimal supporting family beyond -trees.
The ten-vertex ray has a triangular boundary through which the rooted modules of the
-tree construction can be attached indefinitely. The extended graphs have one more edge
than the absolute minimum, with every edge still indispensable.
Theorem 8.2.For every , there is a -free graph with exactly edges and
treewidth four, and a full-dimensional lattice Minkowski-indecomposable summand
of whose actual direction graph is . No proper edge-subgraph of supports a
Minkowski-indecomposable weak summand of dimension . In particular has no
spanning -tree supporting such a ray.
Define the base graph to be the actual direction graph in Theorem 8.1. More
explicitly, it is , with hubs , where has vertices and edges
Thus is a four-cycle with two leaves at each of two opposite vertices. Let . To
obtain , add vertices successively, giving the three earlier neighbors , where
.
Lemma 8.3 (A rigid boundary in the base ray).Let be the ten-vertex polynomial
constructed above, and put . Relative to boundary , its private coefficients have a
one-dimensional private zero space. Its conditional minima, in the edge order , are
Every internal edge of retains a positive slack.
Proof.Subtracting a boundary pair changes neither an internal slack nor a private
equation. For the response, the base polynomial gives
Their conditional minima are respectively and zero. For the edge , all four choices
of can attain a zero when ; the third private module has , so its zero bit always
minimizes it, and the other private bits can be minimized independently. When ,
choosing still attains zero. Hence both conditional minima at are zero, proving the
stated response after subtracting .
For the private-kernel assertion, each of the five modules other than retains all its
spoke zero equations, since none of its spoke edges lies in . The proof above therefore
fixes these five blocks up to scales . For the third module, its private part has the
form
The internal edge has zero slack at . These equations give and , so this private
block also has one scale . We may complete it by ; the discrepancy is supported
entirely on the four boundary cliques of .
The old central edges are internal relative to . Their eight conditional minimum
equations are retained. For the boundary edge with , the four choices of are all
conditional minimizers, as just observed. Differences between these four minimizing
rows determine the two central triangle slopes and impose the four-context
compatibility at . Together with the eight internal minimum equations, they give the
same coefficient comparisons as the preceding boundary relation
Thus
The four old central edge coefficients other than , and the two old central triangle
coefficients, are then the same scalar times their original values. These are all the
remaining private coordinates. Hence the private zero space is precisely the line
spanned by ’s private vector. Boundary pair and triangle coefficients are excluded
from this assertion, as required. □
Proof of Theorem 8.2. The base case is Theorem 8.1. For , let be the rooted -tree
module supplied by Lemma 6.2 on the branch with successive cliques and boundary
. Prescribe its response to be in the edge order . Define
This is an integral, uniform recursive construction.
All internal slacks are nonnegative. On each boundary edge and each third-vertex
bit, the two branch responses add to , and the closing boundary terms contribute
. Therefore all six boundary minima are zero. The two complementary nonconstant
responses have a unique relation in , so Theorem 5.4 gives extremality.
Every old internal direction is retained, and every new internal direction occurs
by the module lemma. Its strict boundary excess also makes all three edges of actual
directions. No other directions occur, since all coefficients are supported on cliques
of . The graph is connected, so the polytope has dimension .
For the asserted dilation, every base slack has range at most four. Subtracting the
boundary edge does not change any of these ranges. Every slack of has range at most
; apply the edge-marking oscillation argument from the quantitative bound for rooted
-tree modules, using its quadruple coefficients equal to one and triangle coefficients
with . This argument also applies to boundary edges, whose boundary-triangle
coefficient is zero. Conditional on the third boundary bit, the new slack has minimum
zero and range at most . Internal slacks have the same or smaller bound. Hence
on every graph edge, proving that the polytope is an actual summand of . Integral
greedy vertices give the lattice claim.
Each added vertex is simplicial with three earlier neighbors, so -freeness is
preserved and . The base graph has a tree decomposition with bags , all sharing .
Appending the bag at each step keeps treewidth at most four. A graph of treewidth
at most three has at most edges, so the displayed edge count makes the treewidth
exactly four.
There is no spanning admissible -tree in , since it is a subgraph of . If one existed
in , its last added vertex would have degree exactly three; every vertex of a -tree has
degree at least three, and has only three available neighbors. Deleting this simplicial
vertex leaves a -tree and cannot increase any triangle multiplicity. Repeating the
deletion would produce a spanning admissible -tree in , a contradiction.
Finally, a full-dimensional indecomposable ray on a proper edge-subgraph would
have at most actual directions. The sharp direction bound forces equality and
makes its direction graph a spanning -tree; the classification makes it admissible.
The preceding obstruction excludes this possibility. Thus deleting any nonempty set
of edges destroys full-dimensional supporting capacity, completing the proof. □
8.3. Sharp exponential separator capacity in -free graphs.
The diamond construction uses the two independent boundary vertices to separate its
responses. For a boundary , there are such contexts, and a branch can be assigned to each
one. Another branches balance their side responses, attaining the full separator capacity
without increasing the clique number.
For , put
These boundary capacities are attained by -free graphs.
Theorem 8.4.For every , the graph has a -dimensional lattice indecomposable
summand of , where . Moreover, for every ,
8.3.1. The explicit functions.
Let the two singleton parts be , and let the third part be . Split the last part into
vertices , indexed by , and additional vertices . In polynomial formulas, each vertex symbol
denotes its zero–one membership indicator. Put .
The module at must have negative hub response only at , which is exactly the negative
part of the affine function . We realize this function as the mixed difference of a
polynomial whose first differences are nonnegative; the extra modules then balance the
remaining boundary responses.
For , write and . Define
Here . Take the central function
and set
Every monomial in this polynomial is a clique of of size at most four. All coefficients
are integers, and there are no constant or singleton coefficients. In particular,
The polytope is the generalized permutahedron with lower set-function .
8.3.2. All elemental inequalities.
First consider a single module . Its four values as a function of are
It is nondecreasing in every variable. For example, its increments in at are
The second is nonnegative because either or . Its increments in at are
and each coefficient of is a zero–one function of . The functions are monotone Boolean
functions. Therefore every spoke slack on an edge incident to a vertex or is
nonnegative.
The boundary graph on is . Its negative conditional responses are especially simple.
Write . Direct differentiation gives
The nonzero derivatives on are when and when , so they have no negative
part.
For each fixed , exactly one module has negative response. For each , exactly binary
vectors have . It follows from (8.3)–(??) that the central coefficients of cancel the sum of
all negative responses exactly
Every boundary conditional minimum is therefore zero. More explicitly, its full slack is
the sum, over outer modules, of
with the positive module weights included. Each term is nonnegative; if the derivative is
negative it is , and otherwise it is . This proves all elemental inequalities for all choices of
conditioning variables.
8.3.3. The zero equations force one positive scale.
We first establish the required private rigidity of each . Write a general variation of its
private coefficient function as
where each is an arbitrary bilinear function of . The original has three values equal to
one and one value equal to zero. If , its zero is at ; its two zero boundary derivatives occur
on at and on at . If , its zero is at ; its zero derivatives occur on at and on at
.
The zero spoke row fixes the zero value of . The two zero boundary derivatives equate
its three other values. All these equations are present in the global zero face; when a
module derivative vanishes, its outer membership bit can be switched between zero and
one while every other module is kept at its conditional minimum. Their difference is the
required equation. Consequently
The derivative vanishes at each of the Hamming neighbors of . Switching the
corresponding outer bit in these zero contexts gives
Thus all equal a common , and . For the same single equation gives the latter identity,
with only one to consider.
The zero -spoke context at gives . If , the zero -spoke context at with all gives . If ,
use instead, giving and hence . Therefore . This proves the private kernel is a line for
every .
Each extra function is monotone Boolean. Its zero spoke equations already force one
private scale, by the connected-zero-region and connected-one-region argument of
Lemma 7.3. Its ignored variables simply have identically zero spoke derivatives and
introduce no additional freedom.
Now let a vector satisfy every global tight equation of . The preceding argument leaves
a private scale for each and a scale multiplying each unweighted . Write its central
coefficients as
The two conditional minimum equations on are simply
because no module has a negative response. Hence . The minimum equation at
context is then
All main module scales equal . Finally the equations at give
Every coefficient has therefore been forced to the same common multiple of the
constructed vector. The latter is nonzero and belongs to the nonnegative cone, so it spans
an extreme ray and is Minkowski-indecomposable.
8.3.4. Dimension, dilation, and sharpness.
All spokes of each main module are active. The -spoke has a zero–one coefficient
taking value one. The hub spokes are positive by the displayed monotonicity formulas,
including the case by choosing a suitable -context. Each extra vertex has positive
directions to . These directions form a connected spanning graph, so the dimension is
.
The actual direction graph omits precisely the edges with from . The edge and every
have positive central coefficients; each has a positive module derivative. Thus the actual
number of directions is
Every clique of uses at most one vertex from each of its four independent parts,
verifying the -free condition directly.
To obtain the quantitative dilation, fix in an slack. Among the main modules, the sum
of the Hamming distances is , and the only negative derivative is , at . Hence
The central coefficient contributes one, and the extra modules contribute at most . The
largest slack at this fixed context is therefore
It attains at . The and slacks are at most . Main-module spoke slacks are at most ,
and extra-module spoke slacks are at most . For all are at most . Thus on graph edges
and nonedge slacks vanish. This gives an actual Minkowski complement in . All
data are integral, so both generalized permutahedra are lattice polytopes up to
translation.
Finally, take the separator . Its induced graph has clique coefficients of size at least
two. There are boundary contexts on and two on each of its other edges, for a
total of . Lemma 5.1 therefore bounds the number of active outer blocks by
Any indecomposable weak summand of consequently has dimension at most . For ,
embed the constructed polytope on any of its outer vertices. Its dimension and
indecomposability are unchanged, and unused graphical segments can be added
to the complement. This proves the claimed exact stabilization and completes
Theorem 8.4.
Corollary 8.5.For every , the graph has a full-dimensional indecomposable
weak summand but contains no spanning -tree satisfying the triangle condition of
Theorem 6.1.
Proof.Every of contains both universal vertices , one vertex of , and one vertex of
the last part. A spanning -tree must therefore be , where is a spanning tree of the
bipartite graph between the two nonsingleton parts. Its triangle multiplicities are the
vertex degrees of , so the triangle condition requires to be subcubic. But has edges,
all incident to the vertices of . Subcubicity would give
which is false for . □
8.3.5. Decision-tree partitions and every intermediate size.
The point indicators in (8.3) can be replaced by the cells of a decision-tree partition.
This provides every remaining full-dimensional case.
Lemma 8.6 (A cube partition construction).Let a full binary decision tree
partition into cells. An internal node tests a coordinate, no root-to-leaf path tests
a coordinate twice, and every coordinate is tested somewhere in the tree. For a leaf ,
write its cell as
and put . Then has a full-dimensional lattice indecomposable weak summand
which is an actual summand of
Proof.For each cell, use the module (8.1) on its fixed coordinates , replacing by and
ignoring all other . Its negative response is exactly the indicator of . Its response
has no negative part, and its negative response is when , and zero otherwise.
Let and be the numbers of leaves fixing coordinate to zero and one, respectively.
Because coordinate is tested at an internal node, both its child subtrees have leaves,
so . Add the extra modules with weights , and use central function
The cell indicators sum to one. The responses sum to , and the negative responses
vanish. Thus every boundary conditional minimum is zero, and the same positive
factorization proves all inequalities.
Each cell module has the one-dimensional private kernel already proved, with
replaced by . Ignored coordinates have identically zero spoke derivatives and give
no additional freedom. The minimum equations kill all central and coefficients in
a variation. On a given cube cell, the minimum equation then equates its unique
module scale with the central coefficient. All cell scales are equal, and the equations
force the extra scales to be times this common value. Hence the complete zero
space is one-dimensional. Every vertex belongs to a nonzero module and the positive
directions connect all vertices through the hubs, so the polytope is full-dimensional.
We record the exact dilation. Fix . Exactly one cell module has derivative , and
all the others have nonnegative derivative. Consequently
After adding the central constant and the positive contributions of the extra
modules, the largest slack at this is
Its maximum is , attained at . The other boundary slacks are at most , the extra
spoke slacks are at most , and a cell-module spoke is at most its depth . A full
binary tree with leaves has internal nodes, each with at least two descendant leaves.
Counting leaf depths by ancestors gives , hence . This proves the claimed exact bound
on every slack and the actual Minkowski-summand assertion. □
Theorem 8.7 (Complete four-partite classification with two singleton parts).Let
and put . Then
Equivalently, this graph has a full-dimensional Minkowski-indecomposable weak
summand if and only if
All dimensions in the formula are attained by lattice polytopes.
Proof.The graph is symmetric in its two nonsingleton parts, so assume . The
separator bound gives the upper bound in the formula. Theorem 8.4 already gives
equality for . It remains to construct full-dimensional rays when .
For , take a subcubic spanning tree of . An explicit choice starts with the
alternating path through all vertices of the smaller part and vertices of the larger
part. Attach the remaining vertices as leaves. For , the path endpoints have room
for two leaves each and its other smaller-part vertices have room for one each, giving
total capacity . The inequality is exactly what is needed. For , use the star with
at most three leaves. Then is a spanning -tree with triangle multiplicities at most
three. Its full-dimensional ray from Theorem 6.1 is also a weak summand of the
larger graphical zonotope.
For , put . There is a binary decision-tree partition using every coordinate with
any prescribed number
of leaves. Begin with a full binary tree with internal nodes and label these nodes
by the different coordinates. Then repeatedly split a leaf using a coordinate not yet
tested along its path. A split adds one leaf and preserves the partition. Until all
point cells are reached there is a leaf of depth less than , so a split is always possible.
Lemma 8.6 supplies a full-dimensional ray on precisely outer vertices. This proves
every case of the formula. □
Remark 8.8 (A balanced quantitative choice).The initial -internal-node tree can
be chosen balanced, and thereafter one can always split a shallowest leaf. Its depths
are then and . Initially label the internal nodes by distinct coordinates; subsequent
splits use any coordinate not already on the chosen path. The path depth remains
at most , and every coordinate remains in use. With , this gives
Thus the intermediate-size construction is an actual integral summand of , and
its largest elemental slack is exactly .
8.4. Comparison with spanning -trees.
The exponential capacity cannot be reached by using only the sparse supports of
Section 6. The following criterion gives the exact limitation of that approach on every
complete four-partite graph.
Theorem 8.9 (Spanning admissible -trees).Let and . The graph contains a
spanning -tree in which every triangle belongs to at most three maximal cliques if and
only if
If is the sum of the three smallest part sizes, the largest dimension of an
indecomposable weak summand whose actual direction graph is a -tree is
This last formula restricts the direction graph to a -tree; it is not a formula for
all indecomposable weak summands of the complete four-partite graph.
Proof.Every tetrahedron uses all four colors. In a properly four-colored -tree, the
number of triangles missing color is ; the initial tetrahedron contributes one, and
each subsequent vertex of another color contributes one new such triangle. The
tetrahedra each contain exactly one triangle missing color . The multiplicity bound
therefore implies
which is the stated necessary inequality.
Conversely start with one vertex of each color, forming a tetrahedron. Every face
initially has two available attachment slots. After additional vertices have been
inserted, with of color , the number of available slots of missing color is
Attach any still-required color with a positive number of slots. Two colors cannot
both have zero slots, since that would imply . If the procedure stopped before reaching
the target, a single required color would remain and its final availability would
be negative. The assumed inequalities say precisely that every final availability is
nonnegative. Thus the procedure reaches the prescribed counts without using any
triangle more than three times.
For the dimension statement, retain all vertices in the three smaller parts and
vertices in the largest part. This count is at least each of the other three part
sizes. The preceding criterion gives an admissible -tree on exactly vertices. Its
full-dimensional indecomposable ray exists by the -tree classification. Conversely, any
admissible -tree support uses some number of vertices outside the original largest
part. The necessary inequality for that part bounds its total number of vertices by .
This proves the sharp restricted dimension formula. □
For example, when , the largest dimension obtainable from an admissible -tree support
in is
For , the unrestricted answer from Theorem 8.7 is . The difference from the best -tree
support is therefore .
9. Lattice summands
9.1. Sharp dilation for lattice summands on 3-trees.
For weak summands, a dilation factor has no intrinsic meaning unless a normalization
is imposed, since one can always rescale the summand. Here a lattice polytope means one
with vertices in the fixed standard lattice , and the same conclusions hold for translates of
such polytopes. With this normalization, the uniform factor two in Theorem 3.1 is optimal
on graphs with the minimum number of directions.
Theorem 9.1.Let be a -tree on vertices. If is a lattice indecomposable polytope
of dimension and for a polytope and , then . Equality is attained by when . More
precisely, the four-clique Möbius coefficients of the lower-support function of are
nonzero integers, and every edge of satisfies
Lemma 9.2.If a full-dimensional indecomposable generalized permutahedron has
a -tree as its direction graph, every four-clique Möbius coefficient is nonzero.
Proof.Corollary 4.4 gives a triangle-connected family of nonzero four-clique
coefficients whose union is the direction graph. A connected family of four-cliques
covers at most vertices; start with four and introduce at most one vertex at each
subsequent shared-triangle step. A -tree has exactly four-cliques. Thus the family
must contain all of them. □
The edge and triangle coefficients supply the constant and linear terms of an edge slack,
so a lower bound depending only on tetrahedra must eliminate their contribution.
Averaging at opposite sign vectors removes the linear terms; on a tree, the remaining
interaction signs can then be chosen independently to give the following oscillation
bound.
Lemma 9.3.Let be a finite tree, and let
Then
If is integer-valued, the right-hand side may be rounded up to the next integer.
Proof.Put , with , and average the values at and . The linear terms cancel, leaving
for a constant . Every such average lies between and . On a tree, arbitrary
prescribed edge products are realizable; fix one root sign and propagate the signs
along the unique paths. We may therefore make all summands simultaneously , and
also simultaneously . The difference of these two averages is , proving the bound.
Integer-valuedness makes the oscillation an integer. □
Proof of Theorem 9.1. The actual direction graph of is contained in . By
Theorem 4.1, it has at least edges, while a -tree has exactly . Hence the actual
direction graph is itself. Lemma 9.2 makes every four-clique coefficient nonzero.
These coefficients are integers; the minimum of over a lattice polytope is an integer,
and Möbius inversion preserves integrality. This remains true if is only a translate
of a lattice polytope, because translations affect only singleton coefficients.
For an edge of a -tree, its common-neighbor graph is a tree. This can be seen
directly from a -tree construction. When first appears, it has two common neighbors,
joined by an edge. A later vertex becomes a common neighbor of both ends of
precisely when it is attached to a triangle containing ; in the common-neighbor graph,
it is then attached as a leaf to the third vertex of that triangle. These are the only
changes. The edges of this tree are in bijection with the four-cliques containing .
The elementary difference at , as a function of its common-neighbor indicators,
is therefore a Boolean quadratic polynomial whose interaction graph is this tree and
whose quadratic coefficients are exactly the for four-cliques . The decomposition
gives
for every conditioning set , because the corresponding elementary difference of is
one. Lemma 9.3 now gives the displayed edgewise lower bound.
Finally, a -tree on at least six vertices has at least three four-cliques. Their
shared-triangle adjacency graph is connected, so choose three distinct cliques with
adjacent to and adjacent to . The triangles and are three-element subsets of the
four-element set ; they intersect in an edge. That edge belongs to all three cliques.
Its three nonzero integer coefficients have absolute-value sum at least three, so
The same argument gives the exact integral dilation for the original hub-and-path
family.
Corollary 9.4.For , , the smallest real for which has a full-dimensional lattice
indecomposable summand is
In particular the smallest factor is one on four and five vertices. For the path-cube
graphs , the smallest factor is one for and two for every .
Proof.The graph is a -tree. Its hub edge belongs to all four-cliques, and its
common-neighbor graph is . The proof of the edgewise inequality above applies also
for and gives
Theorem B.1 attains this bound. On four vertices both graph families are ; on
five vertices both are isomorphic to with one edge deleted. The remaining path-cube
cases follow from Theorem 9.1. □
9.2. The sharp limit for lattice summands without dilation.
For the unscaled zonotope, integrality requires every elemental difference to be zero or
one. In a -free graph these differences are quadratic, and that combination forces a
complete classification of the possible direction supports. As above, integrality refers to the
fixed standard lattice .
Theorem 9.5.Let be a -free graph on vertices, and suppose that a lattice polytope
is a Minkowski-indecomposable summand of with . Then is a complete four-partite
graph in which every part has size one or two, and every edge of is an actual direction
of . In particular, .
Equality is attained by a seven-dimensional indecomposable lattice summand of .
The upper bound also holds for a translate of a lattice polytope. The intermediate
part-size patterns are attained as well, as proved below.
Let be the family of nonzero four-clique coefficients. Corollary 4.4 says that this family
is triangle-connected and its edge union is the actual direction graph.
9.2.1. Boolean quadratic links.
For an actual lattice summand of , every elementary difference satisfies
Indeed, it is a nonnegative integer and is at most the corresponding elementary
difference of , which is one on a graph edge. On the common-neighbor variables of an edge
, write
The interaction graph has an edge precisely when the last coefficient is nonzero. Thus
its edges correspond to the members of containing . We use only nonzero interactions, not
every four-clique of the ambient graph.
Lemma 9.6.Under the hypotheses of Theorem 9.5, if then every nonzero
four-clique coefficient is or . For every edge in the actual direction graph, is a single
edge, a path with two edges, or a four-cycle whose coefficient signs have product .
Every triangle is contained in at most two members of .
Proof.The difference of a Boolean-valued quadratic polynomial between and is an
affine function taking values in . Its oscillation is the sum of the absolute values of
its linear coefficients. Consequently, for every triangle ,
In particular, has maximum degree at most two. If , each triangle of has no other
nonzero four-clique extension. Such a is an isolated member of the shared-triangle
graph of . Corollary 4.4 would then force . Thus for every nonzero four-clique
coefficient is , and each triangle has at most two extensions.
The graph is connected on its nonisolated vertices. Otherwise would split into
polynomials on two or more disjoint nontrivial variable sets, together with any
isolated linear terms. Each polynomial with a nonzero quadratic coefficient is a
nonconstant integer-valued function and has oscillation at least one. Oscillations of
sums on disjoint variable sets add, contradicting the total oscillation at most one.
By Corollary 4.4, every actual direction is contained in a nonzero four-clique, so is
nonempty.
A connected graph of maximum degree two is a path or a cycle. A path with at
least three edges is excluded by Lemma 9.3; its oscillation is at least . A three-cycle
in would make a on its three vertices together with the ends of .
For a cycle of length , pass to signs and average the values at and , as in
Lemma 9.3. The nonconstant part of this average is
On a cycle, all desired edge products can be prescribed except, at worst, one.
Hence the maximum of the sum is at least , and its minimum is at most . Its
contribution to the oscillation is at least , which exceeds one when . For a four-cycle
with sign product , both the all-positive and all-negative signed contributions are
simultaneously realizable, giving oscillation two. The only remaining cycle is a
four-cycle with sign product . □
9.2.2. Completion to a join of four small parts.
The local link restrictions force a global product structure because two face changes
from one four-clique give three consecutive edges in a pair link. Such a path must close to
a square, so the two changes commute. Repeated square completion will turn
the four original vertices into four independent choices, each with at most two
possibilities.
Lemma 9.7.Let be a finite family of four-element sets, connected through shared
three-element sets. Suppose each three-element set belongs to at most two members.
For each pair contained in a member, form the link with edges whenever ; assume
that this link is a single edge, a two-edge path, or a four-cycle. Then there are four
pairwise disjoint sets , each of size one or two, such that
Proof.First consider a member with neighbors across two distinct faces. Write its
four vertices as , and suppose the neighbors replace by and by , where . For the
pair , the interaction graph contains the three edges
If , these would form a three-cycle, which is not one of the allowed links. Thus
they form a three-edge path. The allowed-link condition forces its completion to the
four-cycle, so
This fourth member completes a unique commuting square of face changes.
Start with one member, regarded as the complete join of four singleton parts.
Inductively suppose that contains the complete join of four disjoint parts of sizes one
or two. If this is not the whole shared-face component, choose an outside member
adjacent to a member of the join. It cannot replace a vertex in a doubled part; the
shared face already has its two extensions within the join. It therefore replaces a
singleton vertex, say , by a vertex .
The vertex is new to the entire join. It cannot equal a chosen vertex of another
part, because the outside member has four distinct vertices. If it were the unused
choice of a doubled part, the change to that choice and the change from to would
give a triangular interaction link, which is forbidden. Thus is distinct from all vertices
already used.
Apply the commuting-square completion successively with every doubled part.
For every old choice of one vertex from each part, it supplies the member obtained
by replacing by the same . Hence the enlarged family is the complete join with the
singleton part replaced by . The vertex labels of each completed member are explicit,
so the construction is consistent regardless of the order of the squares.
Each enlargement doubles one of only four parts. After at most four enlargements,
either the whole connected family has been obtained, or all parts are doubled. In
the latter case every face already has two extensions and no outside member can be
adjacent, so connectedness again implies that the family is complete. This proves the
assertion. □
Proof of Theorem 9.5. Consider the four-cliques with nonzero coefficient. By
Corollary 4.4, if their edge union is , giving the assertion. Otherwise Lemma 9.6
gives all hypotheses of Lemma 9.7. The edge union is precisely the actual direction
graph, so this graph is complete four-partite with part sizes at most two. Its vertex
count is at most eight. Any extra edge of would join the two vertices of a part; with
one vertex from each other part, it would form a . Thus there are no extra edges. □
9.3. Unit lattice summands from Boolean quadratic phases.
The four-partite restriction came from combining Boolean slacks with clique number
four. Keeping the Boolean slacks while allowing more parts gives lattice indecomposable
summands in arbitrarily high dimension, with indecomposable complements as well. We
construct these pairs from quadratic sign functions; the four-part case also supplies the
sharp examples in the -free classification.
Theorem 9.8.Let have parts. The zonotope is the sum of two
Minkowski-indecomposable lattice polytopes of dimension . Both summands have
Boolean elemental slacks and actual direction graph .
For even , both are centrally symmetric up to translation. For odd , the complement
of a summand is a translate of ; thus is a translate of the difference body .
We seek Boolean edge slacks whose zero sets determine them up to scale. On a
complete multipartite graph, each slack belongs to a tensor product of three-dimensional
polynomial spaces, where a nonseparable sign function will give precisely the required
one-dimensional face.
Lemma 9.9 (A Boolean face in a multipartite polynomial space).For , let
Write and , so that all are independent signs. Let take values in and suppose
it does not factor across any nonempty proper partition of its variables. Put
Then the space of polynomials in vanishing wherever is exactly the line . For the nonfactorization hypothesis is empty, and the same conclusion holds.
Proof.In one part, the basis becomes . Hence choosing the parts on which a monomial
contains leaves an arbitrary function of exactly those . Every therefore has a unique
expansion
where is an arbitrary function of the signs indexed by . Vanishing on is
equivalent to the pointwise identity . Comparison of the -parity components gives
Suppose is nonempty and proper. If either side is nonzero at any point, fixing that
point on one side of the partition shows that the function on the other side is nowhere zero
and has constant absolute value. Repeating in the other direction gives the same property
for both functions. Equation (9.1) would then factor across , contrary to the hypothesis.
Hence both components vanish.
Only remain. If , then , so . Conversely every multiple of vanishes on its zero set.
□
We also record the elementary quadratic-sum calculation used for positivity and
integrality. Over , put
The associated bilinear matrix is , where is the all-ones matrix. For even it
is invertible and . For odd its kernel consists of zero and the all-ones vector.
Squaring the sum and setting the difference of its two summation variables to gives
Consequently
For even , the normalized transform is a quadratic sign function. Completing the square
shows that the exponent of , as a function of , has quadratic part ; its associated bilinear
matrix is . Its constant and linear terms may differ. Such a sign function is nonseparable
across every nontrivial partition; a variable on each side has mixed Boolean second
difference one in the exponent. Equivalently, the product of its values at the four corners
obtained by flipping those two variables is minus one, whereas a separable sign function
would give plus one.
9.3.1. The even case.
Let be even, and label the two vertices in part by . For Boolean variables put . Define
The quadratic graph term below gives every edge slack . The signed products will
change each slack by exactly in absolute value; the quadratic-sum formula determines
their common normalization. Consider
Discard its constant and singleton terms, and let be the resulting polynomial evaluated
at the indicator of . This normalizes . Every remaining monomial is supported on a clique
of .
Fix an edge between vertices and . Taking its two Boolean differences in (9.3) gives
On the remaining parts, write , . The sum is a quadratic Walsh sum multiplied by .
Since is even, (9.2) yields
where is a sign function with complete quadratic part . Thus every edge slack is zero or
one. Every nonedge slack is zero because no monomial contains two vertices of one
part.
The function is therefore supermodular, as is , where counts the graph edges induced
by . Their base polytopes satisfy
This is an actual summand identity for the unweighted zonotope.
To check integrality, let be a clique of size , with its vertex choices fixed. Its Möbius
coefficient is
The extension sum has free bits. If is even, its magnitude is , so the second term has
magnitude . At this is one half, and the displayed coefficient is zero or one; at even it is
integral. If is odd, the extension sum is zero or has magnitude , so the coefficient is zero or
has magnitude , again integral for . The normalized singleton and constant coefficients are
zero. Both summands therefore have integral set functions and integral greedy
vertices.
For extremality, let satisfy all elemental equalities tight at . For a fixed edge, its slack
polynomial belongs to . The function in (9.4) is nonseparable, so Lemma 9.9
forces the slack of to equal . Every maximal clique has a nonzero coefficient
For every , the coefficient of the remaining variables in its slack is the original clique
coefficient, so
Since this coefficient is nonzero, all edge scales in the clique agree. Maximal cliques
whose choice vectors differ in one bit share vertices, so their scales also agree. The
Boolean cube of choice vectors is connected, and every graph edge lies in one of these
cliques. Hence all are one common scalar. Every nontranslation coefficient contains an
edge, so . Nonnegative slacks imply .
The same argument applies to the complementary slacks , using , and proves that both
summands are extreme rays. Every edge slack is nonconstant and hence positive
somewhere. Both actual direction graphs are , so both dimensions are . Lemma 2.1 gives
Minkowski indecomposability.
9.3.2. The odd case.
Let be odd. Start with the construction on parts and restrict its set function to the
vertices of any parts, deleting one entire part. In the spin polynomial this sets both spins
of the deleted part to one. Integrality and the zero-or-one slack property are
inherited.
where is obtained by fixing one variable of a complete quadratic sign function. Its
quadratic part remains complete on variables. It is still nonseparable across every
nontrivial partition, so the local one-dimensional-face lemma remains applicable.
The surviving maximal-clique coefficients are nonzero exactly on the even-parity choice
vectors. Indeed, for a choice vector on the remaining parts,
The even-parity vectors are connected by moves flipping two bits. Two corresponding
maximal cliques share vertices, so their common edge coefficients again synchronize all
local scales. Every edge is contained in an even-parity maximal clique. The same
extremality and dimension proof therefore works for the restricted function and its
complement.
9.3.3. Symmetry and difference bodies.
Reflecting a generalized permutahedron complements all conditioning bits in
its elemental slacks. In the representation above, complementing both bits of a
remaining part sends to and leaves unchanged. It consequently multiplies by
.
For even , the reflected polytope has the same elemental slacks as the original. Their set
functions differ only by a modular function, so they are translates; this is central
symmetry. The same applies to the complementary summand. For odd , reflection instead
exchanges and . Thus the complement is a translate of the reflection, and is a translate of
. The center of is , so in the odd case the identity can be written explicitly as
Finally, every clique of an -partite graph uses at most one vertex from each part, so is
-free. This completes the proof of Theorem 9.8.
Corollary 9.10 (One singleton part).For every , the unscaled graphical zonotope
of , with parts, has a lattice summand of dimension such that both it and its
complement are indecomposable and have the entire graph as their actual direction
graph.
Proof.Deleting a vertex preserves integrality and the Boolean slack property, but
may remove equations needed for extremality. We first fix a common scale on edges
at the singleton. For every other edge, the two values of the singleton bit then give
two distinct one-dimensional spaces for the same residual slack, forcing it to vanish.
Restrict the function of Theorem 9.8 by retaining only in the first part. Integrality
and Boolean slacks are inherited. For every edge incident to , the slack still has the
form (9.4) on doubled parts. Hence its tight equations force one scale. The nonzero
maximal-clique coefficients synchronize these scales, and their choices form a cube
for even and the even-parity cube, connected by two-bit flips, for odd . Adjacent
choices share an edge at , and every edge at lies in such a clique.
Subtract this common multiple from a vector in the tight kernel. All its coefficients
containing now vanish. For an edge avoiding , its residual slack is therefore
independent of and belongs to , where . Put ; the missing vertex has spin one. The
two original slack slices are
Both phases have complete quadratic part on the remaining variables. Moreover,
so and are distinct. The residual vanishes on the zero set of each slice. Lemma 9.9
puts it in . Thus the complete tight kernel is one-dimensional. Replacing every
phase by its negative proves the same assertion for the complement. Every slice
is nonconstant, so every edge occurs in both summands. The cone criterion and
connectedness finish the proof. □
Corollary 9.11 (The four-part cases).For every , the unweighted graphical
zonotope of is the sum of two full-dimensional indecomposable lattice polytopes
with Boolean elemental slacks. Consequently such a decomposition exists in every
dimension at least three.
Proof.The preceding results cover three or four doubled parts. With two, let be
the singleton vertices. Restrict by retaining their zero-labelled vertices. Its slack
belongs to and fixes one scale by Lemma 9.9. Subtract that scale from a vector in
the tight kernel. Its coefficients containing vanish. For an edge from either singleton
to a doubled part, the residual slack is independent of the other singleton. The two
slices belong to distinct Boolean-face lines in , as in the preceding proof, so the
residual is zero. The remaining edge slacks are constant; their original slacks have a
nonconstant quadratic phase on , so a tight zero kills each constant. The argument
applies equally to the complement.
For the two smaller graphs, write vertex names also for their Boolean variables
and use
on . Its complement is the persimmon block of Section 5.3.1, after relabelling.
The edge slacks of , up to interchanging or , are
Their empty-context zeros kill every pair coefficient except . The zeros on and
with present kill and . Finally the zero with present, and the zeros with both
remaining vertices present, leave the line
On , with singleton vertices and doubled part , take
Its restriction to is . After subtracting the scale fixed there, a vector in the tight
kernel has the form
The relevant original slacks are
The zeros at give . The zero with gives , and the zero with then gives . The
and zeros give . For the complement, the contexts where give and . Taking in
gives , and taking in gives . Both tight kernels are therefore lines.
The larger cases inherit integrality and Boolean slacks from . For these properties
follow directly from its coefficients. For , besides the displayed slacks and their images
under , the remaining ones are
All edge slacks in these cases are nonconstant and Boolean, so both summands
have the entire graph as their direction graph. These give dimensions three through
seven; larger dimensions follow from Theorem 9.8 and Corollary 9.10. □
9.4. The least dilation in the -free case.
Corollary 9.11 completes Theorem 9.5; every permitted part-size pattern occurs, with
both complementary summands indecomposable. The same classification separates dilation
one from dilation two in all dimensions.
Corollary 9.12.For every , the smallest real dilation factor for which some
-free graphical zonotope on vertices has a full-dimensional lattice indecomposable
summand is one when , and two when .
Proof.If such a summand satisfied with , all its elementary differences would be
integers in , hence zero or one. Then would be supermodular, making an actual
summand of . Theorem 9.5 rules this out for . The path-cube family supplies equality
with dilation two. For , Corollary 9.11 supplies dilation one. A smaller factor is
impossible, since a non-point lattice generalized permutahedron has a positive integer
elementary difference. □
Appendix A. A graphic model of the path family
The two types of monomials in count free intervals in a path of linear constraints,
realizing as a projection of a graphic matroid base polytope over every field. The same
graph gives a tridiagonal determinant with Newton polytope , whose indecomposability
then controls factorization.
Proposition A.1 (A graphic -polymatroid model).Put . Over any field , let be
the standard basis of , with outside , and set
Then, for every ,
In particular, the same integer rank function is represented over every field, , and
More precisely, the representation is a grouping of the columns of a reduced
incidence matrix of a graph. Thus is the image of a spanning-tree polytope under
summing edge coordinates within the groups.
Proof.Write , and identify the dual of with coordinates , extended by zero outside
. The annihilator of is defined by
The equality constraints join coordinates along a path with fixed zero endpoints .
Each component disjoint from these endpoints and from all marked zero coordinates
contributes one free parameter.
Such a free component is an interval . Its boundary constraints require , its
internal edges require , and the absence of marked zeros requires . If , the last two
requirements conflict, so a free component has one or two coordinates. A singleton
contributes precisely when , and a pair contributes precisely when and . Writing ,
the annihilator dimension is therefore
This proves the rank formula in every characteristic. The upper rank inequalities
and the defining lower inequalities of are equivalent after imposing . Nonnegativity
follows also from .
For the graphic description, take vertices , all spokes , all path edges , and one
additional parallel copy of each endpoint spoke and . Delete the row for vertex
from an oriented incidence matrix. Its nonzero columns, grouped as , are exactly
the vectors above. There are edges, in groups of at most two. This is a totally
unimodular incidence representation; its matroid is graphic and regular. Grouping
edge coordinates in the matroid base polytope gives the rank function . Greedy
basis extension along any ordering of the groups realizes every greedy vertex of the
polymatroid base, proving the asserted equality of polytopes. □
Proposition A.2 (Stability and absolute irreducibility).Let be the determinant
of the by tridiagonal matrix whose th diagonal entry is and whose and entries
are . Over , its Newton polytope is , and it is a homogeneous real stable polynomial
of degree . Moreover, for every field , the polynomial is absolutely irreducible over .
Proof.Let be the incidence matrix just constructed. Give every edge in group
weight . The displayed tridiagonal matrix is
Cauchy–Binet expresses its determinant as
since the nonzero maximal incidence minors are and correspond exactly to
spanning trees. Over , the coefficients count trees and are positive on their support.
Proposition A.1 therefore gives .
If every has positive imaginary part, then for every nonzero complex vector ,
because the columns span . Hence is nonsingular, proving real stability.
Homogeneity and degree are immediate from the determinant or the spanning-tree
formula.
Absolute irreducibility has a short characteristic-independent proof. Set and .
Expansion along the first row gives, for ,
where . Over any field, induction makes irreducible. It is not associate to ; for
this follows from its displayed linear form, and for it follows from its degree. Also
. Thus . The polynomial is primitive and linear in , so Gauss’s lemma proves it
irreducible. Applying the same argument over an algebraic closure proves absolute
irreducibility. □
The Newton-polytope assertion is made in characteristic zero. Coefficients can
disappear after reduction. For example,
has coefficient two on . The subspace representation, its rank function, and the absolute
irreducibility assertion remain valid over every field.
Corollary A.3 (Every polynomial with this Newton polytope).Over any field ,
every polynomial whose Newton polytope is exactly is absolutely irreducible.
Proof.Work over an algebraic closure and suppose with both factors nonzero. The
Newton polytope of a product is the Minkowski sum of the Newton polytopes;
maximizing any linear weight reduces this assertion to the nonvanishing product of
the two initial forms. Indecomposability of therefore makes the two factor polytopes
translates of and , with .
The displayed slack-one contexts in the main construction give a primitive lattice
edge of . If , the corresponding edge of the lattice polytope has vector , forcing to
be an integer. Hence one factor has point Newton polytope and is a monomial. The
minimum of each coordinate on is , so no variable divides . That monomial factor
is constant, proving the assertion. □
Appendix B. Optimal lattice dilation on path joins
The path-cube family attains a uniform dilation factor two, whereas for the path joins the
least factor grows as . An endpoint correction to the complementary summand attains the
lower bound of Corollary 9.4.
Let , with hubs and path vertices , where . For the path edge , put when is odd and
when is even. Define
Put and define
The three correction terms change only coefficients on . The hub difference of the
uncorrected complement counts selected path blocks with a negative sign. Removing the
contribution of the first block makes its largest possible count , exactly the dilation forced
by the lower bound. The endpoint terms make this change while keeping all nonhub
differences Boolean. We have . Write .
Theorem B.1.The polytope is integral, indecomposable, and has dimension . Its
actual direction graph is , and
Thus it attains the optimal lattice dilation in Corollary 9.4.
B.1. The elemental differences.
The hub difference of counts the nonempty selected path blocks. The endpoint
correction subtracts the block containing , if present. Thus, with ,
The sum counts transitions in a binary word. Their pairs of positions are
disjoint, so there are at most ; both zero and occur. Hence the difference lies in
.
The nonhub differences of are Boolean. On a path edge they are , where
is the other hub. For a path vertex , let and be its path neighbors on edges
labelled respectively and . Alternation makes both sets have size at most one, and
The formula for interchanges the hubs. Thus every nonhub edge other than has . The
remaining two differences are
Nonedge differences vanish by clique support. All coefficients are integral, and
Lemma 2.1 gives the asserted integral complement.
B.2. One scale along the path.
For a vector satisfying the tight equations of , write its coefficients as
On path edge , denote by the triangle coordinate that is negative in the
construction, and by the other one. Thus for odd , with the order reversed for even
.
The tight left-end rows give
Explicitly, use the rows with contexts , the row with context , and the row with
context . These start the propagation without any assumption about an edge to the left of
the path. For , let be the spoke coordinate at the hub of and the other spoke coordinate.
Tight spoke rows give
The first two use just the other hub as context. The next two are the rows on the
spoke conditioned on , first without and then with the other hub. For , the remaining
needed rows are
These are respectively the spoke row conditioned on , the spoke row conditioned on
both adjacent path vertices, and the path-edge row conditioned on . The complement and
endpoint formulas show that all these rows are tight at .
Put for . The left and right triangle equations give where both occur. Thus all equal
one scalar , and
The hub-edge equality conditioned on then gives . All coefficients are consequently
times their prescribed values. The elimination has unit pivots and one free coordinate, also
for , when no internal rows occur. Since , the tight equations cut out precisely the ray of .
Lemma 2.1 proves indecomposability.
Every edge except has positive empty-context difference; for use . Hence the direction
graph is and the dimension is . The graph is a planar -tree; starting from , successively
attach to .
References
[1]
G. Poullot,
Deformation
cones
of
graphical
zonotopes
for
-free
graphs,arXiv
2404.02669v5,
23 October 2025.