{"id":"1f124827-1baa-49db-ab21-31d95308d33d","arxiv_id":"2607.28813","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Multiset dimension attains the trivial upper bound n(G) for the first time at order 11 (eight graphs), equals 4 on every n×n king grid n ≥ 5, and equals n on every 3×n king strip n ≥ 6.","lead":"This preprint disproves a 2017 conjecture by finding the first graphs whose multiset dimension equals their number of vertices, and exactly evaluates the multiset dimension on square and strip king grids. The results give sharp answers to two open questions: four landmarks always resolve an n×n king grid, while a 3×n strip needs one landmark per column.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Completeness of the order-≤11 census is the load-bearing external assumption; 'exactly eight' would fail if geng omitted an isomorphism class, and OEIS totals do not rule this out.","rationale":"The reader's weakest_assumption identifies exactly the same point: the 'exactly eight' claim depends on the completeness and correctness of the external enumeration pipeline (geng, McKay databases, networkx atlas, and the base-16 encoding/filter). I agree that this is the single most load-bearing concern. The internal mathematical content of Parts II and III is analytically argued and independently checkable: the boundary inequalities, antipodal obstruction, collision tables, and the min-plus transfer certificate are all explicitly stated, with the potential table printed in Appendix A and scripts archived. Even the eight order-11 candidates are re-verified by multiple independent programs, so the concern is not about the correctness of the reported examples but about the exhaustive universal quantification in Theorem 1.1. The OEIS count match is a useful aggregate check but cannot detect a generator that omits one isomorphism class while duplicating another. Because the theorem is stated unconditionally as a mathematical result, and because the missing link is not internal to the paper's derivations, the most honest verdict is to accept conditionally: the theorem should be regarded as established once an independent regeneration of the order-11 census reproduces the same eight graph6 codes. This does not reject the paper's substantial contributions — the conjecture is already falsified by G1 alone — but it makes the boundary between verified mathematics and tooling-dependent computation explicit.","tokens_in":21822,"tokens_out":16429,"duration_ms":178640,"concrete_test":"Regenerate all connected graphs of order 11 using an independent generator — for example, a different version of nauty/geng, another canonical graph generator if available, or an independent order-11 graph6 database — and confirm the total count is 1,006,700,565. Then rerun scan11.cpp on the regenerated list and check that exactly the same eight graph6 codes from Table 1 are recovered. For orders ≤10, repeat the same procedure using two independently sourced graph6 databases rather than relying on the networkx atlas and a single published database. If the same eight candidates and the same DDI/extremal counts are obtained, the completeness objection is settled and Theorem 1.1 can be accepted as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 1.1's exactness claim — 'exactly eight connected graphs G with 2 ≤ n(G) ≤ 11 and dim_m(G)=n(G), all of order 11' — rests entirely on the exhaustive enumeration described in §4. The pipeline's internal parts are sound: the base-16 encoding is injective for n≤11, the filter correctly discards graphs that cannot have dim_m = n or n−1, and the eight reported order-11 graphs were re-verified by two independent programs. What is not proved is that geng 2.8.9 (with the res/mod streams) actually emits every isomorphism class of connected graphs of order 11 exactly once. The paper's own §4.1 states: 'Completeness of the enumeration rests on the generator.' Matching OEIS A001349 at orders 2–11 verifies the total number of generated graphs, but a generator bug that simultaneously omits one isomorphism class and duplicates another would preserve the total. If the omitted class had dim_m = n, the 'exactly eight' and 'smallest order is 11' statements would be wrong. The same completeness concern applies to orders ≤10 via McKay's published databases and the networkx atlas, though these are more mature and independently checkable. This is not an internal inconsistency; it is a load-bearing tooling assumption. The existence of a counterexample is independently secure — G1 is explicitly constructed and its full-vertex resolving property is hand-verified — but the paper's headline exactness and minimality claims are only as strong as geng's completeness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the multiset dimension dim_m(G). Part I presents an exhaustive computation over all connected graphs of orders 2–11, reporting exactly eight graphs with dim_m(G)=n(G), all of order 11, thereby disproving the conjecture of Simanjuntak–Siagian–Vetrík that dim_m(G)≤n(G)−1. Part II proves that dim_m(P_n ⊠ P_n)=4 for every n≥5, using rotated coordinates and a case analysis showing that every three-landmark set creates a collision. Part III proves dim_m(P_3 ⊠ P_n)=n for n≥6 via a min-plus transfer certificate for the lower bound and an explicit periodic landmark pattern for the upper bound, and derives dim_m(P_h ⊠ P_n)=Θ(n) for every fixed h≥3.","tokens_in":21984,"tokens_out":17335,"duration_ms":169971,"significance":"If correct, the paper resolves two open questions and a conjecture: the trivial upper bound is attained first at order 11; square king grids are resolved by four landmarks for all n≥5; and height-three king strips require one landmark per column. The paper is unusually strong on reproducibility: it ships scanners, verifiers, raw outputs, a full min-plus potential table, and independent re-implementations of the key checks. The explicit graph G1 and the hand-checkable collision table of Lemma 10.2 are valuable. The main caveat is that the exactness claims of Theorem 1.1 are computational and inherit the trust assumptions of the external generator nauty/geng; the paper explicitly acknowledges this. I also found a specific gap in the zigzag case of Lemma 9.1 that needs repair.","major_comments":[{"comment":"The alleged collision pair P'=(u3, v3+2), Q'=(u3−1, v3+1) does not have the asserted equidistance to p3=(u3−1, v3): the L1 distances are |u3−(u3−1)| + |(v3+2)−v3| = 3 and |(u3−1)−(u3−1)| + |(v3+1)−v3| = 1, respectively. The statement 'both points have L1-distance 2 from p3' is false, so the two vertices do not have equal ordered distance vectors to the three landmarks. Consequently the derivation of relation (9), v1 = v3+1, is unsupported. Since (9) is used to obtain the parametrization (10) and to finish the zigzag case, this is a load-bearing gap in the proof of Theorem 1.2. Please supply a correct collision pair or a different argument establishing (9).","section":"§9, Lemma 9.1 (zigzag case)"},{"comment":"The exactness and minimality claims — 'exactly eight' graphs and '11 is the smallest order' — rest on the completeness of the geng enumeration. The paper states this explicitly and checks totals against OEIS A001349, but a generator bug that simultaneously omitted one isomorphism class and duplicated another would preserve the total. Because the theorem's headline is the exact count, I ask the revision to provide or describe an independent verification of the order-11 enumeration, or alternatively to state the theorem as conditional on the correctness of nauty/geng. This is a correctness-risk / reproducibility request rather than a claim of an observed error.","section":"§4.1 / Theorem 1.1"}],"minor_comments":[{"comment":"The DDI distribution at n=11 is stated as '3 244621 4 996380 5 185858 6 9514 7 630 8 93 9 29 10 1 11 8', but these counts sum to 1,437,143, not the stated 1,437,134 DDI graphs in Table 2. Please reconcile the arithmetic.","section":"§4.2"},{"comment":"In the zigzag proof, the notation 'L1-distance' is used without definition; it is the rotated-coordinate distance |u−u'|+|v−v'|. Please define it at first use.","section":"§9"},{"comment":"The command line fragment 'geng -cq 11i/8' is slightly cryptic; please spell out the full invocation, e.g. 'geng -c -q 11 i/8', so that the eight disjoint streams are unambiguous.","section":"§4.1"},{"comment":"The remark is commendably transparent about the local conditions being necessary but not sufficient for resolving. I suggest adding a sentence in Section 15 emphasising that Proposition 15.1 therefore gives only a lower bound, not a characterisation, for m-resolving sets.","section":"§16, Remark 16.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct in substance and unusually well documented, but the gap in Lemma 9.1 is a genuine proof error in a central argument. The arithmetic discrepancy in the DDI counts also needs correction. If the author supplies a valid collision argument for the zigzag case and fixes the small data issue, I would support acceptance. The reliance on geng completeness is a standard computational trust assumption, but should be made explicit or independently checked as requested."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Real results, honestly scoped. The paper's three headline claims all check out as far as I can see: it kills the 2017 Simanjuntak–Siagian–Vetrík conjecture with eight order-11 graphs, closes Hakanen–Yero's 3-4 gap for square king grids, and solves the height-3 strip exactly. The grid proofs are actual mathematics — the rotated-coordinate conversion of Chebyshev to half-Manhattan on a parity sublattice is a neat idea, and the boundary-inequality case analysis is sound. The strip lower bound is a min-plus transfer with a printed potential table, so every transition is checkable by hand; the automaton description of the equality case is a nice bonus.\n\nThe paper is also unusually transparent about what it does not do: order-12 is explicitly out of scope, the rectangular case is honestly left open, and Remark 16.4 says the local conditions are necessary but not sufficient. That is the right posture.\n\nThe soft spot, as the stress-test note says, is the 'exactly eight' and 'smallest order 11' clause. It rests on geng's completeness for order 11. Matching OEIS A001349 verifies the total count but not the isomorphism-class repartition; a generator bug that swapped one class for a duplicate would be invisible in the totals. This is not an internal flaw — G1 is explicitly constructed and its resolving property hand-verified, so existence is secure — but the exactness and minimality claims inherit a tooling assumption. In practice nauty geng is the standard and the risk is low, but a referee should be asked to actually rerun the census scripts or at least check hashes of the per-stream outputs. The other computed ingredients (the transfer certificate, the 19-state core, the rectangular landscape) are all reproducible from the ancillary code, and the key tables are in the appendix.\n\nMinor note: the paper is long and dense, and the Part I verification relies on a networkx atlas and McKay's databases for small orders, which are mature. No problem there.\n\nWho this is for: anyone working on resolvability parameters or metric dimension; it will be a standard citation. It deserves a serious referee. Send it with the request to audit the census, not just read the summary.","headline":"Real results, honestly scoped: the paper disproves a conjecture and resolves two open problems, with the only genuine soft spot being the census completeness behind 'exactly eight'.","tokens_in":22764,"tokens_out":2954,"would_cite":true,"duration_ms":34899,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C76"],"pacs":[],"model":"deepseek-v4-flash","headline":"Multiset dimension can equal a graph's vertex count, and the smallest such graphs have order 11; square king grids need exactly four landmarks, while 3×n king strips need one per column.","keywords":["multiset dimension","multiset resolving set","distance degree sequence","metric dimension","king grid","strong product","Chebyshev metric","exhaustive search"],"falsifier":"Run an independent exhaustive enumeration of all connected graphs of orders through 11 and compute dim_m exactly; if any graph outside the paper's eight satisfies dim_m = n, Theorem 1.1 collapses. Alternatively, find a three-landmark set that multiset-resolves P_5 ⊠ P_5 or any n ≥ 5, which would falsify Theorem 1.2.","tokens_in":1648,"feed_emoji":"📐","tokens_out":4155,"duration_ms":100155,"temperature":0.7,"pith_summary":"The paper settles three open questions about the multiset dimension of a graph, the smallest number of unlabeled landmarks whose distance multisets identify every vertex. It shows that the trivial upper bound dim_m(G) ≤ n(G) is attained: exactly eight connected graphs of order 11 have dim_m = n, and no graph of order 2 through 10 does, disproving the conjecture that dim_m(G) ≤ n(G)−1 always holds. It also proves that every n×n king grid with n ≥ 5 needs exactly four landmarks, while a 3×n king strip needs exactly n for n ≥ 6 (with small exceptional values). Since every fixed-height strip grows linearly, the constant answer on squares is a strictly two-dimensional phenomenon. The proofs combine exhaustive computation, a coordinate change that turns Chebyshev distances into half Manhattan distances on a parity sublattice, and finite certificate arguments.","feed_headline":"Multiset dimension can equal the vertex count, first at 11","feed_subtitle":"A complete census through order 11 kills a conjecture and fixes square king grids at four landmarks.","key_machinery":"For the extremal result, the central identity is that the full vertex set is an m-resolving set exactly when the distance degree sequences DDS(v) = (a_0, a_1, ...), where a_i counts vertices at distance i from v, are pairwise distinct. The paper exploits the non-monotonicity of multiset resolvability under deletions of landmarks. For king grids, the key identity is 2 d_∞((x,y),(a,b)) = |u−u'| + |v−v'| in rotated coordinates (u,v) = (x+y−m, x−y), which maps the Chebyshev metric to half the Manhattan metric on a parity sublattice; four boundary inequalities reduce every potentially resolving three-landmark set to two geometric cases with explicit collisions. For strips, the machinery is a min-","core_discovery":"The paper establishes three theorems. Theorem 1.1: exactly eight connected graphs of order 11 (and none of smaller order) have multiset dimension equal to their order, disproving the 2017 conjecture of Simanjuntak–Siagian–Vetrík that dim_m(G) ≤ n(G)−1 for every graph with finite multiset dimension. Theorem 1.2: dim_m(P_n ⊠ P_n) = 4 for every n ≥ 5, answering a question of Hakanen and Yero. Theorem 1.3: dim_m(P_3 ⊠ P_n) = n for n ≥ 6, with the small values dim_m(P_3⊠P_3)=∞, dim_m(P_3⊠P_4)=5, and dim_m(P_3⊠P_5)=6. The square-grid lower bound is proved by showing that every set of three landmarks admits an explicit collision pair; the strip lower bound uses a finite min-plus transfer certificat","pith_inferences":["The non-monotonicity mechanism behind the counterexamples suggests that unlabeled resolving parameters may often have graphs where the full set resolves but no proper subset does, independent of the specific multiset setting.","The Θ(3^n) growth of the extremal admissible family found in the strip analysis hints that the number of truly minimal landmark sets on tall strips may also grow exponentially, although the paper only certifies the candidate family.","The blindness lower bound for strips (one landmark covers at most 2h−3 columns) likely extends to other layered strong products, giving linear lower bounds for a wider class of grids.","The observed non-monotonicity in the height-4 strip row (5, 6, >6, 6) suggests that the strip dimension is a fluctuating quasi-linear function for h ≥ 4, which could be tested by extending the computed rectangle scan further."],"forward_implications":["The conjecture dim_m(G) ≤ n(G)−1 for finite multiset dimension is false; the true universal upper bound is dim_m(G) ≤ n(G), first attained at order 11.","Square king grids are fully classified: dim_m(P_n ⊠ P_n) = ∞ for n = 2,3, dim_m(P_4 ⊠ P_4) = 6, and dim_m(P_n ⊠ P_n) = 4 for all n ≥ 5.","The height-three king strip is exactly solved: dim_m(P_3 ⊠ P_n) = n for all n ≥ 6, with the small cases determined.","For every fixed h ≥ 3, dim_m(P_h ⊠ P_n) = Θ(n), so a rectangle's multiset dimension can remain bounded only if its aspect ratio stays bounded.","All eight extremal graphs have diameter 3, girth 3, and trivial automorphism group; whether such graphs exist for infinitely many orders remains open."],"fun_headline_variants":["Multiset dimension conjecture false at n=11","Square king grid multiset dimension is 4 for n≥5","Multiset dimension equals vertex count first at n=11","King strip multiset dimension grows linearly with n","Multiset dimension: conjecture false, king grids fixed at 4"],"cache_read_input_tokens":23680,"weakest_assumption_plain":"The load-bearing premise for the 'exactly eight' claim is that the exhaustive enumeration of all connected graphs up to order 11 is complete and that the distance encoding never collides; if any isomorphism class was missed, the conclusion could fail.","fun_headline_variants_meta":{"raw":{"variants":["Multiset dimension conjecture false at n=11","Square king grid multiset dimension is 4 for n≥5","Multiset dimension equals vertex count first at n=11","King strip multiset dimension grows linearly with n","Multiset dimension: conjecture false, king grids fixed at 4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002906,"raw_usage":{"total_tokens":10987,"prompt_tokens":968,"completion_tokens":10019,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":9938}},"tokens_in":712,"tokens_out":10019,"duration_ms":72778,"temperature":1.0,"reasoning_tokens":9938,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T00:21:22.692383+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an independent exhaustive enumeration of all connected graphs of orders through 11 and compute dim_m exactly; if any graph outside the paper's eight satisfies dim_m = n, Theorem 1.1 collapses. Alternatively, find a three-landmark set that multiset-resolves P_5 ⊠ P_5 or any n ≥ 5, which would falsify Theorem 1.2.","supporting_citations":[],"review_version":1}