REVIEW 2 major objections 5 minor 14 references
Enumerating Minimal Balanced Collections
T0 review · 2 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read The paper proves that the number B_n of minimal balanced collections of subsets of an n-element set lies between 0.288·2^{(n−1)^2}/n! and 120·2^{n^2−n}/n!, establishing B_n = 2^{Θ(n^2)}/n!, but the sharper asymptotic formula in the abstract
desk verdict The body proves new bounds on minimal balanced collections; the arXiv abstract's exact asymptotic is not supported by the proof and is explicitly deferred as future work. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key object is the set U(λ)={u∈{0,1}^m : u·λ=1} of unificators of a weight vector—0-1 rows whose dot product with λ equals 1. For any balanced matrix, its rows are unificators, and λ is realizable exactly when U(λ) spans R^m (Lemma 4.1). The maximum size of U(λ) over positive λ is the middle binomial coefficient, by the extremal antichain bound (Lemma 4.5). The Z_2^m inversion action on columns changes signs of weights without changing |U(λ)|, so an orbit of a nonzero matrix has size 2^{m−|U(λ)|}, and each orbit contains exactly two positive matrices. This orbit-level bookkeeping, combined with an F_2-based construction of many nonzero matrices (Lemma 6.1) and a crude upper bound on all f
What would settle it
Compute B_8 and B_9 exactly using the paper's inductive construction of Λ_m (as was done for n≤7 in Table 2) and compare n!·B_n / 2^{n^2−n+1}; if this ratio does not approach 1 or fluctuates, the abstract's asymptotic formula is false. Alternatively, search small m for a nonzero weight vector λ with |U(λ)| exceeding the middle binomial coefficient; such a vector would invalidate the upper-bound transfer in Lemma 5.4.
Extended reading notes
Core claim
The central discovery is that the number of minimal balanced collections is governed by the number of full-rank n×n 0-1 matrices whose unique weight vector has no zero coordinates, up to a factor of about 2^n and n!. Concretely, Lemma 3.1 identifies minimal balanced collections with full-rank 0-1 matrices M satisfying Mλ=1 for a strictly positive λ; then the Z_2^m action that replaces any column by its complement flips the sign of the corresponding weight, and every orbit contains exactly two positive matrices (Lemma 5.3). This yields a transfer inequality (Lemma 5.4) relating positive and nonzero matrices. A linear-algebra construction over F_2 produces enough nonzero n×n matrices for the l
Load-bearing premise
The lower bound rests on the claim that a family of 0-1 vectors that is linearly independent over F_2 remains linearly independent over Q, so that a matrix built from such a family has a unique rational weight vector with no zero coordinates; if that transfer fails, the lower bound construction collapses—and the upper-bound transfer also relies on the middle-binomial bound applying to mixed-sign weight vectors via sign-flip invariance.
Editorial extensions
If this is right
- B_n = n^{-1}2^{Θ(n^2)}: the leading exponent of the count is n^2, up to polynomial factors.
- Most minimal balanced collections have exactly n subsets: Lemma 6.5 gives B_n < C B_{n,n} for a constant C, so the m=n term dominates the total.
- The factor 2 per nonzero orbit means every minimal balanced collection can be paired with another obtained by complementing all its sets, and both remain balanced.
- The lower bound's construction produces minimal collections from F_2-bases with an extra independence condition, giving a concrete infinite family.
- For fixed m, the exact count B_{n,m} is computable from the set of weight vectors Λ_m via the inclusion-exclusion formula in Corollary 4.1; the paper lists closed forms for m≤4.
Reading between the lines
- The abstract's asymptotic formula B_n = 2^{n^2−n+1}/n!(1+o(1)) would require closing the gap between the lower bound ~2^{n^2−2n} and the upper bound ~2^{n^2−n}; this is a natural target for a sharper analysis of U(λ) for mixed-sign weight vectors.
- The orbit method suggests a probabilistic interpretation: choosing a random 0-1 matrix and conditioning on full rank and nonzero weight, the number of positive representatives per orbit is exactly 2, which may connect to random hypergraph perfect matchings.
- The F_2 construction generalizes in an obvious way to other finite fields F_{p^k}, as the paper itself lists; if the F_2 independence-to-Q transfer has analogues, similar bounds would follow for those fields.
- The link to the colorful Carathéodory theorem indicates that geometrically, the count of minimal balanced collections is controlled by how many antipodal point configurations contain the origin in exactly two spanned simplices; this could yield a geometric proof of the upper bound.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops a matrix-theoretic framework for counting minimal balanced collections of subsets of [n]. It proves that a collection is minimal balanced iff its 0-1 matrix has full column rank and a unique all-positive weight vector solving Mλ=1 (Lemma 3.1), derives a counting formula in terms of the set of ``unificators'' of the weight vector (Lemma 4.2), and then uses a Z2 action that inverts chosen columns to relate positive and mixed-sign full-rank matrices (Lemmas 5.1--5.4). The main proved result is Theorem 1: 0.288/n! · 2^{(n−1)^2} < B_n < 120/n! · 2^{n^2−n}. The arXiv metadata abstract, however, claims the sharper asymptotic B_n = 2^{n^2−n+1}/n! (1+o(1)). The body does not prove this; Section 7 explicitly lists reducing the exponential gap to a constant factor or to (1+o(1)) as future work. The full-text abstract on page 1 states only the bounds, so the paper also contains an internal inconsistency between the two abstracts.
Significance. If the asymptotic formula claimed in the arXiv abstract were established, it would be a substantial answer to a natural enumeration problem originating in cooperative game theory. The paper's structural lemmas, especially the orbit-ratio control in Lemma 5.4 and the finite-field construction in Lemma 6.1, are plausible and potentially reusable, and the exact formulas for fixed m (Corollary 4.1 and the table after it) are useful. However, the headline asymptotic claim is not a consequence of any theorem in the paper: the proved lower and upper bounds are separated by a factor exponential in n. The paper's genuine contribution at present is a nontrivial pair of bounds within an exponential factor, not the announced enumeration.
major comments (2)
- [Abstract / Theorem 1 / §7] The abstract claims B_n = 2^{n^2−n+1}/n! (1+o(1)) and says the asymptotic number is determined. Theorem 1 proves only 0.288/n!·2^{(n−1)^2} < B_n < 120/n!·2^{n^2−n}. Since 2^{(n−1)^2}=2^{n^2−2n+1}, the upper/lower ratio is (120/0.288)·2^{n−1} = O(2^n), so no (1+o(1)) formula follows. Section 7, item 1 explicitly lists ``reducing the gap between the upper and lower bounds, ideally up to a constant factor or even to (1+o(1))'' as future work. Thus the paper's central announced result is not derived anywhere in the body. The full-text abstract on page 1 states only the bounds, so the arXiv metadata abstract and the article abstract also disagree; whichever is intended, the asymptotic claim is unsupported.
- [§6, Cor. 6.3 and Lemma 6.5] The missing ingredient for the claimed asymptotic is a lower bound with exponent n^2−n. Corollary 6.3 gives B_{n,n} ≥ α/n!·2^{(n−1)^2}, and Lemma 6.5 shows B_n < 30 B_{n,n}; combining this with Corollary 6.4 yields Theorem 1's upper bound. But no argument converts the lower exponent 2^{n^2−2n+1} into the abstract's 2^{n^2−n+1}. This is not a matter of sharpening constants; the gap between the two exponents is exponential in n. Since the authors themselves defer this to future work, the title and abstract overstate what is proved.
minor comments (5)
- [§6, Prop. 6.2] The proof of Proposition 6.2 is given as ``Clear!'' but the statement is load-bearing for the lower bound. It is true for 0-1 vectors: F2-independence gives an m×m minor with determinant 1 mod 2, hence an odd integer determinant over Z, so the vectors are Q-independent. Please include this argument.
- [§6, Lemma 6.1, step 4] The zero-coordinate argument says a Q-dependence of 1 and {a'_i}_{i∉S} contradicts the earlier independence claim ``since S≠∅.'' To make this precise, also rule out S=[n]; that case is impossible because A'λ=1 would fail, but the text should say so, since the independence claim only applies to proper subsets.
- [§5, Lemma 5.4] Lemma 4.5's upper bound on |U(λ)| is proved for positive weight vectors. In Lemma 5.4 the same bound is used for mixed-sign λ. The reduction via Corollary 5.1.3 and the inversion z_{neg(λ)} works, but should be stated explicitly, because the printed proof of Lemma 4.5 uses positivity when it concludes v=u from (u−v)λ=0.
- [§5, Lemma 5.2] In the statement and first sentence of the proof, the symbol x_i appears before λ is introduced; it should be λ_i.
- [Table 3] Table 3 appears to contain timing data in seconds rather than mathematical data. If it is not essential, remove it or move it to an appendix; as printed it is a distraction.
Circularity Check
No circularity: the counting bounds are derived from independent rank/orbit arguments; the abstract's asymptotic formula is unsupported but not circular.
full rationale
I walked the derivation chain. Proposition 3.1 and Lemma 3.1 reindex minimal balanced collections as positive full-rank 0-1 matrices; Lemma 4.2 is a direct inclusion-exclusion count over unificators; Lemmas 4.3-4.5 use Sperner's theorem rather than the target count; Section 5 relates positive and nonzero matrices through an explicitly computed Z2 action (Lemma 5.3); and Section 6 obtains the lower bound via an F2/Q rank construction and the upper bound by crude counting of 0-1 matrices combined with orbit ratios. No equation is defined in terms of the quantity it is supposed to determine, and no fitted parameter is relabeled as a prediction. The only self-citation, [7] (Bludov and Musin), is used illustratively in the introduction/table for balanced 2-subsets and is not load-bearing in any proof. One non-circular concern should be flagged: the abstract claims B_n = 2^{n^2-n+1}/n!(1+o(1)), but the body proves only Theorem 1, with bounds differing by an exponential factor, and Section 7 explicitly lists 'Reducing the gap between the upper and lower bounds, ideally up to a constant factor or even to (1+o(1))' as future work. That is a support gap or overclaim, not a circular derivation. Therefore no significant circularity; the minimal non-zero score reflects only the minor self-citation and the abstract/body mismatch, neither of which is circular.
Assumptions & free parameters
assumptions (5)
- domain assumption Bondareva-Shapley characterization of balanced collections and Proposition 3.1 bijection with full-rank positive 0-1 matrices.
- standard math For a full-rank 0-1 matrix M, the solution λ to Mλ=1 is unique and rational.
- standard math Sperner's theorem.
- standard math Linear independence of 0-1 vectors over F2 implies independence over Q.
- domain assumption Peleg's inductive construction generates Λ_m.
Cite this review
Pith. "Pith review of Enumerating Minimal Balanced Collections." pith.science (2026). https://pith.science/paper/4ZUJXSKC
@misc{pith2026251119323,
author = {Pith},
title = {Pith review of: Enumerating Minimal Balanced Collections},
year = {2026},
howpublished = {\url{https://pith.science/paper/4ZUJXSKC}},
note = {Machine review of arXiv:2511.19323}
}
abstract
In this note, we explore the combinatorics of balanced collections. A collection of subsets of the set $[n] = \{1, \dots, n\}$ is called \emph{balanced} if the relative interior of the convex hull of the corresponding characteristic vectors intersects the main diagonal of the $n$-dimensional cube at a point other than the origin, and it is called \emph{minimal} if it contains no proper balanced subcollections. We determine the asymptotic number of minimal balanced collections. Specifically, if $B_n$ denotes their total number, then \[ B_n=\frac{2^{n^2-n+1}}{n!}\bigl(1+o(1)\bigr) \qquad\text{as }n\to\infty. \]
Reference graph
Works this paper leans on
-
[1]
3Blue1Brown, The hardest problem on the hardest test, video at https://youtu.be/OkmNXy7er84?si=hL-UCYIWtLWdVVyD
-
[2]
2-3, 141–152
Imre B´ ar´ any, A generalization of Carath´ eodory’s theorem,Discrete Math.,40(1982), no. 2-3, 141–152
1982
-
[3]
L. J. Billera, Some theorems on the core of an n-person game without side payments,SIAM J. Appl. Math.,18(1970) 567-579
1970
-
[4]
L. J. Billera, J. Tatch Moore, C. Dufort Moraites, Y. Wang, and K. Williams. Maximal unbalanced families, 2012. URL: https://arxiv.org/abs/1209.2309, arXiv:1209.2309
arXiv 2012
-
[5]
Louis J. Billera. On games without side payments arising from a general class of markets.375Journal of Mathematical Economics, 1(2):129–139, 1974. URL: https://www.sciencedirect.com/science/article/pii/0304406874900044, doi:10.1016/0304- 4068(74)90004-4
arXiv 1974
-
[6]
Positive Sum Systems, pages 157–171.Springer International Publishing, Cham, (2015)
Anders Bj¨ orner. Positive Sum Systems, pages 157–171.Springer International Publishing, Cham, (2015)
2015
-
[7]
Balanced 2-subsets.Mathematical Notes, 114(3):407–411, 380 (2023)
Mikhail Bludov and Oleg Musin. Balanced 2-subsets.Mathematical Notes, 114(3):407–411, 380 (2023). doi:10.1134/S0001434623090122
-
[8]
M. V. Bludov. Balanced sets and homotopy invariants of covers, preprint at arXiv:2501.05799
Show all 14 references
-
[9]
O. N. Bondareva. Some applications of linear programming methods to the theory of cooperative games.Problemy Kibernetiki,10(1963), 119–139 (in Russian)
1963
-
[10]
Capturing the Origin with Random Points: Generalizations of a Putnam Problem.The College Mathematics Journal,27(3)(1996), 186–192
Howard, R., Sisson, P. Capturing the Origin with Random Points: Generalizations of a Putnam Problem.The College Mathematics Journal,27(3)(1996), 186–192. https://doi.org/10.1080/07468342.1996.11973774
1996
-
[11]
Dylan Laplace Mermoud, Michel Grabisch and Peter Sudh¨ olter. Minimal bal- anced collections and their application to core stability and other topics of game theory,Discrete Applied Mathematics,341(2023), 60-81, ISSN 0166-218X, https://doi.org/10.1016/j.dam.2023.07.025
2023 doi
-
[12]
An inductive method for constructing minimal balanced collections of finite sets.Naval Res
Bezalel Peleg. An inductive method for constructing minimal balanced collections of finite sets.Naval Res. Logist. Quart.12(1965), 155–162. 19
1965
-
[13]
Klosinski, G.L
L.F. Klosinski, G.L. Alexanderson and L.C. Larson. The Fifty-Third William Lowell Put- nam Mathematical Competition,Am. Math. Monthly,100(1993) pp 755-767
1993
-
[14]
L. S. Shapley. On balanced sets and cores,Naval Res. Logist. Quart.,14(1967), 453–460. M. V. Bludov, MIPT E-mail address:bludov.mv@phystech.edu N. K. Zuev, MIPT E-mail address:zuev.nk@phystech.edu 20
1967
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.