Pith. sign in

REVIEW 5 minor 43 references

Ample sets in Cartesian products

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Ample sets generalize from hypercubes to Cartesian products while keeping their metric, commutative, and topological characterizations.

desk verdict Solid, theorem-heavy extension of classical ample/lopsided sets to Hamming products; the equivalences survive and the new examples are real. read the letter →

arxiv 2607.04014 v1 pith:5ERGFIJM submitted 2026-07-04 math.CO cs.DMmath.MG

Victor Chepoi , Matthew Maat This is my paper
classification math.COcs.DMmath.MG MSC 05C1252B0568Q32
keywords amplesetsCartesianproductsminor-subproductssuperisometricitylopsidedprismcomplexesmean-payoffgamesVC-dimension
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper lifts the classical theory of ample (or lopsided) sets from binary hypercubes to arbitrary finite Cartesian products. Ampleness is defined by a shattering-to-strong-shattering rule on minor-subproducts obtained by partitioning each factor and contracting blocks. The authors prove that this single combinatorial condition is equivalent to a long list of structural properties that already characterize the binary case: the complement is ample, every strong projection is isometric (superisometricity), projections and strong projections commute on minor-subproducts with disjoint supports, serial push-downs commute, and the intersection of the set with every interval is classically ample. They further obtain a decomposition of any ample set by successive ample amalgams of its maximal boxes, which implies that the associated prism complex is contractible. Concrete new examples arise from the winning-strategy sets of mean-payoff games, from the vertex sets of prism-like polyhedra, and from the vertex sets of quasi-median graphs. The same language of minor-subproducts also unifies several multiclass VC-dimensions that appear in learning theory.

What carries the argument

Minor-subproducts (products of partitions of the factors) together with the associated projection and strong-projection operators; the shattering-to-strong-shattering principle on this lattice is the single condition that forces all the metric, commutative and topological characterizations.

What would settle it

Exhibit a subset S of a product of three or more factors of size greater than two that is isometric and whose intersections with all intervals are classically ample, yet fails to contain a copy of some shattered extended minor-subproduct.

Watch

Extended reading notes

Core claim

A subset S of a Cartesian product U = U1 imes au au au imes Um is ample—every shattered minor-subproduct contains a combinatorial copy inside S—if and only if S is superisometric, if and only if projections and strong projections commute on minor-subproducts of disjoint supports, if and only if the complement is ample, and if and only if S ∩ [u,v] is classically ample for every pair of points of S.

Load-bearing premise

The definition of shattering and strong-shattering is taken with respect to the full lattice of minor-subproducts coming from arbitrary partitions of the factors; a coarser family would yield a strictly weaker notion.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper generalizes classical ample/lopsided sets from hypercubes to arbitrary finite Cartesian products U = U1 imes ⋅⋅⋅ imes Um. Using the lattice of generalized partitions and the associated minor-subproducts, it defines shattering and strong-shattering of a minor-subproduct M by a set S ⊆ U, and calls S ample when every shattered M has a copy inside S. The main results establish that this notion is equivalent to superisometricity of all strong projections SM, to commutativity of projections and strong projections on minor-subproducts with disjoint supports, to ampleness of the complement, and to classical ampleness of every intersection S ∩ [u, v] for u, v ∈ S (Theorems 2, 3, 9, 10). Further characterizations via push-downs, Euler characteristic, and AMP-amalgams are given, the prism complex of an ample set is shown to be contractible, and new examples arising from mean-payoff games, prism-like polyhedra and quasi-median graphs are supplied.

Significance. The work supplies a coherent, lattice-theoretic extension of a well-studied binary combinatorial structure to general Hamming graphs. The reduction of ampleness to classical ampleness on intervals (Theorem 10(7)) is especially useful: it immediately yields a polynomial-time recognition algorithm and unifies several previously separate notions of multiclass VC-dimension under a single geometric language. The decomposition theorem and the contractibility of the associated prism complexes give the first topological control on these objects beyond the binary case. Concrete examples from mean-payoff games and quasi-median graphs demonstrate that the definition is not vacuous. The manuscript is self-contained once the binary theory is granted, and the inductive arguments are written with care.

