{"id":"079bf113-08a0-4e85-bd84-14d93967750c","arxiv_id":"2411.16548","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graphs satisfying a (lambda,mu)-bow metric are shown to be delta-hyperbolic for several major graph families, with bounds linear in lambda and mu.","lead":"This paper studies a metric condition called the (lambda,mu)-bow metric, a common generalization of hyperbolicity and the alpha_i-metric. It proves that graphs satisfying this condition have bounded hyperbolicity for several major graph families, while leaving the general case as an open conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reduction in §4.5 is the least secure step: Lemma 9 proves only the d_L(e_x,e_y)=λ case, and Theorem 6 imports [44, Thm 6] without verifying its hypotheses and constants.","rationale":"I re-checked the main proof chain behind Theorem 4. Proposition 8's quasi-median argument is intricate but the distance identities check out; Theorem 3, Lemma 4, and Corollary 1 do give δ≤2(λ+μ)+1 for meshed graphs. The CB-graph, modular/median, and Helly corollaries also follow from the stated lemmas without obvious gaps. The only place where the argument imports unverified, constant-sensitive results is the bipartite/line-graph reduction: Lemma 9 as written handles only equality of the overlap length, and Theorem 6 relies on [44, Theorem 6] and [44, p.194] without stating their hypotheses or proving the constants. This is a genuine load-bearing dependency, but it is not a demonstrated error, and it does not touch the strongest positive result for meshed graphs. Therefore the reader's ACCEPT verdict remains appropriate; the reduction should be patched with an explicit sub-overlap reduction and a precise statement of the [44] transfers.","tokens_in":26949,"tokens_out":48926,"duration_ms":447832,"concrete_test":"Run an exhaustive brute-force verification of Lemma 9 on all connected bipartite graphs up to 8 vertices, including overlaps of length λ+1: for each quadruple of edges e_u,e_x,e_y,e_v of L(G) with d_L(e_x,e_y)>λ−1 and e_x∈I(e_u,e_y), e_y∈I(e_x,e_v), check the claimed (λ−1,μ+2)-bow inequality for μ=0,1,2. Separately, recompute the [44] transfer inequalities δ(H)≤δ(L(H))+1 and δ(G)≤δ(Σ(G))/2 by a direct 4-point derivation for bipartite H; if the constants differ by more than an additive constant, Theorem 6 must be restated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 9 claims that a bipartite (λ,μ)-bow graph G has line graph L(G) satisfying (λ−1,μ+2)-bow, but its proof fixes d_{L(G)}(e_x,e_y)=λ. The property requires the inequality for every overlap longer than λ−1, i.e., also for d=λ+1,λ+2,... . A sub-overlap reduction exists (take the vertex at distance λ from e_y on the shortest e_x-e_y path), but it is not stated, and it must preserve the two interval conditions and the non-negativity of the converted distances. If any sign or parity slip enters there, Corollary 10 and Theorem 6 lose their base case. More importantly, Theorem 6 converts bounded hyperbolicity of L(H) back to H via [44, Theorem 6] (δ(H) ≤ δ(L(H))+1) and then to G via [44, p.194] (δ(G) ≤ δ(H)/2); neither inequality is proved or even stated inside this paper. The reduction's O(f(λ,μ)) dependence is exactly the additive +1 and factor 1/2 from [44], so the constants are load-bearing for the claimed reduction. This does not affect Theorem 4 (meshed graphs), whose proof via Proposition 8 and Corollary 1 is self-contained and appears sound; the concern bears only on the bipartite/line-graph route to the general conjecture.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the (λ,μ)-bow metric introduced by Dragan and Ducoffe, which generalizes both α_i-metrics and δ-hyperbolicity. The authors conjecture that, in graphs, a (λ,μ)-bow metric implies hyperbolicity bounded by a function of λ and μ. They prove this conjecture for meshed graphs (Theorem 4, giving δ ≤ 2(λ+μ)+1), for CB-graphs (Theorem 5), for pseudo-modular/Helly graphs (Corollary 8), for modular/median graphs (Corollary 9), and for graphs with bounded metric-triangle side length or bounded interval thinness (Theorem 1). They also show that several named classes, including AT-free graphs, graphs with bounded tree-length, and k-chordal graphs, satisfy bow metrics with small parameters. Finally, in Section 4.5, they reduce the general conjecture to bipartite graphs or to line graphs of bipartite graphs (Lemma 9, Theorem 6, Corollary 11).","tokens_in":27267,"tokens_out":25025,"duration_ms":213755,"significance":"If correct, the paper makes a substantial advance toward unifying α_i-metrics and hyperbolicity. The strongest self-contained result is Theorem 4 for meshed graphs, with an explicit linear bound δ ≤ 2(λ+μ)+1; since meshed graphs include weakly modular graphs, basis graphs of matroids, and many other classical metric graph classes, the scope is large. The intermediate tools, especially Proposition 8 and Corollary 1, are reusable and clean. The reduction of the general conjecture to bipartite graphs and line graphs of bipartite graphs is elegant and gives a clear target for future work. The paper is honest about the open case of bipartite graphs with λ ≥ 2, and no circularity is present: the conjecture is not assumed in the proofs. The main limitations are local proof gaps, the most significant being the incomplete proof of Lemma 9 in Section 4.5.","major_comments":[{"comment":"The proof of Lemma 9 fixes d_L(e_x,e_y)=λ, but the (λ−1, μ+2)-bow property requires the inequality for every overlap length d ≥ λ; as written, the cases d > λ are not proved. This is load-bearing because Corollary 10 and Theorem 6 rely on Lemma 9. The gap is repairable: if d>λ, let e_y' be the vertex on a shortest e_x-e_y path contained in a shortest e_u-e_y path with d(e_x,e_y')=λ; then (e_u,e_x,e_y',e_v) satisfies the assumptions of the λ-case, and substituting d(e_y',e_v)=d(e_y',e_y)+d(e_y,e_v)=d−λ+d(e_y,e_v) into the λ-case inequality yields exactly d(e_u,e_v) ≥ d(e_u,e_x)+d+d(e_y,e_v)−(μ+2). Please add this argument explicitly.","section":"Section 4.5, Lemma 9"}],"minor_comments":[{"comment":"The statement claims an 'if and only if,' but the proof only establishes that bounded hyperbolicity of L(H) implies bounded hyperbolicity of G; the converse is immediate because L(H) itself satisfies a (2λ+1,2μ+4)-bow metric, and it should be stated for completeness.","section":"Section 4.5, Theorem 6"},{"comment":"Please quote the exact inequalities from [44, Theorem 6] and [44, p.194] that transfer hyperbolicity between H and L(H) and between G and H; this would make the O(f(λ,μ)) dependence in the reduction fully transparent.","section":"Section 4.5, Theorem 6"},{"comment":"The reduction 'without loss of generality, d(v,w)=2' is valid but should be spelled out; one applies the d=2 case to the quadruple (u,v,v',x), where v' is the vertex at distance 2 from v on the v-w path, and uses d(v',x)=d(v,w)−2+d(w,x).","section":"Section 3, Proposition 4"},{"comment":"The step 'we may assume ... this cycle C is simple' needs a justification; as written, a closed walk formed by four shortest paths need not contain a simple cycle with the stated metric properties, and the subsequent chord argument depends on simplicity.","section":"Section 3, Proposition 6"},{"comment":"In the definition of ℓ, the equality d(x',y')=d(x',w') should read d(x',y')=d(y',w').","section":"Section 4.2, Lemma 4"},{"comment":"'A graphs G' should be 'A graph G'.","section":"Theorem 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the main meshed-graph theorem is convincing. The only substantive issue is the incomplete proof of Lemma 9 in Section 4.5, which is repairable with a short argument. I do not see circularity or scope problems; I would not reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper proves a real conjecture in several major graph classes: if a graph satisfies (λ,μ)-bow metric, then its hyperbolicity is bounded by a function of λ,μ, for meshed graphs, CB-graphs, modular/median/Helly graphs, and bipartite graphs with λ=1, plus a reduction of the general conjecture to bipartite or line graphs. The main bound for meshed graphs, δ ≤ 2(λ+μ)+1, is new and the proof via quasiconvex balls and equilateral metric triangles is largely self-contained. The paper also gives clean bow-metric bounds for tree-length, k-chordal, and AT-free graphs. This is a serious contribution, not a routine extension of [51].\n\nThe soft spots are mostly in the last subsection. Lemma 9, which transfers bow metric from a bipartite graph to its line graph, only writes the proof for overlap distance exactly λ. The property requires all overlaps longer than λ−1. A sub-overlap argument does work—pick the vertex at distance λ from one end and re-run the proof—but it is not stated, and the interval conditions need checking. That is an exposition gap, not a fatal flaw. The related Theorem 6 imports two inequalities from [44] without stating them: δ(H) ≤ δ(L(H))+1 and δ(G) ≤ δ(H)/2. The constants are load-bearing for the claimed O(f(λ,μ)) reduction. I could not verify that [44]'s hypotheses are met for the line graph of the 1-subdivision, though nothing in the setup suggests they are not.\n\nEarlier sections have a few terse \"without loss of generality\" steps (Prop 4 assumes d(v,w)=2; Prop 6 assumes a simple cycle) that a referee should ask to expand, but they look repairable. Theorem 4's proof is the core and it holds up.\n\nWho is this for? Metric graph theorists and people working on hyperbolicity in graph classes. It deserves a serious referee. I'd send it out with a request to expand the line-graph reduction and the WLOG steps. If those close, this should be accepted.","headline":"Solid, significant proof of the bow-metric/hyperbolicity conjecture for several major graph classes; the bipartite/line-graph reduction has fixable gaps.","tokens_in":27767,"tokens_out":4874,"would_cite":true,"duration_ms":43493,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"A short-path overlap inequality called the (λ,μ)-bow metric forces bounded hyperbolicity in major graph families, with the general case reduced to bipartite graphs.","keywords":["hyperbolicity","(λ,µ)-bow metric","α_i-metric","meshed graphs","weakly modular graphs","Helly graphs","metric triangles","interval thinness"],"falsifier":"One infinite family of graphs whose hyperbolicity grows without bound while each graph satisfies a $(\\lambda,\\mu)$-bow metric with fixed $\\lambda$ and $\\mu$ would refute the conjecture; by the paper's own Remark 1, any such family must have metric triangles of unbounded side length and unbounded interval thinness, so those two quantities are the concrete place to look. A direct check of the line graph of the 1-subdivision for such candidate graphs would also test the reduction step.","tokens_in":26797,"feed_emoji":"📐","tokens_out":13059,"duration_ms":107409,"temperature":0.7,"pith_summary":"The paper asks whether a purely metric condition on overlapping shortest paths forces a graph to be hyperbolic, meaning its large-scale distances behave like those of a tree. The condition, called a $(\\lambda,\\mu)$-bow metric, says that if two shortest paths overlap by more than $\\lambda$ edges, then the two far endpoints are at least as far apart as the path through the overlap, minus a constant $\\mu$. The authors conjecture that every graph satisfying this condition has hyperbolicity bounded in terms of $\\lambda$ and $\\mu$ alone. They prove the conjecture for meshed graphs, for graphs with convex balls, for modular, median and Helly graphs, and for bipartite graphs when $\\lambda=1$, giving explicit bounds such as $\\delta \\le 2(\\lambda+\\mu)+1$ for meshed graphs. They also show the general conjecture would follow from proving it for all bipartite graphs, equivalently for line graphs of bipartite graphs.","feed_headline":"Bow metric forces bounded hyperbolicity in major graph classes","feed_subtitle":"The paper proves the bow-metric conjecture for meshed, Helly, and bipartite graphs, with explicit bounds.","key_machinery":"The central object is the $(\\lambda,\\mu)$-bow metric itself, a four-point inequality on shortest-path overlaps. The proof strategy turns this inequality into two structural finiteness properties: metric triangles with bounded side length and intervals with bounded thinness. A metric triangle is a triple of shortest-path intervals that meet only at their endpoints; a quasi-median of three vertices is the metric triangle obtained by cutting back the three intervals until they touch. Once the bow metric bounds the side length of metric triangles and the thinness of intervals—for meshed graphs, for example, the bound is $3\\lambda+2\\mu+1$ on thinness and $\\lambda+2\\mu+1$ on triangle side length—known results (Proposition 7 and Proposition 8 in the paper) convert those two bounds into explicit hyperbolicity and slimness constants. A second mechanism is preservation under graph operations: the 1-subdivision of a $(\\lambda,\\mu)$-bow graph is $(2\\lambda+2,2\\mu+2)$-bow, and the line graph of a bipartite $(\\lambda,\\mu)$-bow graph is $(\\lambda-1,\\mu+2)$-bow, which is what reduces the general conjecture to bipartite graphs and to line graphs of bipartite graphs.","core_discovery":"The paper's central claim is that the $(\\lambda,\\mu)$-bow metric implies hyperbolicity in graphs, and it establishes the claim for several large families. For meshed graphs, which include weakly modular graphs, median graphs, Helly graphs, chordal graphs, distance-hereditary graphs and basis graphs of matroids, Theorem 4 gives $\\delta \\le 2(\\lambda+\\mu)+1$. For graphs with convex balls, Theorem 5 gives $\\delta \\le \\frac{5}{2}\\max\\{2,\\lambda+2\\mu+1\\}$; for pseudo-modular and Helly graphs, Corollary 8 gives $\\delta \\le \\max\\{(\\mu+1)/2,\\lambda+1\\}$; and for modular and median graphs, Corollary 9 gives $\\delta \\le \\max\\{\\mu/2,\\lambda\\}$. Bipartite graphs satisfying a $(1,\\mu)$-bow metric are shown to be hyperbolic with $\\delta \\le 3(\\mu+1)/2+4$. The general conjecture is reduced to bipartite graphs and to line graphs of bipartite graphs, so settling either of those cases would settle the conjecture for all graphs.","pith_inferences":["The reduction to line graphs of bipartite graphs makes the conjecture effectively a question about intersection graphs of edges in bipartite graphs; that structural restriction may be the most promising place to search for either a proof or a counterexample.","The explicit bounds in the paper are probably not tight; the rectilinear-grid examples used to show sharpness of several propositions suggest constructing meshed bow-metric graphs with hyperbolicity growing linearly in $\\lambda+\\mu$ to test Theorem 4.","Because Euclidean space satisfies the bow condition with $\\lambda=\\mu=0$ yet has unbounded hyperbolicity, the graph-only conjecture points to integrality of paths as the essential ingredient; one testable extension is whether the result survives for integer-weighted graphs or only for unweighted graphs.","If the conjecture is proved, it would unify the scattered hyperbolicity bounds for chordal, distance-hereditary, AT-free, tree-length, and Helly graph classes under one metric hypothesis, and it would automatically give additive distance-approximation algorithms for every bow-metric graph class."],"forward_implications":["Every meshed graph satisfying a $(\\lambda,\\mu)$-bow metric is hyperbolic with $\\delta \\le 2(\\lambda+\\mu)+1$, so all weakly modular subclasses (median, Helly, chordal, distance-hereditary) inherit an explicit bound whenever they satisfy the metric.","Graphs with convex balls satisfying a bow metric are hyperbolic with $\\delta \\le \\frac{5}{2}\\max\\{2,\\lambda+2\\mu+1\\}$, and pseudo-modular, modular, and median graphs get sharper constants from Corollaries 8 and 9.","Bipartite graphs satisfying a $(1,\\mu)$-bow metric are hyperbolic with $\\delta \\le 3(\\mu+1)/2+4$, extending the earlier $\\alpha_i$-metric hyperbolicity bound to this bipartite case.","The general conjecture is equivalent to proving the same statement for all bipartite graphs or for all line graphs of bipartite graphs; a proof for either class would settle the conjecture for every graph.","Since many classical classes—hyperbolic graphs, slim graphs, tree-length-bounded graphs, k-chordal graphs, and AT-free graphs—satisfy bow metrics with small parameters, the hyperbolicity bounds here apply to all of them through the bow-metric hypothesis."],"supporting_citations":[{"why":"Defines the (λ,µ)-bow metric and proves every δ-hyperbolic graph satisfies (δ,2δ)-bow, the starting point that makes the bow metric a common generalization of hyperbolicity and α_i-metrics.","marker":"[51]"},{"why":"Supplies the theorem that p-thin intervals plus bounded metric triangles force bounded slimness and hyperbolicity, which is the proof engine for converting bow-metric bounds into hyperbolicity.","marker":"[38]"},{"why":"Quoted theorem transferring hyperbolicity between a graph and its line graph; it is the load-bearing step in the bipartite and line-graph reductions of the conjecture.","marker":"[44]"},{"why":"Papasoglu's doubly exponential bound on hyperbolicity in terms of interval thinness of the 1-subdivision, used in Theorem 2 to turn interval-thinness bounds into hyperbolicity.","marker":"[76]"},{"why":"Source of the fact that meshed graphs have equilateral metric triangles, which underlies the structural bounds used for the meshed case.","marker":"[7]"},{"why":"Shows metric triangles in CB-graphs are strongly equilateral or of type (2,2,1), enabling the bounded-triangle and thinness arguments for graphs with convex balls.","marker":"[28]"},{"why":"Survey used for the definitions and class inclusions showing weakly modular graphs are meshed and that meshed graphs include many classical metric graph classes.","marker":"[10]"}],"fun_headline_variants":["Bow metric conjecture proven for key graph families","Bow metric implies hyperbolicity in many graphs","Hyperbolicity from bow metrics: new proofs","Bow metrics force hyperbolicity in meshed graphs","Bow metric to hyperbolicity: bounds for major classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the unproved general conjecture is true; the paper's route to it depends on a quoted theorem transferring hyperbolicity between a graph and its line graph, so if that transfer fails with the needed constants, the reduction of the conjecture to bipartite graphs collapses.","fun_headline_variants_meta":{"raw":{"variants":["Bow metric conjecture proven for key graph families","Bow metric implies hyperbolicity in many graphs","Hyperbolicity from bow metrics: new proofs","Bow metrics force hyperbolicity in meshed graphs","Bow metric to hyperbolicity: bounds for major classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000673,"raw_usage":{"total_tokens":3148,"prompt_tokens":1109,"completion_tokens":2039,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":725,"completion_tokens_details":{"reasoning_tokens":1966}},"tokens_in":725,"tokens_out":2039,"duration_ms":14229,"temperature":1.0,"reasoning_tokens":1966,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:00:29.746652+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One infinite family of graphs whose hyperbolicity grows without bound while each graph satisfies a $(\\lambda,\\mu)$-bow metric with fixed $\\lambda$ and $\\mu$ would refute the conjecture; by the paper's own Remark 1, any such family must have metric triangles of unbounded side length and unbounded interval thinness, so those two quantities are the concrete place to look. A direct check of the line graph of the 1-subdivision for such candidate graphs would also test the reduction step.","supporting_citations":[{"cited_title":"Dragan, G","cited_arxiv_id":null,"evidence_quote":"Defines the (λ,µ)-bow metric and proves every δ-hyperbolic graph satisfies (δ,2δ)-bow, the starting point that makes the bow metric a common generalization of hyperbolicity and α_i-metrics."},{"cited_title":"Chepoi, F.F","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that p-thin intervals plus bounded metric triangles force bounded slimness and hyperbolicity, which is the proof engine for converting bow-metric bounds into hyperbolicity."},{"cited_title":"Coudert, G","cited_arxiv_id":null,"evidence_quote":"Quoted theorem transferring hyperbolicity between a graph and its line graph; it is the load-bearing step in the bipartite and line-graph reductions of the conjecture."},{"cited_title":"Papasoglu, Strongly geodesically automatic groups are hyperbolic, Inventiones Math","cited_arxiv_id":null,"evidence_quote":"Papasoglu's doubly exponential bound on hyperbolicity in terms of interval thinness of the 1-subdivision, used in Theorem 2 to turn interval-thinness bounds into hyperbolicity."},{"cited_title":"Bandelt, V","cited_arxiv_id":null,"evidence_quote":"Source of the fact that meshed graphs have equilateral metric triangles, which underlies the structural bounds used for the meshed case."}],"review_version":1}