{"id":"a1a6ecb4-5a07-48ce-8728-837a3fe49ea6","arxiv_id":"2507.20833","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For a finite connected graph with the boundary set ∂G from [57], the paper proves analogues of Pólya's hitting-time bound, Faber-Krahn, Hardy, Alexandrov-Bakelman-Pucci, hot spots stability, and Björck's theorem.","lead":"This paper studies a recently proposed definition of the boundary of a finite graph and proves six analogues of classical potential-theory results, including random walk hitting times, eigenvalue bounds, Hardy inequalities, and energy maximization. A generalist might read it because it suggests that this graph boundary behaves like the Euclidean boundary of a domain, bridging discrete and continuous analysis.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 2 and 5 rest on an unproved tail-transfer from the reduced distance walk to the original graph walk; Theorem 5 also has an invalid final algebraic step.","rationale":"The paper's program is clear: prove six discrete analogues to show that the boundary from [57] behaves like a Euclidean boundary. Theorems 1, 3, 4, and 6 have arguments that are essentially sound, and I do not see a circularity problem: the inequalities are derived rather than assumed, and the only external input is the boundary definition. The genuine soft spot is exactly where the reader located it. The proof of Theorem 2 needs a quantitative upper bound on the probability that the original graph walk has not hit the boundary after k steps. Lemma 1 bounds the number of b-jumps needed to exit, but the graph walk can spend many steps between jumps. The paper simply asserts the exponential tail transfers with no dmax in the exponent, and the displayed factor of max_v deg(v) does not fix this. Moreover, Theorem 5's final step is algebraically invalid, so the hot-spots stability estimate is not proved by the text. Because the central claim depends on the collective validity of the six theorems, these two unproved steps constitute a real load-bearing concern. I would keep the reader's CONDITIONAL verdict: the paper is promising and much of it is correct, but Theorems 2 and 5 need repair or a clarified argument before the central claim can be accepted.","tokens_in":20058,"tokens_out":17574,"duration_ms":211610,"concrete_test":"Write out the missing stochastic domination lemma: for the graph walk started at v0, prove P(tau > k) <= C 2^{-c k/(Delta diam(G)^2)} with Delta = max_v deg(v), and redo the k->infinity step in Theorem 2 and the algebra in Theorem 5. If the only valid exponent contains Delta, then the stated constants of Theorems 2 and 5 are not consequences of the given proof. To test whether the theorems themselves survive, compute lambda_1(L_2) on a family with Delta >> min_v deg(v), such as a spider graph with m arms of length L, and compare the value with (1/4) min_v deg(v)/diam(G)^2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is in the proofs of Theorems 2 and 5, which share an unjustified passage from Lemma 1 to the original graph walk. Lemma 1 controls the number of sign-changing jumps (the b-process) needed to exit the interval {-D,...,D}, but the quantity to be bounded is the number of graph steps before hitting the boundary. Between two b-jumps the graph walk may spend an arbitrarily long time at vertices of the same distance from the starting point; at a vertex of degree Delta this holding time has mean about Delta/2. A correct stochastic domination argument gives a tail bound with exponent k/(2 Delta diam(G)^2), not k/(2 diam(G)^2) as written in Section 5. The factor 4 max_v deg(v) in the displayed inequality does not repair the exponent, and letting k go to infinity preserves the error. Consequently, the proof as written yields lambda_1(L_2) >= c min_v deg(v)/(Delta diam(G)^2), which is weaker than the stated constant in Theorem 2 by a factor of Delta. Theorem 5 repeats the same transfer and then makes an additional algebraic error: from A^k f(v0) <= (M + f(v0))/2 it concludes f(v0) <= A^{-k} M, whereas the correct rearrangement is f(v0) <= M/(2A^k - 1), which requires 2A^k > 1 and is not guaranteed. These two unproved links mean that two of the six advertised analogues are not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript defines a boundary set ∂G for a finite connected graph: a vertex v lies in ∂G if some vertex w has the property that the average distance from the neighbors of v to w is strictly smaller than d(v,w). It then states and proves six discrete analogues of classical potential-theoretic results: the Pólya-type random-walk hitting-time bound, Faber-Krahn, Hardy, Alexandrov-Bakelman-Pucci, a hot-spots stability estimate, and Björck's theorem. The intended claim is that ∂G plays for graphs the role that the Euclidean boundary plays for compact domains in PDE theory. The proofs are elementary and mostly self-contained; in my reading, four of the six arguments (Theorems 1, 3, 4, and 6) are sound, while the proofs of Theorems 2 and 5 contain nontrivial gaps that affect the advertised conclusions.","tokens_in":20388,"tokens_out":12234,"duration_ms":130211,"significance":"If fully established, the six theorems would form a coherent body of evidence that ∂G is the natural potential-theoretic boundary for finite graphs, and the paper would be a useful contribution to discrete analysis. The Hardy inequality (Theorem 3) and the Björck-type result (Theorem 6) are proved by clean, explicit arguments; Theorem 1 gives the expected quadratic hitting-time bound; and Theorem 4 has a correct ABP-type estimate with explicit constants. The main value is the unified picture: several classical PDE statements, each normally proved by different methods, are shown to hold with the same boundary notion. However, the two gaps identified below leave that package incomplete as it stands. They do not undermine the results whose proofs are sound, but they do affect two of the six central claims, so the paper is not ready for acceptance in its current form.","major_comments":[{"comment":"The passage from Lemma 1 to the original graph walk is unjustified. Lemma 1 bounds the number of sign changes of the distance process (the b-walk) needed to exit an interval, but the quantity μ_k(V\\∂G) in the proof is the probability that the original graph walk has not hit ∂G after k actual steps. Between two b-jumps the walk may spend arbitrarily many graph steps at the same distance, and the displayed factor max_v deg(v) in the inequality (1-q)^k ≤ 4 max_v deg(v) 2^{-k/(2 diam(G)^2)} does not repair the exponent, because it does not convert a bound in the number of b-jumps into a bound in the number of graph steps with the same k. A correct stochastic domination argument would yield an exponent of order k/(max_v deg(v) diam(G)^2), giving only λ_1(L_2) ≥ c min_v deg(v)/(max_v deg(v) diam(G)^2) rather than the stated λ_1(L_2) ≥ (1/4) min_v deg(v)/diam(G)^2. Since the Faber-Krahn statement is one of the paper's central advertised analogues, the theorem is not established as stated.","section":"Section 5, proof of Theorem 2"},{"comment":"The final algebraic step is invalid. From A^k f(v_0) ≤ (M + f(v_0))/2, with A = 1 - λ_2/min_v deg(v), the correct rearrangement is f(v_0) ≤ M/(2A^k - 1), not f(v_0) ≤ A^{-k} M; the latter is a stronger bound and does not follow. Moreover, if 2A^k ≤ 1, the displayed inequality gives no upper bound on f(v_0) at all, and nothing in the proof guarantees 2A^k > 1 for the chosen k. In addition, the iterated inequality (1 - λ_2/min_v deg(v)) f(v_k) ≤ E[f(v_{k+1}) | v_k] is only valid when f(v_k) ≥ 0; the second eigenfunction generally changes sign on V\\∂G, so the transition from the eigenvalue equation to A^k f(v_0) ≤ E f(v_k) requires an additional argument that is not supplied. The proof also uses k = 2 max_v diam(G)^2, whereas Theorem 4 and Theorem 1 require k = 2 max_v deg(v) diam(G)^2 to guarantee that half the walk has hit the boundary.","section":"Section 7.3, proof of Theorem 5"}],"minor_comments":[{"comment":"The displayed value k = 2 max_v diam(G)^2 appears inconsistent with Theorem 4, where k = 2 max_v deg(v) diam(G)^2 is used; the discrepancy changes the exponent in the claimed bound and should be corrected.","section":"Section 7.3"},{"comment":"The phrase 'letting k→∞' is misleading: the subsequent inference 2^{1/(2 diam(G)^2)} ≤ 1/(1-q) is valid only if the tail bound has been proved for the original graph walk with a constant independent of k, which is exactly the missing step identified above.","section":"Section 5"},{"comment":"The displayed line 'i = d(v,w) > 1/deg(v) sum ...' contains a typographical artifact (a stray '>' sign) that should be cleaned up.","section":"Proposition 1"},{"comment":"The manuscript contains no numbered equations, which makes it unnecessarily difficult to cite specific steps; adding equation numbers would improve verifiability.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The two gaps are localized but affect two of the six advertised theorems. The other four results are, in my assessment, sound and interesting. I would support publication if Theorem 2 is repaired (possibly with a max-degree factor in the constant) and Theorem 5 is either given a correct proof with a modified constant or stated with the weaker bound that the proof can actually support. I see no circularity problem: the boundary notion comes from the author's earlier paper [57], but the theorems here are new statements about that object. The author should also check the sign issue in the hot-spots proof, since the second eigenfunction is not nonnegative on the interior."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two of the six advertised theorems are not proven as written; the other four look right, and the paper deserves a serious referee. The program is clear: take the boundary ∂G from [57] and show it supports Dirichlet-type analogues of classical potential theory. Theorems 1, 3, 4, and 6 are genuine new results and their proofs are mostly clean. Theorem 1's Wald argument is a bit loose but can be made rigorous. Theorem 3 is a nice application of the Agmon-Allegretto-Piepenbrink machinery to the expected hitting time. Theorem 4 follows from Theorem 1 via Markov. Theorem 6's rearrangement argument is careful and works.\n\nThe soft spots are in Theorems 2 and 5. Both proofs need to bound the probability that the original graph walk has not hit ∂G after k steps. Lemma 1 bounds the number of sign-changing jumps of the distance process (the b-process), not the number of graph steps. Between two b-jumps the walk can idle at vertices of high degree for a long time. A correct transfer gives a tail with k/(Δ diam²) in the exponent, not k/(2 diam²); the prefactor 4Δ in the paper's display does not fix that. So Theorem 2's lower bound on λ1(L2) has not been established. Theorem 5 repeats the same transfer and then makes an algebraic error: from A^k f(v0) ≤ (M+f(v0))/2, the conclusion is f(v0) ≤ M/(2A^k − 1), not f(v0) ≤ A^{−k} M; the denominator can even be negative at the chosen k = 2Δ diam². These are load-bearing, not cosmetic.\n\nThe hot-spots observation is explicitly empirical, with no reproducible data; fine as a remark, but it should not be advertised as evidence. The circularity worry is a non-issue: the boundary definition comes from a cited earlier paper and the inequalities are derived, not assumed.\n\nWho is this for: people working on graph Laplacians, random walks on graphs, and discrete PDE analogues. A serious referee should be able to fix or refute Theorems 2 and 5. I would send it to review, with a clear request to focus on those two proofs.","headline":"A worthwhile paper with four solid theorems and two unproven ones; referee it, but do not accept as is.","tokens_in":20883,"tokens_out":4993,"would_cite":false,"duration_ms":53830,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C81","31C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph's potential-theoretic boundary is where neighbors point inward, and six classical inequalities hold there.","keywords":["graph boundary","potential theory","random walk hitting time","Faber-Krahn inequality","Hardy inequality","Alexandrov-Bakelman-Pucci estimate","hot spots","Björck theorem"],"falsifier":"A direct check of the definition on the complete bipartite graph $K_{n,n}$ settles part of the naturalness claim: every vertex has a witness, so $\\partial G=V$ and the interior $V\\setminus\\partial G$ is empty; if one regards $K_{n,n}$ as having no natural geometric boundary, then the six theorems become vacuous on it and the potential-theoretic interpretation would need to explain what 'interior' means there.","tokens_in":19734,"feed_emoji":"📐","tokens_out":11845,"duration_ms":121288,"temperature":0.7,"pith_summary":"The paper proposes that a finite connected graph has an intrinsic boundary: a vertex belongs to ∂G when some other vertex witnesses that the average neighbor is closer to it than the vertex itself. The claim is that this boundary behaves like the boundary of a Euclidean domain for potential theory. To support this, the author proves six quantitative analogues of classical results for functions vanishing on ∂G: an expected-exit-time bound for random walks, a Faber–Krahn inequality, a Hardy inequality, an Alexandrov–Bakelman–Pucci estimate, a stability estimate for the hot-spots eigenfunction, and a Björck-type theorem saying energy-maximizing measures live on the boundary. If correct, these six results together say that imposing Dirichlet conditions on ∂G reproduces the scaling laws of classical analysis on arbitrary finite graphs, making ∂G a natural object for graph PDEs and spectral theory.","feed_headline":"Six classical inequalities hold on a graph's witness-defined boundary","feed_subtitle":"Functions vanishing on that boundary obey Euclidean-style diameter scaling on any finite connected graph.","key_machinery":"The load-bearing object is the boundary ∂G defined by the witness condition, together with Proposition 1: v∈∂G if and only if, for some w, v has more neighbors at distance one closer to w than at distance one farther from w. Negating gives the interior characterization used throughout: for every w, the number of neighbors moving away from w is at least the number moving toward w. That single combinatorial dichotomy converts graph questions into questions about a one-dimensional random walk on distance layers {0,1,...,diam(G)} with no leftward drift; Lemma 1 bounds the exit time of this dominated walk by diam(G)^2 with an exponential tail. The expected hitting time φ of ∂G then serves as the Hardy weight and as the super-solution in a modified Agmon–Allegretto–Piepenbrink argument, while the same distance-walk bound supplies the mixing input for the ABP and hot-spots estimates.","core_discovery":"On the paper's own terms, the discovery is that the witness-based set ∂G is a usable Dirichlet boundary for all finite connected graphs, not just trees or grids. The central quantitative package is the following: a random walk from any vertex hits ∂G in expected time at most max_v deg(v)·diam(G)^2; the smallest eigenvalue of the graph Laplacian with Dirichlet conditions on ∂G is at least (1/4) min_v deg(v)/diam(G)^2; the expected hitting time φ satisfies a Hardy inequality with weight deg(v)/φ(v); a function's maximum is controlled by its boundary maximum plus 2(maxdeg/mindeg)diam(G)^2 ∥Lf∥∞; the second eigenfunction's interior maximum is bounded by a possibly large constant times its boundary maximum when its eigenvalue λ2<1; and any extremal probability measure for a strictly convex increasing function of graph distance is supported in ∂G. The proofs rest on a distance-layer characterization: an interior vertex has at least as many neighbors farther from every witness as closer to it.","pith_inferences":["If ∂G is accepted as the potential-theoretic boundary, then other classical boundary notions (Martin boundary, measure-theoretic boundary) likely have distinct graph analogues with their own sets of true theorems; the paper itself says this is probably not the end of the story.","The stochastic-domination proof suggests a testable extension: replacing the uniform maximum degree by a local degree average might sharpen the constant in Theorems 1, 2, and 4 on graphs with heterogeneous degrees.","The Björck theorem has a computational corollary the author leaves implicit: for maximum-dispersion-type optimization on graphs, one may restrict the search to ∂G, shrinking the feasible set dramatically on graphs with small boundary.","Because the boundary is defined through distance comparisons, graph embeddings or metric perturbations that change distances can shift ∂G nonlocally; quantifying that sensitivity would tell whether ∂G is robust enough for use in data-science Laplacian pipelines."],"forward_implications":["Functions vanishing on ∂G form a genuine Dirichlet space: the principal eigenvalue of the restricted Laplacian is positive and bounded below by $\\min_v \\deg(v)/(4\\,\\mathrm{diam}(G)^2)$, so interior heat decay has a rate controlled by the diameter.","The random walk exit-time bound $\\mathbb{E}T \\le \\max_v \\deg(v)\\,\\mathrm{diam}(G)^2$ holds from any starting vertex, so boundary absorption is always quadratically fast in the diameter, matching Brownian intuition.","The Björck-type theorem implies that for any strictly convex increasing function of graph distance, a maximizer of the two-point energy can be chosen with all mass on $\\partial G$; in particular, for $\\alpha>1$ the distance-energy maximizers avoid interior vertices.","The ABP estimate yields a quantitative maximum principle: if $\\|Lf\\|_{L^\\infty(V\\setminus\\partial G)}$ is small, then $f$'s maximum exceeds its boundary maximum only by a controlled multiple of $\\mathrm{diam}(G)^2$.","For path-like graphs, where the second eigenvalue satisfies $\\lambda_2 \\lesssim 1/\\mathrm{diam}(G)^2$, the hot-spots constant in Theorem 5 stays uniformly bounded, giving genuine interior-to-boundary control for the second eigenvector."],"supporting_citations":[{"why":"Introduces the witness-based boundary ∂G and proves the isoperimetric inequality that motivates this paper.","marker":"[57]"},{"why":"Supplies the Euclidean exit-time upper bound that Theorem 1 discretizes.","marker":"[49]"},{"why":"Supplies the fundamental-frequency problem behind the Faber–Krahn inequality that Theorem 2 addresses.","marker":"[53]"},{"why":"Provides the super-solution method used in Lemma 2 to prove the Hardy inequality.","marker":"[1, 3, 4, 48]"},{"why":"Gives the continuous super-solution lemma whose discrete counterpart is Lemma 2.","marker":"[20]"},{"why":"Provides the classical Alexandrov–Bakelman–Pucci estimates whose graph analogue is Theorem 4.","marker":"[6, 7, 8, 50, 51, 56]"},{"why":"Provides the Euclidean hot-spots upper bound whose graph analogue is Theorem 5.","marker":"[60]"},{"why":"Provides the classical theorem on boundary-supported energy maximizers that Theorem 6 generalizes.","marker":"[11]"},{"why":"Gives the 'large interior ball' interpretation used after the Faber–Krahn argument.","marker":"[42]"}],"fun_headline_variants":["Witness boundary yields classical potential theory on all graphs","Graph potential theory: witness boundary gives Euclidean-style results","Random walk on any graph hits witness boundary in O(diam^2)","Dirichlet on graphs: witness boundary works like Euclidean domains","Hardy, Faber-Krahn, ABP all hold on graph witness boundaries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the witness-defined set ∂G is the right boundary notion; two of the proofs (Theorems 2 and 5) additionally assume, without an explicit justification, that Lemma 1's exponential tail bound transfers from the auxiliary distance-change walk to the original graph walk.","fun_headline_variants_meta":{"raw":{"variants":["Witness boundary yields classical potential theory on all graphs","Graph potential theory: witness boundary gives Euclidean-style results","Random walk on any graph hits witness boundary in O(diam^2)","Dirichlet on graphs: witness boundary works like Euclidean domains","Hardy, Faber-Krahn, ABP all hold on graph witness boundaries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000819,"raw_usage":{"total_tokens":3582,"prompt_tokens":941,"completion_tokens":2641,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":2554}},"tokens_in":557,"tokens_out":2641,"duration_ms":20061,"temperature":1.0,"reasoning_tokens":2554,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:42:54.366090+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct check of the definition on the complete bipartite graph $K_{n,n}$ settles part of the naturalness claim: every vertex has a witness, so $\\partial G=V$ and the interior $V\\setminus\\partial G$ is empty; if one regards $K_{n,n}$ as having no natural geometric boundary, then the six theorems become vacuous on it and the potential-theoretic interpretation would need to explain what 'interior' means there.","supporting_citations":[{"cited_title":"Steinerberger, The Boundary of a Graph and its Isoperimetric Inequality, Discrete Applied Mathematics 338 (2023), p","cited_arxiv_id":null,"evidence_quote":"Introduces the witness-based boundary ∂G and proves the isoperimetric inequality that motivates this paper."},{"cited_title":"P´ olya, Torsional rigidity, principal frequency, electrostatic capacity and symmetrization","cited_arxiv_id":null,"evidence_quote":"Supplies the Euclidean exit-time upper bound that Theorem 1 discretizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the fundamental-frequency problem behind the Faber–Krahn inequality that Theorem 2 addresses."},{"cited_title":"Brian Davies, Heat kernels and spectral theory, Cambridge University Press, 1989","cited_arxiv_id":null,"evidence_quote":"Gives the continuous super-solution lemma whose discrete counterpart is Lemma 2."},{"cited_title":"Steinerberger, Curvature on graphs via equilibrium measures, Journal of Graph Theory 103.3 (2023): 415-436","cited_arxiv_id":null,"evidence_quote":"Provides the Euclidean hot-spots upper bound whose graph analogue is Theorem 5."},{"cited_title":"Bjorck, Distributions of positive mass, which maximize a certain generalized energy inte- gral","cited_arxiv_id":null,"evidence_quote":"Provides the classical theorem on boundary-supported energy maximizers that Theorem 6 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the 'large interior ball' interpretation used after the Faber–Krahn argument."}],"review_version":2}