Representatives of Box-Closure Systems on Downsets of Products of Chains

1 Introduction

Closure systems generated by local inference rules arise naturally in combinatorics, order theory, database theory, and phylogenetics. This paper studies a simple but structured closure system on finite downsets of products of chains. The basic rule is a coordinate-mixture rule: if two lower elements lie below a common upper element, then all coordinatewise mixtures of the two lower elements also lie below the same upper element.

The construction is motivated by restricted cross-consistency rules that appear in LCA-like constraint systems, but the object studied here is not the full LCA $(+)$-closure. This distinction is essential. In the full LCA setting one works with all unordered pairs of leaves, possible non-uniqueness or non-existence of LCAs in directed acyclic graphs, same-side pairs, non-designated cross-pairs, and additional interactions. The projection of a full LCA $(+)$-closure to a designated subsystem need not coincide with the box-closure of that projected subsystem. In this paper, box-closure is treated as an autonomous combinatorial closure operator.

Let

be a finite downset. For each $x\in D$, introduce a symbol $p_x$. The target relation is the product order

A representative is a subset $T\subseteq R_D$ whose box-closure is all of $R_D$. The central question is: which subsets $T$ represent $R_D$, and how small can such a representative be?

We solve this problem completely. If $y\in D$ lies on a coordinate axis, then the immediate predecessor relation into $y$ is forced. If $y$ has at least two active coordinates, then any one incoming relation

is sufficient. Thus the representative problem decomposes over upper endpoints.

The main consequences are:

• \[ \min\{|T|:T^\Box=R_D\}=|D|-1; \]

• every inclusion-minimal representative is cardinality-minimal;

• after removing the fixed forced axis generators, the minimum representatives are bases of a partition matroid;

• the number of representatives, the number of minimum representatives, and the size enumerator of all representatives have closed product formulae;

• the weighted representative problem decomposes independently over upper endpoints;

• for full boxes, the product order has exponentially larger strict relation set than its minimum box-closure representative.

• in dimension two, projected LCA-closures on designated Ferrers cross-pairs give an explicit LCA-motivated realization with exact jump-length enumerators and cover-contained counts.

The two-dimensional case $D\subseteq [m]\times[n]$ recovers a restricted Ferrers LCA-like system on designated cross-pairs $a_i b_j$. We discuss that connection near the end as motivation, not as the main theorem.

2 Downsets in products of chains

Let

with its usual order. Fix positive integers $n_1,\dots,n_d$, and write

We order $\mathbf n$ coordinatewise:

A subset

is a downset if

Throughout, $D$ is a nonempty finite downset. Hence $D$ contains the bottom element

For $y=(y_1,\dots,y_d)\in D$, define its active support by

Then

A non-minimal element $y\ne\hat{0}$ is called an axis element if

If $y$ is an axis element, then it has a unique lower cover, denoted

Explicitly, if $t$ is the unique active coordinate, then

An element $y\in D$ is called multi-coordinate if

For $y\in D$, write

and

3 Box-closure systems

For each $x\in D$, introduce a formal symbol $p_x$. Let

The target relation is the product order on these symbols:

Its strict part is

A generating set will always mean a subset

Reflexive relations are built into the closure and are not counted as generators.

Definition 3.1 (Box-closure).

For $T\subseteq R_D^{<}$, the box-closure $T^\Box$ is the smallest relation on $P_D$ containing $T$ and satisfying the following rules.

(B0) Reflexivity. For every $x\in D$,

\[ p_x\preceq p_x. \]

(B1) Transitivity. If

\[ p_x\preceq p_y \quad\text{and}\quad p_y\preceq p_z, \]

then

\[ p_x\preceq p_z. \]

(B2) Box rule. If

\[ p_x\preceq p_z \quad\text{and}\quad p_y\preceq p_z, \]

then for every coordinatewise mixture $w$ of $x$ and $y$, meaning

\[ w_t\in\{x_t,y_t\} \qquad(t=1,\dots,d), \]

with $w\in D$, we add

\[ p_w\preceq p_z. \]

The box rule preserves the upper endpoint $z$.

Definition 3.2 (Representatives).

A subset $T\subseteq R_D^{<}$ is a representative of $R_D$ if

\[ T^\Box=R_D. \]

The main problem is to characterize all representatives.

Lemma 3.3 (The product order is box-closed).

The relation $R_D$ is closed under the box-closure rules.

4 Endpoint preservation

The first structural observation is that non-reflexive relations cannot be generated without a generator having the same upper endpoint.

Lemma 4.1 (Endpoint preservation).

Let $T\subseteq R_D^{<}$. Suppose

\[ p_x\preceq p_y\in T^\Box \]

