{"id":"1ae1fa86-b51b-4f12-b2d6-8b83f96c2b72","arxiv_id":"2607.07809","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The separation profile of any δ-hyperbolic planar or apex-minor-free graph grows at most as C log n, answering Benjamini–Schramm–Timár affirmatively.","lead":"Hyperbolic planar graphs (and more generally hyperbolic apex-minor-free graphs) have separation profiles that grow at most logarithmically. This settles a 2012 question of Benjamini–Schramm–Timár and gives a coarse-geometric obstruction tool with explicit constants in the planar case.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript answers a concrete open question of Benjamini–Schramm–Timár with two complete, self-contained proofs. The only non-trivial intermediate step is the efficient-hull construction of Proposition 4.2; its size and quasi-isometry constants are derived explicitly from 8δ-slimness of quadrilaterals and require no external black-box beyond the classical stability of hyperbolicity. The planar argument never uses the hull and yields an explicit linear dependence on δ, giving an independent verification of the same asymptotic statement. Constants are acknowledged to be non-optimal, but the asymptotic claims are unaffected. Pure-mathematics character makes independent checking straightforward; no formal-verification gap or unstated hypothesis remains. The reader’s ACCEPT verdict with high confidence is therefore left unchanged.","tokens_in":13677,"tokens_out":642,"duration_ms":6969,"concrete_test":"Independently recompute the diameter bound for bags in Proposition 3.2 from Gromov’s tree-approximation inequality (1) alone: verify that d_T(f(x),f(y)) ≤ 1 for any two vertices of a bag forces d_Γ(x,y) ≤ 1 + 2δ log_{2} n, and that the same numerical constant appears when the loaded-cycle lower bound of Lemma 5.9 is inserted into the planar argument of Theorem B.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption flag on Proposition 4.2 is the natural place to look, but the construction is self-contained and the estimates close. After adding all pairwise geodesics one obtains |V(Y)| ≤ n^{3} and the 8δ-slimness of geodesic quadrilaterals (Lemma 2.1) places every ambient geodesic between points of Y inside the 8δ-neighbourhood of Y. The second enlargement therefore only needs geodesics of length ≤ 16δ+1, producing the stated |V(F)| ≤ (16δ+3)n^{6} bound and a (δ-dependent) quasi-isometric embedding into Γ. Hyperbolicity of F then follows from the standard stability lemma (Lemma 4.1). The subsequent appeal to Coudert–Ducoffe–Nisse (Theorem 4.3) and the weighted-centroid separator (Lemmas 4.4–4.5) is routine. The planar route (Proposition 3.2 + geodesic loaded cycles inside grid minors) is independent and supplies an explicit linear-in-δ bound. No hidden hypothesis or gap appears to threaten either theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that the separation profile of any connected δ-hyperbolic apex-minor-free graph grows at most logarithmically (Theorem A), answering Question 4.5 of Benjamini–Schramm–Timár. For the special case of planar graphs it supplies the explicit bound sep_Γ(n) ≤ 60 + 120 δ log_{2} n (Theorem B). The first proof constructs an efficient hull F of any finite connected subgraph H with |V(F)| = O_δ(n^{6}) that is quasi-isometrically embedded (hence uniformly hyperbolic), obtains logarithmic tree-length via Gromov tree approximation, converts to logarithmic tree-width by the Coudert–Ducoffe–Nisse theorem for apex-minor-free graphs, and extracts a balanced separator. The second proof works with the grid profile of planar graphs, produces a tree-decomposition whose bags have ambient diameter O(δ log n), and uses geodesic loaded cycles inside large grid minors (via the Jordan curve theorem) to force a matching lower bound on bag diameters, yielding the linear-in-δ constant.","tokens_in":13942,"tokens_out":920,"duration_ms":9636,"significance":"The result settles a natural open question posed in the foundational paper on separation profiles and extends the known logarithmic bound from the hyperbolic plane itself to all hyperbolic planar graphs and, more broadly, to hyperbolic apex-minor-free graphs. The two independent proofs give complementary strengths: Theorem A covers a larger class of graphs, while Theorem B supplies an explicit linear dependence on the hyperbolicity constant. The efficient-hull construction (Proposition 4.2) and the controlled tree-decomposition of Proposition 3.2 are clean and potentially reusable. The paper also recovers, as a corollary, logarithmic tree-width bounds for subgraphs of such graphs, extending earlier results of Chepoi et al. and Dieng–Gavoille.","major_comments":[],"minor_comments":[{"comment":"The constant 60 + 120 δ appearing in Theorem B is obtained by chaining several crude estimates (n/4 for the load, /3 from Berger–Seymour, factor 5 from the grid-to-tree-width conversion). A short remark that the constants are not claimed to be optimal, and that modest improvements are possible by tightening the choice of the interior cycle or the load fraction, would be helpful.","section":"Theorem B / §5.3"},{"comment":"In the proof of Proposition 4.2 the bound |V(Y)| ≤ n^{3} is written as n + (n choose 2)n; the slightly cleaner estimate |V(Y)| ≤ n^{3}/2 + n is available and would improve the final polynomial degree by a constant factor, though this is purely cosmetic.","section":"Proposition 4.2"},{"comment":"Figure 1 is referenced but the caption is minimal; a one-sentence description of the four sides of the geodesic quadrilateral would make the 8δ-slimness argument easier to follow on a first reading.","section":"Figure 1"},{"comment":"The date line reads “8th July 2026”; this is presumably a typographical error for 2025 or 2024 and should be corrected.","section":"Front matter"},{"comment":"A brief forward reference in the introduction to the open question on the cut-width profile (mentioned at the end of §1) would better motivate why the authors work with vertex separators rather than edge separators throughout.","section":"§1"}],"recommendation":"accept","confidential_remarks":"The manuscript is clean, self-contained and answers a well-known question with two independent proofs. I see no reason to delay acceptance; the minor points listed above can be handled at the copy-editing stage."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the Benjamini–Schramm–Timár question: hyperbolic planar graphs (and more generally hyperbolic apex-minor-free graphs) have logarithmic separation profiles. Theorems A and B are the statements you will actually use; the planar bound is explicit and linear in δ (60 + 120δ log n).\n\nWhat is new is the combination of Gromov tree approximation with two different ways of handling subgraphs that need not themselves be hyperbolic. The efficient-hull construction (Prop. 4.2) enlarges a connected n-vertex subgraph to a uniformly quasi-isometrically embedded F of size O(δ n^6) that is still Δ_δ-hyperbolic; tree-length is then logarithmic, Coudert–Ducoffe–Nisse converts that to tree-width for apex-minor-free graphs, and a weighted centroid gives the separator. The planar route is independent: the same tree approximation produces bags of ambient diameter O(δ log n), and geodesic loaded cycles extracted from large grid minors force those bags to be large, yielding the grid-profile bound and hence the separation bound via Dvořák–Norin. Both arguments are written out completely; the slim-quadrilateral estimates and the quasi-isometry constants close without gaps.\n\nThe only soft spots are the ones the authors already flag: the polynomial degree in the hull and the absolute constants are not optimised. That does not touch the asymptotic claims or the linear dependence on δ in the planar case. Citations are standard and the logic is non-circular.\n\nThis is for people who work with Poincaré profiles, coarse embeddings, or tree-width of hyperbolic graphs. It is short, self-contained, and immediately usable. Send it to referees; it should be accepted after routine polishing of constants if anyone cares.","headline":"Clean affirmative answer to the BST question on logarithmic separation profiles for hyperbolic planar (and apex-minor-free) graphs, with two independent proofs and usable constants.","tokens_in":14544,"tokens_out":466,"would_cite":true,"duration_ms":5129,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C83","20F67","51F30"],"pacs":[],"model":"grok-4.5","headline":"Hyperbolic planar and apex-minor-free graphs have at most logarithmic separation profiles.","keywords":["separation profile","hyperbolic graphs","planar graphs","apex-minor-free","tree-width","tree approximation","grid profile"],"falsifier":"Exhibit a single infinite hyperbolic planar graph (or apex-minor-free graph) that contains finite subgraphs on n vertices whose balanced vertex separators must grow faster than any constant multiple of log n.","tokens_in":14587,"feed_emoji":"📐","tokens_out":579,"duration_ms":5462,"temperature":0.7,"pith_summary":"The paper answers a question of Benjamini, Schramm and Timár by proving that every hyperbolic planar graph has a separation profile that grows at most like a constant times the logarithm of n. The same logarithmic bound holds more generally for every connected graph that is hyperbolic and excludes a fixed apex graph as a minor. Separation profiles measure how hard it is to cut finite subgraphs into pieces of half-size or smaller by removing vertices; they are monotone under regular maps and therefore obstruct coarse embeddings. The authors obtain an explicit linear dependence on the hyperbolicity constant in the planar case, and they deduce a matching logarithmic bound on the tree-width of every finite subgraph of such a graph.","feed_headline":"Hyperbolic planar graphs separate only logarithmically","feed_subtitle":"Finite subgraphs of hyperbolic apex-minor-free graphs admit log-size balanced cuts","key_machinery":"An efficient hull (Proposition 4.2) that enlarges any finite connected subgraph H of a δ-hyperbolic graph to a uniformly quasi-isometrically embedded subgraph F of size O(n⁶); F is then uniformly hyperbolic, so Gromov’s tree-approximation lemma supplies a tree-decomposition of logarithmic ambient diameter that converts into a logarithmic separator via apex-minor-free tree-width control.","core_discovery":"Every connected δ-hyperbolic graph that excludes a fixed apex graph A as a minor has separation profile at most C(A,δ) log₂(n+1). In the special case of planar graphs the constant may be taken linear in δ: sep_Γ(n) ≤ 60 + 120 δ log₂ n.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Logarithmic separation profiles for hyperbolic planar graphs","Hyperbolic apex-minor-free graphs admit only log-size cuts","Sep profiles grow at most logarithmically in hyperbolic planar graphs","δ-hyperbolic apex-minor-free graphs separate like O(log n)","Balanced log-size cuts for hyperbolic planar and apex-minor-free graphs"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The hull construction must keep the enlarged subgraph only polynomially larger than the original finite piece while still quasi-isometrically embedding it into the ambient hyperbolic graph.","fun_headline_variants_meta":{"raw":{"variants":["Logarithmic separation profiles for hyperbolic planar graphs","Hyperbolic apex-minor-free graphs admit only log-size cuts","Sep profiles grow at most logarithmically in hyperbolic planar graphs","δ-hyperbolic apex-minor-free graphs separate like O(log n)","Balanced log-size cuts for hyperbolic planar and apex-minor-free graphs"]},"model":"grok-4.5","effort":"low","cost_usd":0.00482,"raw_usage":{"total_tokens":1240,"prompt_tokens":559,"num_sources_used":0,"completion_tokens":93,"cost_in_usd_ticks":48200000,"prompt_tokens_details":{"text_tokens":559,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":588,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":559,"tokens_out":93,"duration_ms":5413,"temperature":1.0,"reasoning_tokens":588,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T17:37:30.039939+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a single infinite hyperbolic planar graph (or apex-minor-free graph) that contains finite subgraphs on n vertices whose balanced vertex separators must grow faster than any constant multiple of log n.","supporting_citations":[],"review_version":1}