minor comments (5)
  1. [§6, Definition 14] Throughout the text the same symbol S^M is used both for the strong projection and, later, for the complement of a set; a typographic distinction (e.g., S^M versus S^*) would remove occasional local ambiguity.
  2. [§3.1] Figure 2 (Hasse diagram of GPart(U)) is dense; a short caption listing the atoms and co-atoms would help the reader navigate the lattice operations used in Lemmas 1 and 5.
  3. [§1, Figure 1] The running example of Figure 1 is reused effectively, but the concrete verification that the seven-point set is ample is left implicit; a one-sentence check that every shattered elementary minor has a copy would make the illustration self-contained.
  4. [§7.3, Theorem 10] In the statement of Theorem 10 the phrase “for all u, v ∈ U” in item (6) and “for all u, v ∈ S” in item (7) are shown equivalent only later; a forward reference would clarify the logical order.
  5. A few typographical slips remain (e.g., “Amplenness”, “superisometricity” inconsistently hyphenated, missing spaces after commas in several displayed equations). A final copy-edit pass would remove them.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: definitions of minor-subproducts and ampleness are introduced first; equivalences are derived by lattice induction and reduction to classical binary ampleness on intervals.

full rationale

The paper defines generalized partitions, minor-subproducts, shattering, strong-shattering, and ampleness (Definitions 4–12) before proving any equivalences. Theorems 1–3, 8–11 then establish that ampleness is equivalent to superisometricity, commutativity of projections/strong-projections on disjoint supports, complement ampleness, and classical ampleness of every S ∩ [u,v] (Theorem 10(7)). The proofs proceed by induction on |U|, lattice joins of atoms (Lemma 1), and elementary projections; they cite prior binary results only as base cases once the reduction to hypercube intervals is obtained. No parameters are fitted, no uniqueness theorem is imported as an external force, and no ansatz is smuggled via self-citation. The single mild self-reference is the use of the classical binary theory as the inductive base, which is independent of the new multi-factor statements. Score 1 reflects only that ordinary dependence on prior binary work.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

Pure combinatorial paper. Background is standard lattice theory of partitions, Hamming-graph geometry, and the classical binary ample/lopsided theory. No empirical free parameters. The only ‘invented’ objects are the minor-subproduct formalism and the resulting notion of ampleness for general products; both are definitional and immediately used to state theorems.

assumptions (4)
  • standard math Partition lattices Part(Ui) and their product GPart(U) are complete, atomistic, co-atomistic, and complemented (standard lattice theory).
    Used throughout Sections 2–3 to define minor-subproducts and supports.
  • standard math Intervals in Hamming graphs are hypercubes; convex sets are full-dimensional subproducts (boxes).
    Lemma 2 and subsequent interval characterizations.
  • domain assumption Classical binary ample sets satisfy the shattering→strong-shattering principle and the listed metric/commutative characterizations (Dress, Lawrence, Bandelt et al.).
    Base case for all inductive reductions to intervals [u,v].
  • domain assumption Mean-payoff games admit positional optimal strategies; the binary-degree case yields binary ample strategy sets (prior work of the second author).
    Used in Theorem 16 to lift to unrestricted out-degrees via interval ampleness.
invented entities (2)
  • Minor-subproduct M(Λ) of a Cartesian product (via generalized partitions)
    purpose: Provides the patterns that can be shattered or strongly shattered, generalizing coordinate subsets of hypercubes.
    Definitional; no independent physical existence claimed; falsifiable only by counter-examples to the stated equivalences.
  • Ample set of a general Cartesian product (MProd-ample) independent evidence
    purpose: Central object whose characterizations and topological properties are proved.
    Definitional extension of Dress/Lawrence; independent evidence consists of the new examples (games strategies, polyhedra, quasi-median graphs).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ample sets in Cartesian products." pith.science (2026). https://pith.science/paper/5ERGFIJM

@misc{pith2026260704014,
  author       = {Pith},
  title        = {Pith review of: Ample sets in Cartesian products},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5ERGFIJM}},
  note         = {Machine review of arXiv:2607.04014}
}
abstract

