REVIEW 1 major objections 4 minor 5 references
The edge multiset dimension of hypercubes
T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper proves that the edge multiset dimension of the hypercube $Q_d$ is infinite exactly in dimensions 2 through 5 and finite for every dimension at least 6, settling an open question from a recent survey.
desk verdict A complete and convincing classification of the edge multiset dimension of hypercubes, with the d=5 nonexistence resting on a heavy but well-audited computation. 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 random-flow forest lemma (Lemma 11) is the main mechanism. Fix two edges $e,f$ and partition the cube into cells $V_{ab}=\{w:d(e,w)=a,\,d(f,w)=b\}$; the numbers of selected vertices in these cells are independent binomial variables. Equality of the two edge histograms is exactly a zero-divergence condition on the graph whose vertices are distance levels, and after conditioning on the cells outside any spanning forest, every tree component has at most one feasible flow. The collision probability is therefore at most the product of central-binomial atoms $\beta(N)=2^{-N}\binom{N}{\lfloor N/2\rfloor}$ over the forest edges. A secondary mechanism is the projection lemma (Lemma 3), which identifies edges in one direction with vertices of $Q_{d-1}$ and provides the necessary condition that drives the exhaustive $Q_5$ search.
What would settle it
Recompute the $Q_5$ enumeration with an independently written program: if any 32-bit mask passes all five directional filters yet has no pair of edges with equal histograms, then $\mathrm{edim}_m(Q_5)$ is finite and the classification fails. More directly, any explicit edge-multiset resolving set in $Q_5$ would refute Theorem 6.
Extended reading notes
Core claim
The central discovery is the complete classification of the edge multiset dimension of hypercubes: $\mathrm{edim}_m(Q_d)=\infty$ exactly when $2\le d\le5$, and $\mathrm{edim}_m(Q_d)$ is finite for every $d\ge6$. For the infinite side, the paper exhaustively verifies that no subset of the 32 vertices of $Q_5$ separates all 80 edges by distance multisets; for the finite side, it gives explicit resolving sets of sizes 15, 63, 115, 246, and 492 in dimensions 6 through 10, and a probabilistic existence proof for all larger dimensions. The probability argument shows that for a random landmark set chosen by independent fair coin flips, the chance that any two edges collide is below 1 once $d\ge11$, so a resolving set exists.
Load-bearing premise
The classification rests on the correctness of the computer-assisted parts: the exhaustive enumeration of all $2^{32}$ subsets of $Q_5$, the certificate checks for $Q_6$ through $Q_{10}$, and the certified rational forest bounds for $11\le d\le50$, and an error in any of these computations could shift the threshold.
Editorial extensions
If this is right
- The finite-infinite transition is now completely known: $\mathrm{edim}_m(Q_d)=\infty$ for $d\in\{2,3,4,5\}$ and finite for every $d\ge6$.
- For dimensions 6 through 10, explicit resolving sets of sizes 15, 63, 115, 246, and 492 are available as independent certificates.
- For every dimension $d\ge11$, a random landmark set of density 1/2 is resolving with positive probability, certified by exact rational bounds for $11\le d\le50$ and an elementary ten-edge forest estimate beyond.
- The lower bound $6\le\mathrm{edim}_m(Q_6)$ holds, narrowing the first open case to the interval $[6,15]$.
Reading between the lines
- Not in the paper: the random-flow forest lemma does not rely on special hypercube arithmetic beyond explicit cell formulas, so a similar union-bound strategy could locate finite-infinite thresholds for Cartesian products of paths, cycles, or other highly symmetric graphs with few edge-pair orbit types.
- Not in the paper: the certified range $11\le d\le50$ and the tail estimate $d\ge51$ use different arguments, and a uniform analytic bound starting at $d=11$ seems within reach, an extension the paper's own open-problem list anticipates.
- Not in the paper: the density-1/2 random construction is probably far from optimal; sparse random landmark sets may yield much smaller resolving sets, and the paper's own heuristic failure to find a size-14 set for $Q_6$ suggests the true minimum is closer to 6 than to 15.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper determines the edge multiset dimension of hypercubes completely. It proves edim_m(Q_d)=∞ if and only if 2≤d≤5, edim_m(Q_1)=1, and finiteness for all d≥6. The main ingredients are a projection lemma reducing the Q5 nonexistence proof to an exhaustive 2^32 enumeration; explicit resolving sets for Q6–Q10; a probabilistic construction for d≥11 based on a random-flow forest lemma for collision probabilities; certified rational bounds for 11≤d≤50; and an analytic tail estimate for d≥51. The paper also proves the elementary lower bound edim_m(Q6)≥6.
Significance. If the computational claims are correct, the paper fully resolves the open problem posed in the survey [1] and introduces a reusable anti-concentration technique for multiset resolvability parameters: collision probability is bounded by a product of central-binomial atoms after conditioning outside a forest. The analytic part is rigorous and largely self-contained, and the paper ships archived code, an independent verifier, explicit certificates, and a SHA-256 manifest, which are notable strengths. The residual risk is concentrated in the computer-assisted Theorem 6, as discussed below; I did not execute the deposited code during review.
major comments (1)
- [Section 4, Theorem 6 and Remark 8] The complete classification rests on the Q5 exhaustive proof, and within it the correctness of the R4 bitset (Lemma 5) and the projection-filter lookup in step (i) is load-bearing: an error there could discard a genuine resolving set before step (ii) is reached. Remark 8 says that the independent verifier "recomputes all edge histograms from scratch," but it does not state whether the verifier re-derives R4, re-runs the five directional filters over all 2^32 masks, or merely rechecks the 3,056,640 survivors supplied by the enumerator. Please specify the verification pipeline precisely and report the verifier's own blockwise survivor counts, or provide a filter-free exhaustive check. This is a documentation request rather than a claim of a mathematical error; if the verifier already re-derives R4, a clarifying sentence in Remark 8 will resolve the concern.
minor comments (4)
- [Section 9, Lemma 18] The statement of Lemma 18 displays the lower bound as "Nab ≥ 2d/(Cd 2)" and should read "Nab ≥ 2^d/(C d^2)"; the surrounding text shows the intended meaning, but the displayed formula should be corrected.
- [Section 8, Table 3] The certified rational bounds for 11≤d≤50 are reported only as five-digit decimal upper roundings. Including one exact certified fraction (for example for d=11) or the certificate script in an appendix would let readers inspect the rational arithmetic without downloading the archive.
- [Section 6, Lemma 11] The incidence matrix B_Γ is used in the sentence "equality of the two histograms is precisely the zero-divergence system B_ΓY=0" before it is formally defined; reorder the text so that the notation is introduced first.
- [Section 9, Lemma 18] The claim that each factor in the near-central binomial ratio is nondecreasing in n along each parity class is stated without proof; a one-sentence verification would make the estimate easier to check.
Circularity Check
No circularity: the classification follows from independent exhaustive certificates, a self-contained probabilistic union bound, and verified computational checks.
full rationale
The derivation chain is self-contained and does not reduce any claimed prediction to its inputs. The finite-infinite transition for Q5 rests on Theorem 6, whose proof enumerates all 2^32 masks, filters them by the proven necessary condition of Corollary 4 (the R4 bitset from Lemma 5), and checks every surviving mask for a collision; the filter is a genuine necessary condition, not an assumption of the conclusion, and the survivor check is explicit. The Q6-Q10 certificates in Table 1 are verified by pairwise histogram comparison and by an independent checker. The d >= 11 result uses a random landmark set with fixed density 1/2, a forest-based anti-concentration lemma with explicit binomial-atom bounds, exact orbit and cell formulas, and certified rational upper bounds; no parameter is fitted to the target values. The tail d >= 51 is handled by a closed-form ten-edge forest estimate. Citations to the survey [1] for the Q3/Q4 values are not load-bearing, since the paper states it reproduced those values by its own exhaustive enumeration over all 2^8 and 2^16 subsets. No uniqueness theorem is imported from the authors' prior work, and no known result is merely renamed. The open-problem remark about simulated annealing is explicitly heuristic and does not support any theorem. The only residual concern is reproducibility of the archived computations, which is a correctness/verification matter, not circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption Correctness of the deposited computer code for the exhaustive Q5 enumeration, the certificate checks for Q6-Q10, and the certified rational bounds for 11≤d≤50.
- standard math Aut(Q_d) consists exactly of coordinate permutations and translations, used in Lemma 13 to classify edge-pair orbits.
- standard math Standard probabilistic facts: independence of binomial cell counts, the union bound, and Wallis-type bounds on central binomial coefficients (Lemma 17).
Cite this review
Pith. "Pith review of The edge multiset dimension of hypercubes." pith.science (2026). https://pith.science/paper/YCT2XJ2D
@misc{pith2026260809983,
author = {Pith},
title = {Pith review of: The edge multiset dimension of hypercubes},
year = {2026},
howpublished = {\url{https://pith.science/paper/YCT2XJ2D}},
note = {Machine review of arXiv:2608.09983}
}
read the original abstract
For a graph G and a nonempty set S of vertices, the edge multiset representation of an edge e is the multiset of distances from e to the elements of S, where d(uv,s)=min{d(u,s),d(v,s)}. The edge multiset dimension edim_m(G) is the minimum cardinality of a set whose edge representations are pairwise distinct, and is infinite if no such set exists. A recent survey asked whether edim_m(Q_d) is infinite for every d >= 3. We answer this question negatively and determine the finite-infinite transition completely: edim_m(Q_d) is infinite if and only if 2 <= d <= 5. An exhaustive computation proves edim_m(Q_5) = infinity, extending the known nonexistence results for Q_3 and Q_4. Explicit independently verifiable resolving sets are given for Q_6 through Q_10. For all d >= 11 we prove existence probabilistically: equality of two random edge histograms is a zero-divergence event on a graph of distance levels, and conditioning outside a spanning forest bounds its probability by a product of central-binomial atoms. Certified exact rational computations cover 11 <= d <= 50, and an elementary ten-edge forest estimate handles the tail d >= 51. We also prove the lower bound edim_m(Q_6) >= 6.
Reference graph
Works this paper leans on
-
[1]
Multiset resolvability parameters in graphs: A survey with new results and open problems
M. Farhan, S. Klavˇ zar, D. Kuziak, and I. G. Yero,Multiset resolvability parameters in graphs: A survey with new results and open problems, arXiv:2607.10311, 2026
work page Pith review arXiv 2026
-
[2]
H. M. Ikhlaq, R. Ismail, H. M. A. Siddiqui, and M. F. Nadeem,A new technique to uniquely identify the edges of a graph, Symmetry15(2023), no. 3, Article 762
work page 2023
- [3]
-
[4]
Saenpholphat,On multiset dimension in graphs, Academic SWU1(2009), 193–202
V. Saenpholphat,On multiset dimension in graphs, Academic SWU1(2009), 193–202
work page 2009
-
[5]
R. Simanjuntak, P. Siagian, and T. Vetr´ ık,The multiset dimension of graphs, arXiv preprint arXiv:1711.00225v2, 2019. 13
arXiv 2019
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.