with $x<y$. Then $T$ contains at least one generator of the form

\[ p_u\preceq p_y \]

with $u<y$.

Corollary 4.2.

If $T^\Box=R_D$, then for every $y\ne\hat{0}$, the set $T$ contains at least one generator with upper endpoint $y$.

Lemma 4.3 (Axis covers are forced).

Let $y$ be an axis element. If

\[ p_{y^-}\preceq p_y\in T^\Box, \]

then

\[ p_{y^-}\preceq p_y\in T. \]

5 Complete representative theorem

We now prove the main classification.

Theorem 5.1 (Complete representative classification).

Let $T\subseteq R_D^{<}$. Then

\[ T^\Box=R_D \]

if and only if the following two conditions hold:

1. for every axis element $y\ne\hat{0}$,

   \[ p_{y^-}\preceq p_y\in T; \]

2. for every multi-coordinate element $y$, there exists at least one $x\in D_{<y}$ such that

   \[ p_x\preceq p_y\in T. \]

Thus axis elements have forced incoming cover generators, while each multi-coordinate element requires at least one incoming generator from its strict lower ideal.

6 Minimum and inclusion-minimal representatives

The complete representative theorem immediately identifies all minimal representatives.

Theorem 6.1 (Inclusion-minimal equals cardinality-minimal).

Let $T\subseteq R_D^{<}$ be a representative. Then $T$ is inclusion-minimal if and only if:

1. for every axis element $y\ne\hat{0}$, $T$ contains the forced generator

   \[ p_{y^-}\preceq p_y; \]

2. for every multi-coordinate element $y$, $T$ contains exactly one generator

   \[ p_x\preceq p_y \]

   with $x<y$.

Consequently, every inclusion-minimal representative has cardinality

\[ |D|-1. \]

In particular,

\[ \min\{|T|:T^\Box=R_D\}=|D|-1. \]

7 Partition matroid structure

Let

be the set of forced axis generators.

For every multi-coordinate element $y$, define

Then Theorem 6.1 says that every inclusion-minimal representative is exactly

Theorem 7.1 (Partition matroid theorem).

After removing the fixed forced set $F_{\mathrm{ax}}$, the variable parts of the inclusion-minimal representatives are precisely the bases of the partition matroid

\[ \mathcal M_D= \bigoplus_{\substack{y\in D\\ |\operatorname{supp}(y)|\ge2}} U_{1,E_y}, \]

where $U_{1,E_y}$ is the rank-one uniform matroid on $E_y$.

Remark 7.2.

Equivalently, one may build a matroid on the full generating set by adding the elements of $F_{\mathrm{ax}}$ as fixed coloops and taking the direct sum with $\mathcal M_D$. We avoid this extra formalism and simply remove the fixed forced set.

8 Enumerators and compression

The preceding results yield exact enumeration formulae and optimal compression ratios.

8.1 Inclusion-minimal representatives

The number of inclusion-minimal representatives is

Indeed, for each multi-coordinate $y$, one chooses an arbitrary parent $x\in D_{<y}$. Axis generators are forced.

For a full box

we have

Therefore

8.2 Hasse-supported minimum representatives

A representative is Hasse-supported if all its generators are cover relations.

For a multi-coordinate element $y$, the number of lower covers is

Therefore the number of Hasse-supported minimum representatives is

For a full box,

In dimension $2$, this specializes to

8.3 All representatives

Theorem 5.1 also counts all representatives.

For an axis element $y$, the forced generator

must be included, while any other incoming generator from

may be included or omitted. Thus the number of choices in that endpoint fiber is

For a multi-coordinate element $y$, any nonempty subset of $D_{<y}$ may be chosen as the set of incoming generators. Thus the number of choices in that endpoint fiber is

Therefore the total number of representatives is

The ordinary generating function by cardinality is

The coefficient of $t^k$ is the number of representatives of size $k$.

8.4 Optimal compression of the product order

The strict product-order relation has size

The minimum representative has size

Thus the optimal strict-order compression ratio is

For a full box

we have

and

Hence

while

For the cube $D=[n]^d$,

As $n\to\infty$,

Thus box-closure gives an optimal representative that is polynomially smaller, by a factor of order $n^d$, than the full strict product order in fixed dimension $d$.

9 Weighted optimization and random minimum representatives

Let a weight

be assigned to every strict relation

9.1 Minimum-weight inclusion-minimal representatives

Among inclusion-minimal representatives, the minimum weight is

The axis terms are forced, and each multi-coordinate endpoint fiber independently chooses one minimum-weight incoming generator.

9.2 Minimum-weight representatives with nonnegative weights

If all weights are nonnegative, then every minimum-weight representative may be chosen inclusion-minimal. Hence the same formula gives the minimum weight among all representatives.