Ample sets of hypercubes, introduced by A. Dress in 1995, constitute a combinatorial structure with rich properties and important examples. Ample sets can be characterized in a multitude of combinatorial, graph-theoretical, recursive, and geometrical ways, and they are equivalent to lopsided sets introduced by J. Lawrence in 1983. In this paper, we define and investigate ample sets of Cartesian products $U=U_1\times\cdots\times U_m$. This is done using minor-subproducts of $U$, which correspond to products of partitions of factors: each minor-subproduct is obtained by partitioning each $U_i$ into blocks and contracting blocks into singletons. For a minor-subproduct $M$ and a set $S$, we define the notions of shattering of $M$ by $S$, of copy of $M$ in $S$, of projection $S_M$ of $S$ on $M$, and of strong-projection $S^M$ of $S$ on $M$. We call a set $S$ \emph{ample} if for any minor-subproduct $M$ that is shattered by $S$, there exists a copy of $M$ included in $S$. We prove that several characterizations of ample sets can be extended to ample sets of Cartesian products. In particular, we show that ampleness of $S$ is equivalent to the ampleness of the complement $S^*$, to superisometricity (isometricity of $S^M$ for any minor-subproduct $M$), and commutativity $(S^M)_{M'}=(S_{M'})^M$ for all minor-subproducts $M,M'$ with disjoint supports. We also provide more efficient characterizations of ampleness, in particular, by showing that $S$ is ample iff S is isometric and both $S_e$ and $S^e$ are ample for some elementary minor-subproduct, iff the intersection of S with any interval [u,v] with u,v in S is ample in the classical sense. We characterize ampleness by push downs and provide a decomposition theorem, allowing us to prove that their prism complexes are contractible. We provide new examples of ample sets arising from payoff games, prism-like polyhedra, and quasi-median graphs.

Figures

Figures reproduced from arXiv: 2607.04014 by the authors.

