Lower bounds for cube-ideal set-systems

Ahmad Abdi; Daniel Dadush; G\'erard Cornu\'ejols; Mahsa Dalirrooyfard

arxiv: 2505.14497 · v2 · submitted 2025-05-20 · 🧮 math.CO · math.OC

Lower bounds for cube-ideal set-systems

Ahmad Abdi , G\'erard Cornu\'ejols , Daniel Dadush , Mahsa Dalirrooyfard This is my paper

Pith reviewed 2026-05-22 13:58 UTC · model grok-4.3

classification 🧮 math.CO math.OC

keywords cube-ideal set-systemslower boundsVC-dimensioncombinatorial optimizationideal cluttersLovász-Plummer conjecturepolyhedral combinatorics

0 comments

The pith

Cube-ideal set-systems must have exponential size and linear VC-dimension.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that cube-ideal set-systems on n elements have size at least exponential in n. It also proves that their VC-dimension is at least linear in n. These lower bounds are derived using combinatorics, convex geometry, and polyhedral theory. The results have applications to strong orientations, perfect matchings, dijoins, and ideal clutters, including the Lovász-Plummer conjecture.

Core claim

A set-system Ssubseteq {0,1}^n is cube-ideal when its convex hull is exactly described by capacity and generalized set covering inequalities. The central claim is that every such set-system has cardinality exponential in n and VC-dimension linear in n. The proofs integrate combinatorial arguments with geometric and polyhedral methods to establish these bounds and apply them to problems in graph theory and combinatorial optimization.

What carries the argument

The cube-ideal set-system, defined by the property that its convex hull equals the polyhedron defined by capacity inequalities and generalized set covering inequalities.

If this is right

Any cube-ideal set-system is at least exponentially large in the number of elements.
The VC-dimension of cube-ideal set-systems grows linearly with n.
These size bounds imply new restrictions on the structure of ideal clutters and related objects in combinatorial optimization.
Applications include lower bounds relevant to the Lovász-Plummer conjecture on perfect matchings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar lower bounds might hold for other polyhedrally defined families of set-systems.
Computational checks for small values of n could help determine the precise constants in the exponential growth.
These techniques from convex geometry could be applied to bound dimensions in related combinatorial structures.

Load-bearing premise

The convex hull of the set-system is exactly described by capacity and generalized set covering inequalities.

What would settle it

A cube-ideal set-system with size smaller than exponential in n or with VC-dimension smaller than linear in n would falsify the lower bounds.

read the original abstract

A set-system $S\subseteq \{0,1\}^n$ is cube-ideal if its convex hull can be described by capacity and generalized set covering inequalities. In this paper, we use combinatorics, convex geometry, and polyhedral theory to give exponential lower bounds on the size of cube-ideal set-systems, and linear lower bounds on their VC dimension. We then provide applications to graph theory and combinatorial optimization, specifically to strong orientations, perfect matchings, dijoins, and ideal clutters, including the Lov\'{a}sz-Plummer conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives exponential lower bounds on the size of cube-ideal set-systems and linear VC-dimension bounds, derived from their polyhedral definition, with applications to ideal clutters.

read the letter

The main thing here is that cube-ideal set-systems must have exponential size and at least linear VC-dimension. The authors start from the definition that the convex hull equals the polytope cut out by capacity inequalities plus generalized set-covering inequalities, then use combinatorial enumeration and convex-geometry arguments to force many vertices or high shattering number. They carry the same description over to applications on strong orientations, perfect matchings, dijoins, and ideal clutters, including a link to the Lovász-Plummer conjecture. That connection is the clearest payoff. What the paper does well is turn a polyhedral assumption into explicit quantitative lower bounds without extra parameters or fitting. The citation pattern stays inside the relevant clutter and polyhedral literature, which keeps the claims grounded. The soft spots are limited. The central assumption is definitional, so it holds by construction, but the bounds could be loose if many natural set-systems fall outside the cube-ideal class. Without the full derivations in front of me it is hard to judge how tight the volume or vertex-count steps actually are, though the high-level structure shows no internal contradiction. This is for specialists in polyhedral combinatorics and combinatorial optimization who already follow work on ideal clutters. A reader interested in concrete lower bounds or in the Lovász-Plummer conjecture will find usable statements. The paper has enough specific claims and standard methods applied in a new setting to deserve a serious referee, even if the proofs need polishing for clarity. I would send it out for peer review.

Referee Report

0 major / 4 minor

Summary. The paper defines a set-system S ⊆ {0,1}^n as cube-ideal if its convex hull equals the polytope cut out by capacity inequalities together with generalized set covering inequalities. It establishes exponential lower bounds on |S| and linear lower bounds on the VC-dimension of S via combinatorial enumeration, convex-geometric volume/vertex arguments, and polyhedral integrality. These bounds are then applied to strong orientations, perfect matchings, dijoins, ideal clutters, and the Lovász-Plummer conjecture.

Significance. If the central claims hold, the work supplies concrete structural constraints on a class of polytopes arising in ideal clutters and related combinatorial objects. The explicit applications to the Lovász-Plummer conjecture and to integrality questions in matching and orientation problems constitute a clear contribution to polyhedral combinatorics. The multi-tool approach (combinatorics + geometry + polyhedral theory) and the direct use of the defining inequalities to derive the bounds are strengths.

minor comments (4)

The abstract states that the convex hull 'can be described by' the listed inequalities; the body should explicitly confirm that the description is exact (i.e., the inequalities suffice to cut out conv(S)) rather than merely sufficient.
In the statement of the main lower-bound theorem, the dependence on n should be made fully explicit (e.g., |S| ≥ c·2^{αn} for concrete constants c, α) so that the exponential character is immediately verifiable.
The applications section would benefit from a short paragraph summarizing how the new VC-dimension bound translates into a concrete statement about the Lovász-Plummer conjecture.
A few sentences clarifying the relationship between cube-ideal set-systems and the more familiar notion of ideal clutters would help readers outside the immediate sub-area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, including the summary of our results on exponential lower bounds for cube-ideal set-systems and linear VC-dimension bounds, as well as the applications to ideal clutters and the Lovász-Plummer conjecture. We appreciate the recommendation for minor revision and will incorporate any suggested improvements in the revised version.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper defines cube-ideal set-systems via the property that their convex hull is exactly described by capacity and generalized set covering inequalities. It then applies combinatorial enumeration, volume/vertex arguments from convex geometry, and polyhedral integrality to derive exponential lower bounds on size and linear lower bounds on VC-dimension. These steps use the definition directly as a constraint on admissible polytopes rather than fitting parameters or renaming results. No equations, predictions, or self-citations are shown that reduce the central claims to inputs by construction. The applications to ideal clutters and the Lovász-Plummer conjecture follow from the same polyhedral description without load-bearing circular reductions. The derivation is self-contained against external combinatorial and geometric benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definitions of convex hulls, VC-dimension, and ideal clutters from prior polyhedral combinatorics literature; no free parameters or new invented entities are introduced in the abstract.

axioms (1)

domain assumption Convex hull of a 0-1 set-system can be described by capacity and generalized set covering inequalities precisely when the system is cube-ideal.
This is the central definition used to derive all subsequent bounds.

pith-pipeline@v0.9.0 · 5626 in / 1016 out tokens · 33139 ms · 2026-05-22T13:58:10.296455+00:00 · methodology

Lower bounds for cube-ideal set-systems

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)