9.3 Arbitrary real weights

If negative weights are allowed, extra generators may reduce the total weight. The problem still decomposes by upper endpoint.

For an axis element $y$, the forced generator $p_{y^-}\preceq p_y$ must be included, and any additional negative-weight incoming generator should be included. The optimal axis contribution is

For a multi-coordinate element $y$, one must choose a nonempty subset of $D_{<y}$. The optimal contribution is

Equivalently, include all negative-weight incoming generators; if there are no negative-weight incoming generators, include one generator of minimum weight.

Thus the arbitrary-weight representative problem decomposes into independent endpoint-fiber optimizations.

9.4 Random minimum representatives

A uniformly random inclusion-minimal representative is sampled as follows:

1. include every forced axis generator;

2. for each multi-coordinate element $y$, choose one parent $x\in D_{<y}$ uniformly and independently.

Thus the probability that a generator $p_x\preceq p_y$ appears in a uniformly random minimum representative is

The entropy of the uniform distribution on minimum representatives is

9.5 Minimum-representative polytope and Boltzmann sampling

The endpoint factorization gives a polyhedral form of the minimum-representative space.

For $y\in D\setminus\{\hat{0}\}$, define the admissible parent set

Let

Minimum representatives are exactly the sets

Therefore the convex hull of incidence vectors of minimum representatives is

Equivalently,

This is the base polytope of the partition matroid from Theorem 7.1, with singleton blocks for the forced axis endpoints.

For an additive energy $w$, the partition function over minimum representatives is

Thus exact Boltzmann sampling is obtained by choosing each parent independently with probability

Uniform sampling is the case $\beta=0$.

10 The two-dimensional projected LCA case

The box-closure system was motivated by a restricted cross-consistency rule for designated LCA-like pairs. We now describe this connection in dimension $2$ in a more explicit form.

10.1 Ferrers pair systems and projected closure

Let

be a Ferrers downset. Introduce leaf labels $a_i$ for represented rows and $b_j$ for represented columns, and write

The designated universe is

We define the projected LCA closure $+_D$ on relations in $P_D\times P_D$ by reflexivity, transitivity, and the following restricted cross-consistency rule. If

then, whenever the displayed pair symbols belong to $P_D$, one obtains

This is exactly the two-dimensional box rule for the coordinate pairs $(i,\ell)$ and $(r,j)$ with common upper endpoint $(k,m)$.

This projected closure is not the full LCA $(+)$-closure on all pairs of leaves. It ignores same-side pairs $a_i a_{i'}$, $b_j b_{j'}$, singleton symbols, non-designated cross-pairs, and other interactions present in the full LCA universe. Moreover, the projection of a full LCA $(+)$-closure to the designated universe need not coincide with the box-closure of the designated subsystem.

10.2 A rooted DAG realizing the designated product order

For completeness, we recall a realization of the designated product order by a rooted DAG.

Proposition 10.1 (Ferrers grids are realized by rooted DAGs).

For every finite Ferrers downset $D$, there is a rooted DAG $N_D$ with leaf set containing the labels $a_i,b_j$ and internal vertices $v_{ij}$, $(i,j)\in D$, such that

\[ \operatorname{lca}_{N_D}(a_i,b_j)=v_{ij} \]

for every $(i,j)\in D$, and

\[ v_{ij}\preceq v_{k\ell} \quad\Longleftrightarrow\quad i\le k,\ j\le \ell. \]

Equivalently, the LCA order of $N_D$, restricted to the designated pair set $P_D$, is the product order on $D$.

This statement is only about designated cross-pairs. The full LCA relation of the DAG may contain additional comparisons involving other pairs of leaves. If one wants the DAG to satisfy a particular convention for phylogenetic networks, degree-$(1,1)$ vertices may be suppressed or the construction may be modified in the standard way. The representative theorems above do not depend on these network conventions.

10.3 Projected closure equals the product order

Let $H_D$ be the Hasse-cover relation of the product order on $D$:

Here $x\lessdot y$ means that $x$ is an immediate predecessor of $y$ in the product order.

Theorem 10.2 (Projected Ferrers closure).

For every finite Ferrers downset $D$,

\[ H_D^{+_D} = \{p_{ij}\preceq p_{k\ell}:(i,j),(k,\ell)\in D,\ i\le k,\ j\le \ell\}. \]

Equivalently, the projected closure of the Hasse-cover relation is exactly the product order.

10.4 Minimum representatives in Ferrers grids

The two-dimensional representative results are immediate specializations of the general theory, but it is useful to spell them out in LCA notation.

The axis elements are the first row and first column. Their immediate predecessor generators are forced. Every interior cell $(i,j)$, $i,j>1$, requires exactly one incoming generator from its strict lower rectangle