Figure 1
Figure 1. The Hamming graph corresponding to the Cartesian product {a, b, c} × {A, B} × {0, 1}. Coordinates are shown next to the graph for clar￾ity. The seven colored vertices induce an isometric subgraph. We will use this set as a running example. of shattering in binary products {a, b} X or in products Y X, used in various definitions of VC￾dimension, a subset S of a product always shatters a subset of coordinates Y ⊆ X. I… view at source ↗
Figure 2
Figure 2. for an example [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. A box partition (left) and its related minor-subproduct (right). Example 2. Consider again the Cartesian product {a, b, c} × {A, B} × {0, 1}, and take the generalized partition Λ = ({{a, b}, {c}}, {{A}, {B}}, {{0}, {1}}). This generalized partition in￾duces a box partition ( [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The set S in the figure shatters the minor-subproduct M = M(Λ, U), where Λ = ({{a, b}, {c}}, {A}, {B}, {{0, 1}}). This can be observed from the figure, since every box contains an element of S. The set S also strongly shatters M, since S contains a copy of M, namely {a…
Figure 5
Figure 5. Figure 5: The Cartesian product U = {a, b, c}×{A, B, C}, its Hamming graph, and the box-partition defined by M from Example 4. The set S is shown in blue. Example 5. The classical notion of ample/lopsided set [1, 30] corresponds to ample sets in binary products, i.e., in Cartesi…
Figure 6
Figure 6. Figure 6: Left: box partition related to the minor-subproduct M from [PITH_FULL_IMAGE:figures/full_fig_p024_6.png]
Figure 7
Figure 7. Figure 7: Top left: the boxes of f related to the square [s, t]. Top right: the boxes of e that correspond to the vertices of Q′ in case 3. Bottom: the boxes of e with elements of Q in case 4 (note: the fourth coordinate is not indicated, the vertices marked with + are those wit…
Figure 8
Figure 8. Figure 8: The set S ⊆ {a, b, c} × {A, B, C} (colored vertices) is an AMP￾amalgam of S1 and S2, where S1 = S +(C) and S2 = S c (C). A continuous map F : T × [0, 1] → T is a deformation retraction of a topological space T onto a subspace A if, for every x in T and a in A, F(x, 0) …
Figure 9
Figure 9. Figure 9: A mean payoff game, with circles representing Maximizer nodes and squares representing Minimizer nodes. All nonzero edge weights are shown on the edges. The set Σ for this game is the ample set from [PITH_FULL_IMAGE:figures/full_fig_p050_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 4 linked inside Pith

  1. [1]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, A. Dress, and J. Koolen. Combinatorics of lopsided sets.European J. Combin., 27(5):669–689, 2006

    2006

  2. [2]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, A. Dress, and J. Koolen. Geometry of ample/lopsided sets.arXiv preprint, 2603.27835, 2026

    arXiv 2026

  3. [3]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, and K. Knauer. COMs: Complexes of oriented matroids.J. Combin. Theory, Ser. A, 156:195–237, 2018

    2018

  4. [4]

    Bandelt, H

    H.-J. Bandelt, H. Mulder, and E. Wilkeit. Quasi-median graphs and algebras.J. Graph Theory, 18:681–703, 1994

    1994

  5. [5]

    Ben David, N

    S. Ben David, N. Cesabianchi, D. Haussler, and P. M. Long. Characterization of learnability for classes of{0, . . . , n}-valued functions.J. Comput. System Sci., 50:74–86, 1995

    1995

  6. [6]

    Björner.Handbook of Combinatorics, vol

    A. Björner.Handbook of Combinatorics, vol. 1,2, chapter Topological Methods, pages 1819–

  7. [7]

    Björner, M

    A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler.Oriented Matroids, volume 46. Cambridge University Press, 1993

    1993

  8. [8]

    DefectSauerresults.J

    B.BollobàsandA.Radcliffe. DefectSauerresults.J. Combin. Theory, Ser. A,72:189—-208, 1995

    1995

Show all 43 references
  1. [9]

    Brukhim, D

    N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff. A characterization of multiclass learnability. InFOCS, pages 943–955. IEEE, 2022

    2022

  2. [10]

    Chalopin, V

    J. Chalopin, V. Chepoi, S. Moran, and M. K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes.J. Comput. System Sci., 127:1–28, 2022

    2022

  3. [11]

    Chase, B

    Z. Chase, B. Chornomaz, S. Hanneke, S. Moran, and A. Yehudayoff. Dual VC dimension obstructs sample compression by embeddings. InCOLT, pages 923–946, 2024

    2024

  4. [12]

    V. Chepoi. Isometric subgraphs of Hamming graphs andd-convexity.Cybernetics (Kiev), 1:6–10, 1988

    1988

  5. [13]

    V. Chepoi. Classification of graphs by means of metric triangles.Metody Diskret. Analiz., 49:75–93, 96, 1989

    1989

  6. [14]

    Chepoi, A

    V. Chepoi, A. Genevois, and K. Knauer. Cell structure of mediangle graphs.arXiv preprint, 2505.23293v3, 2026. 56 V. CHEPOI AND M. MAAT

    2026 arXiv

  7. [15]

    Chepoi, K

    V. Chepoi, K. Knauer, and M. Philibert. Ample completions of oriented matroids and complexes of uniform oriented matroids.SIAM J. Discrete Math., 36:505–535, 2022

    2022

  8. [16]

    Chepoi, A

    V. Chepoi, A. Labourel, and S. Ratel. On density of subgraphs of Cartesian products.J. Graph Theory, 93(1):64–87, 2020

    2020

  9. [17]

    Daniely and S

    A. Daniely and S. Shalev-Shwartz. Optimal learners for multclass problems. InCOLT, pages 287–316, 2014

    2014

  10. [18]

    B. A. Davey and H. A. Priestley.Introduction to Lattices and Order. Cambridge University Press, 2002

    2002

  11. [19]

    D. Ž. Djoković. Distance-preserving subgraphs of hypercubes.J. Combin. Theory Ser. B, 14:263–267, 1973

    1973

  12. [20]

    A. Dress. Towards a theory of holistic clustering. InMathematical Hierarchies and Biology (Piscataway, NJ, 1996), volume 37, page 271–289. Amer. Math. Soc., Providence, RI, 1997

    1996

  13. [21]

    Fijalkow, C

    N. Fijalkow, C. Aiswarya, G. Avni, N. Bertrand, P. Bouyer, R. Brenguier, A. Carayol, A. Casares, J. Fearnley, P. Gastin, H. Gimbert, T. A. Henzinger, F. Horn, R. Ibsen-Jensen, N. Markey, B. Monmege, P. Novotný, P. Ohlmann, M. Randour, O. Sankur, S. Schmitz, O. Serre, M. Skomra...

    2025 arXiv

  14. [22]

    Füredi and J

    Z. Füredi and J. Pasch. Traces of finite sets: extremal problems and geometric applications. InExtremal Problems for Finite Sets, volume3, pages251–282.BolyaiSocietyMathematical Studies, Visegrád, Hungary, 1991

    1991

  15. [23]

    Genevois.Cubical-like geometry of quasi-median graphs and applications to geometric group theory

    A. Genevois.Cubical-like geometry of quasi-median graphs and applications to geometric group theory. PhD thesis, Aix-Marseille Université, 2017. arXiv:1712.01618

    2017 arXiv

  16. [24]

    Grätzer.General Lattice Theory

    G. Grätzer.General Lattice Theory. Birkhäuser Verlag, 2003

    2003

  17. [25]

    Hatcher.Algebraic Topology

    A. Hatcher.Algebraic Topology. Cambridge Univ. Press, Cambridge, 2002

    2002

  18. [26]

    Haussler

    D. Haussler. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension.J. Combin. Theory Ser. A, 69:217–232, 1995

    1995

  19. [27]

    Haussler, N

    D. Haussler, N. Littlestone, and M. Warmuth. Predicting{0,1}-functions on randomly drawn points.Inform. and Comput., 115:248–292, 1994

    1994

  20. [28]

    Imrich and S

    W. Imrich and S. Klavžar.Product Graphs: Structure and Recognition. Wiley-Interscience Publication, New York, 2000

    2000

  21. [29]

    Knauer and T

    K. Knauer and T. Marc. On tope graphs of complexes of oriented matroids.Discrete Comput. Geom., 63(2):377–417, 2020

    2020

  22. [30]

    Lawrence

    J. Lawrence. Lopsided sets and orthant-intersection by convex sets.Pacific J. Math., 104(1):155–173, 1983

    1983

  23. [31]

    M. Maat. Strategy Improvement, the Simplex Algorithm and Lopsidedness, Sept. 2025. arXiv:2509.16075

    2025

  24. [32]

    S. Moran. Shattering-extremal systems, 2012. Masters’ thesis, arXiv:1211.2980

    2012 arXiv

  25. [33]

    Moran and M

    S. Moran and M. K. Warmuth. Labeled compression schemes for extremal classes. InALT 2016, volume 9925 of Lecture Notes in Comput. Sci., pages 34–49, 2016

    2016

  26. [34]

    Mulder.The Interval Function of a Graph, volume 132

    H. Mulder.The Interval Function of a Graph, volume 132. Math. Centre Tracts, Mathe- matisch Centrum, Amsterdam, 1980

    1980

  27. [35]

    B. K. Natarajan. On learning sets and functions.Machine Learning, 4(1):67–97, Oct. 1989

    1989

  28. [36]

    A. Pajor. Sous-espacesℓn 1 des espaces de Banach, 1985. Travaux en Cours. Hermann, Paris

    1985

  29. [37]

    Pollard.Empirical processes

    D. Pollard.Empirical processes. Theory and applications, volume 2. NSF-CBMS Regional Series in Probability and Statistics, 1990

    1990

  30. [38]

    B. I. P. Rubinstein, P. L. B. Bartlett, and J. H. Rubinstein. Shifting: One-inclusion mistake bounds and sample compression.J. Comput. Syst. Sci., 75(1):37–59, 2009

    2009

  31. [39]

    M. L. van de Vel.Theory of Convex Structures, volume 50. Elsevier, 1993

    1993

  32. [40]

    Wiedemann.Hamming Geometry

    D. Wiedemann.Hamming Geometry. PhD thesis, Univ. of Ontario, 1986. re-typeset 2006

    1986

  33. [41]

    E. Wilkeit. Isometric embedding in Hamming graphs.J. Combin. Theory Ser. B, 50:179–197, 1990

    1990

  34. [42]

    E. Wilkeit. The retracts of Hamming graphs.Discrete Math., 102:197–218, 1992

    1992

  35. [43]

    P. Winkler. Isometric embedding in the product of complete graphs.Discrete Appl. Math., 7:221–225, 1984

    1984

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.