{"id":"a8b82379-a805-4a9e-9513-f0aa61c742bf","arxiv_id":"1908.05879","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every tree on n vertices with finite multiset dimension, the multiset dimension is at most n-2, and finite multiset dimension is characterized for caterpillars and lobsters.","lead":"This paper proves that any tree on n vertices with finite multiset dimension needs at most n-2 landmarks, improving the previously conjectured n-1 for trees. It also gives necessary and sufficient conditions for caterpillars and lobsters to have finite multiset dimension, partially answering an open problem from earlier work.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's even-order, odd-diameter case asserts an m-resolving set without proof; the both-centers-even subcase is particularly unverified.","rationale":"The reader's weakest assumption identifies exactly the even-order odd-diameter case of Theorem 1, where an m-resolving set is asserted without verification. My reading confirms that this is the most load-bearing gap: it is the sole step proving the upper bound n - 2 for a substantial family of trees. The text even contains an ambiguity about whether R' removes x, and the cardinality parity does not work as written if x is retained. This is a genuine proof gap, not merely a stylistic omission, so a conditional verdict is appropriate. However, I found no evidence that the theorem is false; the construction may be repairable, and the authors' exhaustive data for n <= 10 are consistent with the claimed bound. The lobster and caterpillar theorems have their own ambiguities, especially the S4 convention and the maximum-size resolving sets in (3)->(1), but those affect Theorem 2 and 3 rather than the headline bound. The paper's central contribution, Theorem 1, rests on the unproved even-order case, so the manuscript should be revised to supply the missing parity verification or a different construction before acceptance.","tokens_in":8948,"tokens_out":6418,"duration_ms":67101,"concrete_test":"Enumerate all trees of even order n <= 12 with odd diameter and both center degrees even (or, more broadly, all even-order odd-diameter trees), implement the construction of Case 2.2 exactly as written: R' = V(T) - N1 - N2, and also the natural corrected version R' = V(T) - {x} - N1 - N2. For each tree, compute the representation multiset of every vertex with respect to each candidate set and check whether the multiset representations are all distinct. If the written version fails but the corrected version succeeds, the gap is a fixable omission; if either version fails on some instance, the proposed construction is invalid and Theorem 1 requires a different argument for this case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1, Case 2.2, handles odd |T| explicitly, but the even |T| case is left as an unproved assertion. When one center has odd degree, the text removes the even-sized neighbor set N and claims R' = R - N is an m-resolving set 'as we already established in the previous cases,' yet the required parity argument is not carried out for this construction. When both centers have even degree, the text defines N1 and N2 and simply states that R' = V(T) - N1 - N2 'is the required new m-resolving set.' This is the only step that establishes md(T) <= n - 2 for even-order trees with odd diameter, so a gap here leaves the central theorem unproved in that case. Moreover, the notation is ambiguous: as written, R' = V(T) - N1 - N2 does not explicitly remove x, and its size is even, so the promised odd-cardinality parity contradiction cannot apply; if x is intended to be removed, the parity argument still needs to be redone for pairs of vertices in the same branch and different branches after deleting both N1 and N2. No counterexample is apparent, but the proof as written does not demonstrate that the proposed set is resolving.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript studies the multiset dimension md(G) of trees. The main result, Theorem 1, asserts that every tree T of order n and diameter at least 2 with finite multiset dimension satisfies md(T) <= n-2, improving the conjectured upper bound n-1 from [4] for trees. The proof distinguishes even and odd diameter, and within the odd-diameter case separates odd and even order. The authors also state necessary and sufficient conditions for lobsters (Theorem 2) and caterpillars (Theorem 3) to have finite multiset dimension, and they propose Conjecture 2, a sharp bound md(T) <= n - diam(T) + 1, supported by exhaustive computations for trees up to order 10.","tokens_in":9210,"tokens_out":5632,"duration_ms":47954,"significance":"If the main theorem and characterizations are correct, the paper settles Conjecture 1 from [4] for trees in a strengthened form and partially answers Open Problem 1. Theorem 2 is a structurally rich characterization of lobsters and would be a substantial contribution. The exhaustive search data in Table 1, generated with standard tools, provides useful evidence for Conjecture 2 even though the search does not itself constitute a proof. The proofs are direct derivations from the definitions and from basic lemmas in [4], with no apparent circularity. However, the proof of Theorem 1 has a load-bearing gap in the even-order, odd-diameter subcase, and the statement of Theorem 2 contains a definitional ambiguity about S4; both need to be repaired before the claims are fully established.","major_comments":[{"comment":"In the even-order, odd-diameter subcase of Theorem 1, the set R' = V(T) - N1 - N2 is asserted to be 'the required new m-resolving set' with no proof. The preceding parity argument for the odd-order case relied on |R'| being odd; here, as written, R' contains both centers x and y and has even cardinality, so the stated parity contradiction cannot apply. If the intended set is V(T) - {x,y} - N1 - N2, the text should say so and the resolution proof (for pairs in the same branch and in different branches) must be carried out for the deletion of both neighbor sets. Without this argument, the upper bound md(T) <= n-2 is not established for even-order trees of odd diameter.","section":"Theorem 1, Case 2.2"},{"comment":"The symbol S4 is used ambiguously. In Section 1, S4 denotes the star on four vertices; in condition (2), a component of G-E(P) that is an S4 has infinite multiset dimension by Lemma 1(4), while in condition (3), S4 appears as one of the allowable component types of [H]. These two uses are not reconciled, and the proof of (2)=>(3) says that an H with infinite multiset dimension 'is an S4 which fulfills (3)' without showing that an S4 component of G-E(P) yields components of [H] of the listed types. The equivalence of (2) and (3) is therefore not demonstrated as written.","section":"Theorem 2, conditions (2)-(3)"},{"comment":"The proof asserts as an unstated premise that for i=0 and i=n, the maximum resolving set R(Hi) contains a vertex at distance two from P because P is a minimum 2-center path. This is not proved, and it is load-bearing: the subsequent claim that the maximum element of rm(v|union R(Hi)) is ecc(v) depends on it. Without a proof that a vertex at distance two exists in each end component (or a modified construction), the parity arguments in both Constructions 1 and 2 do not go through.","section":"Theorem 2, proof of (3)=>(1)"}],"minor_comments":[{"comment":"The first paragraph of the proof contains the typo 'multiset dimention'; it should read 'multiset dimension'.","section":"Theorem 1, proof"},{"comment":"In the sentence 'If there exists a vertex vi in NH(v) with degree at least 4 then there is at least 3 leaves attached to u', the variable should be 'vi' rather than 'u'.","section":"Theorem 2, proof of (1)=>(2)"},{"comment":"The notation (d(v,x)+1)^{k-1} in the equation for rm(v|R) is not defined; clarify that it denotes a multiset with k-1 copies of the same distance.","section":"Theorem 1, Case 2.1"},{"comment":"The component ordering 'S4 > P3 > P2' is informal; define the order explicitly, for example by the number of vertices or by the maximum distance of a vertex in the component to the root.","section":"Theorem 2, Construction 1"},{"comment":"The statement that the bound is sharp is followed by one example tree; clarify whether sharpness means equality for infinitely many n or for all n, since the bound depends on both n and diameter.","section":"Conjecture 2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a serious graph theory paper with a real result, but the proof of Theorem 1 is not complete. The gap is exactly where the stress-test says it is: Case 2.2, when the tree has even order and odd diameter. The authors construct an m-resolving set by removing neighbor sets and then say 'as we already established in the previous cases' without doing the parity check. When both centers have even degree, the set R' = V(T)−N1−N2 as written has even cardinality, so the odd-cardinality parity argument cannot apply. If x was meant to be removed too, they still don't prove the resolver property. This is load-bearing: without it, the n−2 bound is unproved for that whole class of trees. I don't see a counterexample, so the result may well be true, but the written proof doesn't establish it.\n\nWhat's good: the n−2 bound improves the natural n−1 bound from [4], and the proof for the other cases is sound. The exhaustive search for n≤10 is a nice empirical check and is clearly separated from the proof; there's no circularity. Theorems 2 and 3 give necessary and sufficient conditions for lobsters and caterpillars to have finite multiset dimension, which is a legitimate partial answer to Problem 1. The self-citations to [4] are appropriate.\n\nThe soft spots beyond the gap: Theorem 2's condition (2) says the only 'bad' component of G−E(P) is an S4, but condition (3) talks about components of the separated graph [H] being P2, P3, or S4. The notation is used loosely, and the equivalence between (2) and (3) is not as clean as it should be. A careful referee will need to clarify this.\n\nBottom line: this deserves peer review, not desk rejection. The main idea is credible and the contribution is a real step in an established program. But I would not cite it in its current form until the even-order case is fixed. Send it to a referee who can check the construction carefully.\n\nBest,","headline":"The paper's n−2 bound for trees is plausible but the proof has a genuine gap in the even-order, odd-diameter case; the characterizations are a useful step.","tokens_in":9693,"tokens_out":5671,"would_cite":false,"duration_ms":48393,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For finite multiset dimension, every tree of order n is resolved by at most n−2 vertices.","keywords":["m-resolving set","multiset dimension","trees","caterpillars","lobsters","graph distances","center of a tree","resolving set"],"falsifier":"Enumerate all trees of orders 11 and beyond (the paper's tables stop at order 10) and compute their multiset dimensions; the first tree with finite multiset dimension and $md(T)=n-1$ or $md(T)=n$ would disprove Theorem 1. For the specific proof step, test the set $R'=V(T)-N_1-N_2$ in every even-order tree with odd diameter and look for two vertices with the same representation multiset.","tokens_in":8757,"feed_emoji":"🌳","tokens_out":10471,"duration_ms":95097,"temperature":0.7,"pith_summary":"Every tree $T$ with $n$ vertices, diameter at least $2$, and a finite multiset dimension satisfies $md(T)\\le n-2$. This proves, for trees, a conjecture that the universal upper bound is $n-1$, and improves it by one. The paper reaches the bound by showing that a smallest resolving set can always be shrunk below the full vertex set, using the center structure of trees and a parity argument. It also gives complete structural characterizations for the two restricted families: caterpillars and lobsters. These are the first tree families for which finiteness of the multiset dimension is decided by simple local conditions.","feed_headline":"Trees cap their landmark count at n−2","feed_subtitle":"Settles a graph conjecture for trees and yields simple tests for caterpillars and lobsters.","key_machinery":"The machinery consists of the representation multiset $r_m(v|W)$, the multiset of distances from $v$ to the landmarks in $W$, and an m-resolving set $W$, one that assigns distinct multisets to distinct vertices; $md(G)$ is the minimum size of such a set. The tree proofs lean on the formula $ecc(v)=\\mathrm{rad}(T)+d(v,C(T))$, which ties the largest distance from a vertex to its distance from the center, and on a parity count: in a tree of odd diameter, a vertex on one side of the central edge and a vertex on the other side have opposite distances to every third vertex, so the counts of landmarks at odd distance are interchanged. For caterpillars and lobsters, the operating objects are the minimum $k$-center-path and the separation $[H]$ obtained by subdividing every edge incident with the root of a component and deleting the root.","core_discovery":"On the paper's own terms, the central result is Theorem 1: if a tree $T$ of order $n$ and diameter at least $2$ has $md(T)<\\infty$, then $md(T)\\le n-2$. The proof starts from any resolving set, shows that the full vertex set can be replaced by the complement of the center (or, in the hard odd-diameter even-order case, by the complement of the two centers' neighbor sets), and then shows the remaining set still separates all vertices by their representation multisets. The paper further proves Theorem 2, a necessary-and-sufficient condition for a lobster to have finite multiset dimension in terms of the components left after removing its minimum 2-center path, and Theorem 3, the analogous condition for caterpillars: every vertex of the minimum 1-center path has at most two neighbors outside the path. Together these partially settle the open characterization problem for trees posed in [4].","pith_inferences":["Beyond the paper: the parity-counting device used in Theorem 1 should transfer to any bipartite graph with odd diameter and a trackable center structure, so the same deletion argument is a plausible route toward the general $n-1$ conjecture for bipartite graphs.","Beyond the paper: because the paper's exhaustive data stop at order 10, the first test of Conjecture 2 is a complete enumeration of trees of orders 11 and 12; if the conjectured bound $n-\\mathrm{diam}(T)+1$ is right, no tree of those orders should have dimension larger than that bound.","Beyond the paper: the separation-characterization method for lobsters suggests a recursive prescription for wider tree classes built from $k$-center paths, though the paper itself notes that applying the argument inductively to the size of the minimum center-path may be difficult."],"forward_implications":["Conjecture 1 from [4] is true for trees: every tree with finite multiset dimension has $md(T)\\le n-1$, and Theorem 1 sharpens this to $md(T)\\le n-2$.","Since no graph has multiset dimension 2, a non-path tree with finite multiset dimension must have dimension at least 3; Theorem 1 therefore confines its possible values to $1$ and the integers from $3$ through $n-2$.","A caterpillar has finite multiset dimension exactly when each vertex of its minimum 1-center path has at most two neighbors outside the path, so the condition can be read off from the spine.","A lobster has finite multiset dimension exactly when the components left after deleting its minimum 2-center path are each of a short resolvable shape, with the only allowed infinite one being a star $S_4$; this turns finiteness into a local check.","The restriction to a minimum 2-center path is essential: a non-minimum path can satisfy the component conditions while the lobster still has infinite multiset dimension."],"supporting_citations":[{"why":"Introduces the multiset dimension, supplies the lemmas on paths, diameter-2 graphs, and twin vertices, and states Conjecture 1 and Problem 1 that the paper addresses.","marker":"[4]"},{"why":"Gives the lemma on multiset-similar equivalence classes used to prove that three mutually twin vertices force infinite multiset dimension.","marker":"[2]"},{"why":"Underlies the exhaustive enumeration of all trees up to order 10, whose statistics support the proposed sharpened bound in Conjecture 2.","marker":"[3]"}],"fun_headline_variants":["Tree landmark bound: n−2 or infinite","Multiset dimension of trees capped at n−2","Trees: finite dimension means ≤ n−2","Lobsters and caterpillars get finite-dimension tests","New bound for tree multiset dimension"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main bound rests on the claim that in a tree with odd diameter and even order, deleting the two centers' neighbor sets leaves a landmark set that still distinguishes every vertex by distance multisets; if that separation claim fails, the $n-2$ upper bound is not established.","fun_headline_variants_meta":{"raw":{"variants":["Tree landmark bound: n−2 or infinite","Multiset dimension of trees capped at n−2","Trees: finite dimension means ≤ n−2","Lobsters and caterpillars get finite-dimension tests","New bound for tree multiset dimension"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":9.2e-05,"raw_usage":{"total_tokens":1265,"prompt_tokens":995,"completion_tokens":270,"prompt_tokens_details":{"cached_tokens":896},"prompt_cache_hit_tokens":896,"prompt_cache_miss_tokens":99,"completion_tokens_details":{"reasoning_tokens":198}},"tokens_in":99,"tokens_out":270,"duration_ms":4427,"temperature":1.0,"reasoning_tokens":198,"cache_read_input_tokens":896,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:03:06.578049+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all trees of orders 11 and beyond (the paper's tables stop at order 10) and compute their multiset dimensions; the first tree with finite multiset dimension and $md(T)=n-1$ or $md(T)=n$ would disprove Theorem 1. For the specific proof step, test the set $R'=V(T)-N_1-N_2$ in every even-order tree with odd diameter and look for two vertices with the same representation multiset.","supporting_citations":[{"cited_title":"Khemmani and S","cited_arxiv_id":null,"evidence_quote":"Gives the lemma on multiset-similar equivalence classes used to prove that three mutually twin vertices force infinite multiset dimension."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Underlies the exhaustive enumeration of all trees up to order 10, whose statistics support the proposed sharpened bound in Conjecture 2."}],"review_version":1}