Thus

Every minimum representative is determined by an admissible parent map

such that

and, for $i,j>1$,

The representative is

Consequently,

For a rectangle $D=[m]\times[n]$, this becomes

For the square $D=[s]\times[s]$,

10.5 Cover-contained representatives

A minimum representative is cover-contained if it is a subset of the Hasse-cover relation $H_D$.

The cover-contained minimum representatives are exactly the parent maps for which each interior cell chooses one of its two Hasse parents:

Therefore

where

For $D=[m]\times[n]$, this is

The Hasse-cover presentation itself has exact redundancy

Indeed, if $r$ is the number of nonempty rows and $c$ the number of nonempty columns, then the number of vertical covers is $|D|-c$ and the number of horizontal covers is $|D|-r$. Hence

and

For $D=[s]\times[s]$, the probability that a uniformly random minimum representative is cover-contained is

Its logarithm is

Thus local, cover-contained representatives form an asymptotically negligible subfamily of all minimum representatives.

10.6 Jump-length enumerator

The classification also yields an exact enumerator by locality. For a parent choice

define its jump length as

For a minimum representative $T_\pi$, define its total jump length by

Let

be the number of non-minimum boundary cells.

Theorem 10.3 (Jump-length generating function).

The generating function

\[ F_D(q)=\sum_{T\text{ minimum}}q^{\Lambda(T)} \]

is

\[ F_D(q) = q^{b(D)} \prod_{\substack{(i,j)\in D\\ i>1,\ j>1}} \left( \sum_{\substack{0\le a\le i-1\\ 0\le b\le j-1\\ (a,b)\ne(0,0)}} q^{a+b} \right). \]

Equivalently,

\[ F_D(q) = q^{b(D)} \prod_{\substack{(i,j)\in D\\ i>1,\ j>1}} \left( \frac{(1-q^i)(1-q^j)}{(1-q)^2}-1 \right), \]

where the second expression is interpreted as the corresponding polynomial.

Setting $q=1$ recovers the product formula for the number of minimum representatives.

For a uniformly random minimum representative $T$,

For $D=[s]\times[s]$, this is

Thus a uniformly random minimum representative has only $O(s+(\log s)^2)$ cover edges out of $s^2-1$ total generators.

Similarly,

For $D=[s]\times[s]$,

10.7 Small rectangles

For $D=[2]\times[3]$, there are six designated pairs and the minimum representative size is $5$. Boundary parents are forced:

The interior cells are $(2,2)$ and $(2,3)$. They have respectively $3$ and $5$ possible parents, so the total number of minimum representatives is

The cover-contained subfamily has

members.

For $D=[3]\times[3]$, the minimum representative size is $8$. The four interior cells

have respectively

possible parents. Thus the total number of minimum representatives is

The cover-contained subfamily has size

11 Relationship with LCA constraints and triple representatives

The classical LCA-constraint problem concerns rooted trees and constraints comparing lowest common ancestors. Recent work extends LCA constraints to directed acyclic graphs and phylogenetic networks, where LCA existence and uniqueness become nontrivial and where closure operations involve the full universe of leaf pairs [ASSU81], [EH26], [HLM26], [LH25], [LAMSH25].

The present paper studies a different restricted closure system. Its relation to LCA theory is motivational and occurs explicitly in the two-dimensional designated cross-pair case. The main results should not be read as theorems about the full LCA $(+)$-closure.

Representative triple sets in rooted phylogenetic trees have a known matroidal structure. The box-closure systems studied here also yield a matroidal structure, but of a different and simpler kind: after removing the forced axis generators, the variable parts of the inclusion-minimal representatives form the bases of a partition matroid. This follows from endpoint-fiber decomposition, not from triple-closure theory.

12 Conclusion

We introduced box-closure systems on finite downsets of products of chains and solved their representative problem completely.

The main results are:

1. a complete characterization of all representatives;

2. the equivalence of inclusion-minimality and cardinality-minimality;

3. the minimum size formula $|D|-1$;

4. a partition-matroid description of the variable parts of minimum representatives after removing forced axis generators;

5. exact enumerators for minimum, Hasse-supported, and all representatives;

6. optimal compression ratios for product orders under box-closure;

7. a decomposed solution of the weighted representative problem;

8. a factorized model of random minimum representatives and a product-of-simplices description of their polytope;

9. recovery of the two-dimensional projected Ferrers LCA-like system as a special case, including exact jump-length enumerators and cover-contained counts.

The contribution is a complete combinatorial analysis of a coordinate-mixture closure system. Its connection to LCA constraints is motivational and restricted, not a claim about the full LCA $(+)$-closure.