{"id":"7920291e-78df-48b5-b807-70c13cb99a38","arxiv_id":"2502.02731","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The maximum fault-tolerant metric dimension for graphs with metric dimension k grows like 3^k, and analogous base-2 growth holds for edge and adjacency metric dimension.","lead":"This paper determines that the fault-tolerant metric dimension of a graph can grow exponentially at base 3 relative to the ordinary metric dimension, settling the true exponential base between prior upper and lower bounds. The same paper proves analogous growth results for edge, adjacency, and truncated metric dimension, and links an extremal graph problem to a decades-old problem in set theory.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the base-3 growth limit is supported by a correct lower-bound construction and a valid closed-neighborhood upper bound; remaining issues are minor and asymptotic.","rationale":"The central claim is the asymptotic identity lim_{k→∞} max_{G: dim(G)=k} log_3(ftdim(G))/k = 1. The upper-bound half is the closed-neighborhood construction of Theorem 2.7; checking the fault-tolerance argument, including the case where the added vertex equals the removed landmark, shows the proof is sound. The lower-bound half is the real risk, and I checked it directly. For a full-cell pair v=0α, w=1α with α having no zero digit, every vertex other than v, w, and s1 is equidistant to v and w: the center and all other leaves have distances 1 and 2, r1 is adjacent to both, and for i>1 the distances to s_i and r_i depend only on α_i. Thus the reader's weakest assumption is actually correct. The proof's count of undersized cells is loose but not harmful; the exact count supports the stated 3^{k−1}−k lower bound. The abstract's upper-bound typo, the k=1 degeneracy, and the Section 8 uncovered-coordinate wording are real defects but do not affect the asymptotic base. I therefore cannot identify a load-bearing concern about the limit formula, and the reader's conditional verdict remains appropriate without revision.","tokens_in":25096,"tokens_out":25832,"duration_ms":245946,"concrete_test":"For k=3 and k=4, enumerate all vertices x of J_k and all full-cell pairs (0α,1α), and compute dist(x,v) and dist(x,w) to verify that equality holds for every x outside {v,w,s1}. This O(k·3^{2k}) check settles the load-bearing resolvability claim. A secondary check is to confirm that exactly 3^{k−1}−k full cells remain after deleting the all-1s vertex and the k vertices with exactly one zero.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The suspected weakness in Theorem 2.8 does not land. For a full-cell pair v=0α and w=1α, where α has no zero, the center c and every other leaf are equidistant to v and w; r1 is adjacent to both; and for i>1, both s_i and r_i have equal distances to v and w because those distances depend only on α_i. Hence none of those vertices resolves the pair. Only s1, with distances 1 and 2 to v and w, and the two vertices themselves resolve v and w. Therefore every full cell forces at least one of its two 0/1-labelled vertices into any fault-tolerant resolving set. The count of full cells is also better than the proof states: exactly one cell loses two removed vertices and k−1 cells lose one, so |R|=3^{k−1}−k, matching the theorem's stated bound. The upper-bound construction in Theorem 2.7 is valid, with only a harmless misstatement when the added vertex equals the removed landmark. The genuine defects are presentational: the abstract's upper bound omits the additive k term, J_1 is a degenerate disconnected exception, and the Section 8 construction should say '2 or ∞' for uncovered coordinates. None of these changes the exponential base 3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies how large fault-tolerant versions of metric dimension can be relative to the original dimension. For standard metric dimension it proves ftdim(G) ≤ dim(G)(2+3^{dim(G)-1}) and constructs graphs J_k with dim(J_k)=k and ftdim(J_k) ≥ 3^{k-1}-k, yielding the limit lim_{k→∞} max_{G: dim(G)=k} log_3(ftdim(G))/k = 1. Analogous base-2 limits are proved for fault-tolerant edge metric dimension and adjacency dimension, and a base-3 limit is proved for k-truncated metric dimension for k ≥ 2. The paper also characterizes graphs with fault-tolerant dimension 2 or n for several variants, proves sharp degree bounds for vertices in resolving sets, and establishes an equivalence between the maximum clique number of graphs of edge metric dimension at most k and the Erdős–Kleitman problem on families with distinct pairwise unions.","tokens_in":25320,"tokens_out":34615,"duration_ms":301333,"significance":"If the results are correct, the paper closes a real gap by showing that the exponential base of fault-tolerant metric dimension is 3, improving on the previous base-5 upper bound and base-2 lower bound. The edge and adjacency analogues, and the truncated-metric extension, give a coherent picture in which the fault-tolerant exponential base matches the maximum-degree base. The constructive lower bounds are explicit and elementary, and the upper-bound method (closed neighborhood plus a bounded number of added vertices) is simple and likely to be reusable. The equivalence with the Erdős–Kleitman problem is a nice bridge between graph theory and extremal set theory. The paper's reliance on the first author's earlier theorems ([11], [12], [13]) is a standard use of established tools and does not appear circular.","major_comments":[{"comment":"The abstract states ftdim(G) ≤ dim(G)(1+3^{dim(G)-1}), but Theorem 2.7 proves only the weaker bound ftdim(G) ≤ dim(G)(2+3^{dim(G)-1}). The extra additive term arises because the proof adds one vertex u_s for each landmark s. Thus the abstract's advertised upper bound is not established by the manuscript, and the statement should be corrected to match the theorem (or the theorem must be strengthened). The asymptotic limit in Corollary 2.9 is unaffected by this correction.","section":"Abstract; Theorem 2.7"},{"comment":"The proof of Theorem 2.8 concludes that |T − {s1}| ≥ 3^{k-1} − k − 1 and then states the theorem's bound ftdim(J_k) ≥ 3^{k-1} − k. The inference appears to use |T| ≥ |T − {s1}| + 1, which is valid only if s1 ∈ T; the proof does not justify this. If s1 ∉ T, the same counting gives only |T| ≥ |R|. The gap is repairable: exactly one partition cell has size 1 and k−1 cells have size 2, so |R| = 3^{k-1} − k, and if s1 ∉ T then fault-tolerance forces both vertices of each full cell into T. As written, however, the proof is incomplete. The same 'remove the first landmark' issue appears in the proofs of Theorem 3.9 and Theorem 4.9, where it should be handled with the analogous case split.","section":"Theorem 2.8 proof (also Theorems 3.9 and 4.9)"}],"minor_comments":[{"comment":"The statement that J_k is connected with dim(J_k)=k fails for k=1: J_1 is a disjoint union of two edges, and dim(J_1)=2. Since only k ≥ 2 is used for the limits, the theorem should be stated for k ≥ 2 or include a separate treatment of k=1.","section":"Theorem 2.8; Abstract"},{"comment":"The sentence about r_i says the distance is 1 to both v and w when the common ith digit is 0 or 1; when the digit is 0, the distance is actually 2 via s_i. This does not affect the conclusion because the distances to v and w remain equal, but it should be corrected.","section":"Theorem 2.8 proof"},{"comment":"In the forward direction of Theorem 8.1, the distance-vector formulas for clique edges and for edges {u_i, v_j} assume every coordinate not in the relevant union has value 2. If an index appears in no subset of the family F, the corresponding vertex u_t is isolated and the coordinate is ∞, not 2. This should be stated; the distinctness argument is unaffected because differences only occur at coordinates belonging to some subset.","section":"Section 8, Theorem 8.1"},{"comment":"The proof says that a landmark v has one coordinate equal to 0 and the rest positive; for disconnected graphs the other coordinates may be infinite. The upper bound still holds, but the sentence should allow ∞.","section":"Theorem 7.4"},{"comment":"The notation is confusing: the proof uses S both for the resolving set {s1,...,sk} and for the set of non-center vertices in the copy of K1,3^k when it writes '|S| = 3^k − k − 1'. Also, in the final paragraph 'T − {u1}' should be 'T − {s1}'.","section":"Theorem 2.8 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct after the local fixes described in the major comments. The abstract overstates the main upper bound, and one central lower-bound proof needs a short case split. The reliance on the first author's earlier theorems is legitimate and is not a circularity concern. The paper fits the scope of math.CO and would be a solid contribution after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the take: the paper settles the exponential base for fault-tolerant metric dimension — it's 3, not the 5 from Hernando et al. or the 2 from Knor et al. That was a real open gap, and the resolution is clean. The same framework also gives base 2 for edge and adjacency dimension, base 3 for truncated dimension, and an equivalence between max clique with bounded edge metric dimension and the Erdős–Kleitman set-family problem.\n\nThe upper bound construction (closed neighborhood of a resolving set plus one extra vertex per landmark) is simple and works. The lower bound graph J_k is a smart ternary gadget; I checked the stress-test re-derivation and the counting in Theorem 2.8 is fine — exactly one size-3 cell loses two vertices, k−1 lose one, so |R| = 3^{k−1} − k, matching the theorem. The proof's intermediate 'at most k+1' is an off-by-one, but it's the harmless direction and the conclusion holds.\n\nThe soft spots are all presentational. The abstract claims ftdim(G) ≤ dim(G)(1+3^{dim−1}), but Theorem 2.7 proves dim(G)(2+3^{dim−1}). The abstract also says the lower bound is 3^{k−1}−k−1 while the theorem gives 3^{k−1}−k. J_1 is not connected, so the 'infinite family of connected graphs' needs k≥2 or a tweak. Section 8's construction says uncovered coordinates have distance 2; they can be ∞. That doesn't break the equivalence because ∞ is constant on the uncovered elements, but the text should say '2 or ∞.' There's also a typo in Theorem 2.8 where |S| should be |N|.\n\nNone of this changes the asymptotic result. The paper is honest about what it proves, the key limit follows from the stated bounds, and the dependence on prior work (including the first author's own papers) is legitimate — those are independent published tools.\n\nFor a reader: if you care about metric dimension variants or extremal set theory, this is worth your time. I'd bring it to reading group and I'd cite it. It deserves a proper referee; after the abstract and small fixes, it should be accepted.","headline":"The paper settles the exponential base for fault-tolerant metric dimension (it's 3) and proves a clean equivalence with the Erdős–Kleitman problem; the gaps are presentational, not mathematical.","tokens_in":25852,"tokens_out":7174,"would_cite":true,"duration_ms":62764,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fault-tolerant metric dimension grows exponentially with base 3, not 2 or 5, in the worst case.","keywords":["metric dimension","fault-tolerant metric dimension","edge metric dimension","adjacency dimension","truncated metric dimension","resolving set","Erdős–Kleitman problem","extremal graph theory"],"falsifier":"Compute the exact fault-tolerant metric dimension of $J_4$, the graph with $3^4$ leaves minus 5 plus the added $s_i,r_i$ vertices. The paper predicts $\\operatorname{ftdim}(J_4)\\ge 3^3-4-1=22$, so a fault-tolerant resolving set of size 21 or less would refute the lower-bound construction. More directly, check whether any vertex other than a pair of leaves with ternary labels $0abc$ and $1abc$ resolves that pair; the proof of Theorem 2.8 asserts that only the two leaves and $s_1$ do.","tokens_in":24886,"feed_emoji":"📏","tokens_out":7830,"duration_ms":68272,"temperature":0.7,"pith_summary":"Fault tolerance is expensive in metric dimension: if a graph needs $k$ landmarks to locate every vertex, it can need roughly $3^k$ landmarks before any one of them is allowed to fail. This paper proves that the worst-case exponential base is exactly 3, improving the previous upper bound of about $5^k$ and the previous lower bound of about $2^k$. The upper bound comes from enlarging any resolving set by its closed neighborhood, and the matching lower bound comes from a family of ternary-labeled stars $J_k$ in which every fault-tolerant resolving set must contain a vertex from almost every digit class. The same strategy yields the base-2 analogue for edge metric dimension and sharp bounds for adjacency, truncated, and local metric dimensions, and it connects the clique number of edge-metric-dimension-$k$ graphs to the Erdős–Kleitman problem on set families with distinct pairwise unions.","feed_headline":"Fault tolerance pushes metric dimension to exponential base 3","feed_subtitle":"New upper and lower bounds agree: the worst-case growth rate is 3^k, closing the gap between earlier base-5 and base-2 bounds.","key_machinery":"The upper bound is carried by the closed-neighborhood enlargement of a resolving set: from any resolving set $S$, take $S$ together with all neighbors of vertices in $S$, then add one extra vertex for each landmark to repair the single unresolved pair that can remain; the bound that a landmark in a resolving set of size $k$ has at most $3^{k-1}$ neighbors controls the total size. The matching lower bound is carried by the family $J_k$: a star $K_{1,3^k}$ whose leaves are labeled by distinct ternary strings of length $k$, plus vertices $s_i,r_i$ that read the $i$-th ternary digit. In $J_k$, two leaves whose labels agree except in the first digit (0 versus 1) are distinguished only by themselves and by $s_1$, which forces any fault-tolerant resolving set to spend one vertex on almost every one of the $3^{k-1}$ digit classes.","core_discovery":"The central discovery is that the largest possible fault-tolerant metric dimension among graphs of metric dimension $k$ grows like $3^k$ up to subexponential factors, i.e. $\\lim_{k\\to\\infty}\\frac{\\log_3(\\max_{G:\\dim(G)=k}\\operatorname{ftdim}(G))}{k}=1$. Toward this limit, the paper proves $\\operatorname{ftdim}(G)\\le \\dim(G)(2+3^{\\dim(G)-1})$ for every graph of order greater than 1, improving the long-standing base-5 upper bound, and constructs connected graphs $J_k$ with $\\dim(J_k)=k$ and $\\operatorname{ftdim}(J_k)\\ge 3^{k-1}-k-1$, forcing the matching base-3 lower bound. The same machinery proves the analogous base-2 limit for fault-tolerant edge metric dimension and yields sharp extremal bounds for adjacency dimension and $k$-truncated metric dimension, together with characterizations of when the fault-tolerant values equal 2 or $n$.","pith_inferences":["The pattern in the paper suggests a general principle: for a metric-dimension variant whose maximum degree grows like $c^k$, the fault-tolerant version should have worst-case exponential base $c$; Section 9 asks exactly when this principle can fail, and the base-5-to-3 correction here shows why the principle needs proof rather than analogy.","The equivalence with the Erdős–Kleitman problem is two-way: any set family with more than about $(8/3)^{k/6}$ members having distinct pairwise unions would immediately produce edge-metric-dimension-$k$ graphs with larger cliques, and any upper-bound technique for such cliques would transfer back to set families.","A testable extension is to restrict to trees or bounded-degree graphs: the exponential lower-bound graphs are high-degree stars, so fault-tolerant metric dimension may grow only polynomially in $k$ on trees, and computing it for path and star families would show whether the $3^k$ phenomenon is driven by high degree."],"forward_implications":["For every graph $G$, a fault-tolerant resolving set of size at most $\\dim(G)(2+3^{\\dim(G)-1})$ always exists, and the exponential base 3 cannot be lowered because the graphs $J_k$ require roughly $3^{k-1}$ vertices in any fault-tolerant resolving set.","The analogous limit for edge metric dimension holds with base 2: the largest fault-tolerant edge metric dimension among graphs of edge metric dimension $k$ grows like $2^k$.","For $k$-truncated metric dimension with $k\\ge 2$, the fault-tolerance base is again 3; for adjacency dimension, the 1-truncated case, the base is 2.","In every variant considered, a fault-tolerant resolving set of size 2 exists exactly when the ordinary resolving set has size 1, and the paper gives neighborhood conditions under which the fault-tolerant value equals the order $n$.","The maximum clique number of a graph of edge metric dimension at most $k$ equals the Erdős–Kleitman function $ek(k)$, so any improvement on $ek(k)$ transfers directly to that extremal graph problem."],"supporting_citations":[{"why":"Introduced fault-tolerant metric dimension and gave the earlier base-5 upper bound that this paper improves.","marker":"[18]"},{"why":"Provided the first exponential lower bound, $\\operatorname{ftdim}=\\dim+2^{\\dim-1}$, which the new base-3 construction supersedes.","marker":"[22]"},{"why":"Supplies the maximum-degree bound $3^k-1$ and the $D_k$ embedding lemma used in the upper bound and extremal results.","marker":"[12]"},{"why":"Contains the earlier construction that the $J_k$ family is very similar to, and the $H_k$ family used for edge metric dimension lower bounds.","marker":"[11]"},{"why":"The Erdős–Kleitman extremal set problem that the paper proves equivalent to the clique number of edge-metric-dimension-$k$ graphs.","marker":"[5]"}],"fun_headline_variants":["Metric dimension's fault-tolerant worst case pinned to 3^k","Fault-tolerant metric dimension: exponential base 3 confirmed","Base-3 growth for fault-tolerant metric dimension proven","Worst-case fault-tolerant metric dimension grows like 3^k","New bounds set fault-tolerant metric dimension to 3^k"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound construction rests on the assertion that in $J_k$, a pair of leaves whose ternary labels agree except in the first digit (0 and 1) is resolved only by the two leaves themselves and by $s_1$; if any additional vertex also distinguished such a pair, the $3^{k-1}$ lower bound would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Metric dimension's fault-tolerant worst case pinned to 3^k","Fault-tolerant metric dimension: exponential base 3 confirmed","Base-3 growth for fault-tolerant metric dimension proven","Worst-case fault-tolerant metric dimension grows like 3^k","New bounds set fault-tolerant metric dimension to 3^k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000969,"raw_usage":{"total_tokens":4278,"prompt_tokens":1259,"completion_tokens":3019,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":875,"completion_tokens_details":{"reasoning_tokens":2951}},"tokens_in":875,"tokens_out":3019,"duration_ms":20826,"temperature":1.0,"reasoning_tokens":2951,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:20:26.164680+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact fault-tolerant metric dimension of $J_4$, the graph with $3^4$ leaves minus 5 plus the added $s_i,r_i$ vertices. The paper predicts $\\operatorname{ftdim}(J_4)\\ge 3^3-4-1=22$, so a fault-tolerant resolving set of size 21 or less would refute the lower-bound construction. More directly, check whether any vertex other than a pair of leaves with ternary labels $0abc$ and $1abc$ resolves that pair; the proof of Theorem 2.8 asserts that only the two leaves and $s_1$ do.","supporting_citations":[{"cited_title":"Hernando, M","cited_arxiv_id":null,"evidence_quote":"Introduced fault-tolerant metric dimension and gave the earlier base-5 upper bound that this paper improves."},{"cited_title":"Fault tolerance of metric basis can be expensive","cited_arxiv_id":"2410.03656","evidence_quote":"Provided the first exponential lower bound, $\\operatorname{ftdim}=\\dim+2^{\\dim-1}$, which the new base-3 construction supersedes."},{"cited_title":"Geneson, S","cited_arxiv_id":null,"evidence_quote":"Supplies the maximum-degree bound $3^k-1$ and the $D_k$ embedding lemma used in the upper bound and extremal results."},{"cited_title":"Geneson, Metric dimension and pattern avoidance in g raphs","cited_arxiv_id":null,"evidence_quote":"Contains the earlier construction that the $J_k$ family is very similar to, and the $H_k$ family used for edge metric dimension lower bounds."},{"cited_title":"Erd˝ os, D.J","cited_arxiv_id":null,"evidence_quote":"The Erdős–Kleitman extremal set problem that the paper proves equivalent to the clique number of edge-metric-dimension-$k$ graphs."}],"review_version":1}