{"id":"786b111b-8911-48d5-bb9e-d882b98eea2b","arxiv_id":"2607.07260","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Adding O(n^{1-ε/α}) edges to a tree yields an n-node graph with broadcast time (1+ε)log₂n, improving the prior O(n^{1-ε}) bound, with a matching Ω(n) lower bound at ε→0.","lead":"This paper improves bounds on how many extra connections a network needs to broadcast a message to all nodes in near-optimal time. It matters for designing sparse communication networks that stay efficient under the classic telephone model.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The o(1) absorption concern is real but secondary; the core construction is sound.","rationale":"The reader correctly identified the o(1) absorption from Lemma 2.1 as the weakest link, and I agree this is the most natural concern. However, having examined it carefully, the concern affects constants but not the asymptotic claim. The parameter t−d grows as ~2ε·log₂ n → ∞, so the o(1) terms in Lemma 2.1 are legitimately absorbed into the big-O. The exponent arithmetic (α−ε)/α = 1 − ε/α is exact, not approximate. The three contributions (upper bound, lower bound, refined 1-relaxed construction) each have complete proofs with no hidden circularity. The lower bound proof (Theorem 1.4) uses a clean leaf-counting argument on subtrees of binomial trees (Lemma 3.1) and a degree-distribution analysis that checks out. The 1-relaxed construction (Theorem 1.5) is a refinement of a known construction with a verified broadcast protocol. The paper is honest about the gap between upper and lower bounds for h(n,1) (n/8 vs n − 4log₂ n). No red flags, no manufactured tightness. The reader's ACCEPT at HIGH confidence is appropriate.","tokens_in":19751,"tokens_out":797,"duration_ms":1379956,"concrete_test":"Verify the pruning claim concretely: construct the graph for n = 2^20 with ε = 0.2 (so α ≈ 0.44, ε/α ≈ 0.45), compute d from Eq. (1), build the core C with 2^{d-1} nodes, attach truncated B_k trees at level m = β(t−d), then prune to exactly n nodes. Check that b(G) ≤ (1+0.2)·20 = 24 rounds by simulating broadcast from every node. If any source exceeds 24 rounds, the pruning argument has a gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's identified concern about Lemma 2.1's convergence rate is the most natural soft spot, but it does not undermine the central claim. The claim is asymptotic (O-notation), and Lemma 2.1 is cited from established literature [23, 32, 34] with the form F(s) = (1±o(1))φ^s. In the proof of Theorem 1.2, the parameter t−d grows as approximately 2ε·log₂ n, which tends to infinity, so the o(1) terms are legitimately absorbed. The edge count becomes n + O(n^{(α−ε)/α}) = n + O(n^{1−ε/α}), with the o(1) contributions vanishing in the exponent. This is standard asymptotic analysis. A more substantive concern would be whether the pruning step (removing nodes from truncated binomial trees to hit exactly n nodes) preserves the broadcast time bound b(G) ≤ (1+ε)log₂ n. The paper argues that removing leaves from a binomial tree cannot increase broadcast time from the root (Fact 1.3) nor increase the distance from leaf to root. This is correct: pruning leaves from B_k preserves b(T,r) ≤ k because the remaining tree is still a subtree of B_k, and any subtree of B_k rooted at r has b(T,r) ≤ k. The broadcast protocol from any source still works: reach the core in ≤ m rounds, broadcast in core in d rounds, then broadcast in each attached tree in ≤ k rounds. Pruning only reduces these trees, so the bound holds. No internal inconsistency found.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the minimum number of edges required for n-node graphs achieving near-optimal broadcast time in the telephone model. The main result (Theorem 1.2) shows that for every epsilon in (0, alpha) where alpha = 1/log_2(phi) - 1 ~ 0.44, there exist n-node graphs with broadcast time (1+epsilon)log_2 n and n + O(n^{1-epsilon/alpha}) edges, improving the prior O(n^{1-epsilon}) overhead bound of Averbuch, Peeri, and Roditty (2017). The construction attaches truncated binomial trees to a sparse core graph. The paper also establishes a linear lower bound (Theorem 1.4): for n = 2^k, any n-node graph with broadcast time k+1 requires at least (9/8)n - O(1) edges, showing the O(n) overhead at epsilon -> 0 is tight. Finally, Theorem 1.5 slightly improves the upper bound on 1-relaxed minimum broadcast graphs to 2n - 4*ceil(log_2 n) + O(1) edges.","tokens_in":19942,"tokens_out":1651,"duration_ms":497813,"significance":"The paper makes a solid contribution to the network design problem for broadcasting. The upper bound O(n^{1-epsilon/alpha}) smoothly interpolates between the known O(n) overhead for 1-relaxation and the zero overhead at epsilon = alpha, resolving the question of whether a gap exists at the alpha*log_2 n threshold. The lower bound is valuable as lower bounds in this area are notoriously difficult. The proofs are combinatorial and checkable, and the construction is explicit. The result on broadcast cost (Corollary 2.2) is a nice consequence.","major_comments":[{"comment":"Section 2, proof of Theorem 1.2: The proof relies on Lemma 2.1, which gives the asymptotic F(s) = (1 +/- o(1)) * phi^s. The parameter t - d grows as approximately 2*epsilon*log_2(n), which tends to infinity, so the o(1) terms are legitimately absorbed into the big-O notation. This is standard asymptotic analysis and the central claim is sound. However, the proof would benefit from a brief remark acknowledging that the hidden constants in the O(n^{1-epsilon/alpha}) bound depend on the convergence rate of the o(1) terms in Lemma 2.1, and that the result is asymptotic in nature (requiring n >= n_epsilon). This is a presentation issue rather than a correctness concern.","section":null},{"comment":"Section 2, 'Fixing the number of nodes' paragraph: The pruning step (removing nodes from truncated binomial trees to hit exactly n nodes) is argued to preserve the broadcast time bound. The argument that removing leaves cannot increase broadcast time from the root (by Fact 1.3) is correct. However, the broadcast protocol from an arbitrary source node s requires: (1) reaching the core in <= m rounds, (2) broadcasting in the core in d rounds, (3) broadcasting from each core node into its attached tree in <= k rounds. The paper should explicitly verify that pruning leaves does not increase the distance from any node to the core beyond m, which is the first step of the broadcast protocol. Since pruning only removes nodes, the distance from any remaining node to the core cannot increase, so this holds, but making this explicit would strengthen the argument.","section":null},{"comment":"Section 3, proof of Theorem 1.4, case delta(G) = 1: The degree-distribution argument is careful but dense. The transition from counting additional edges incident to internal vertices of T_v to the minimization of A = (1/2) * sum_{i=2}^{k-2} x_i * (k-1-i) under the constraint sum x_i >= 2^{k-2} - 3 is correct. The final bound A >= 2^{k-4}(k-2) - (3/2)(k-3) leading to |E(G)| >= n - 1 + n/8 for k >= 6 is verified. The constraint sum x_i >= 2^{k-2} - 3 (rather than 2^{k-2}) accounts for the four vertices in S_k and S_{k-1} already having degree >= k-1; this should be stated more explicitly for clarity.","section":null}],"minor_comments":[{"comment":"Abstract: 'previsouly' should be 'previously'.","section":null},{"comment":"Section 1.1, first paragraph: 'standardtelephone model' should be 'standard telephone model'.","section":null},{"comment":"Section 1.2.1: 'Theorem 1.2 has an important corollary' -- Corollary 2.2 is stated in Section 2, not immediately after Theorem 1.2. Consider adding a forward reference.","section":null},{"comment":"Figure 2: The caption mentions 'The dotted line is the new upper bound' but the figure description could clarify that the dotted curve represents n^{1-epsilon/alpha} and the solid curve represents n^{1-epsilon}.","section":null},{"comment":"Section 2, proof of Theorem 1.2: The notation '(1 +/- o(1))' appears in several places (e.g., in the application of Lemma 2.1 and in Equation 1). It would be cleaner to use '(1+o(1))' consistently, noting that the o(1) term may be positive or negative but is absorbed into the asymptotic bound.","section":null},{"comment":"Section 4, proof of Theorem 1.5: The condition k >= 8 is mentioned for the pruning to preserve that x has at least one child y in T, but the final edge count formula |E(G)| = 2(n-1) - 2(1 + (k-1) + (k-2)) = 2n - 4k + 2 is stated for k >= 6. The relationship between these thresholds should be clarified.","section":null},{"comment":"Section 5, Equation (3): The lower bound is stated as n/8 <= h(n,1), but Theorem 1.4 gives (9/8)n - O(1) edges total, which translates to h(n,1) >= n/8 - O(1). The -O(1) term is missing in Equation (3).","section":null},{"comment":"Table 1: The lower bound entry '1/8 n' for relaxation tau=1 should perhaps be 'n/8 - O(1)' to match the precise statement of Theorem 1.4.","section":null},{"comment":"Section 1.2.2: 'wether B(n+1) >= B(n)' should be 'whether B(n+1) >= B(n)'.","section":null},{"comment":"Section 2: The variable n_epsilon is introduced but the threshold for n is not explicitly quantified. A brief remark on how n_epsilon depends on epsilon would be helpful.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a well-executed combinatorial construction with correct proofs. The main result is a genuine improvement over the prior state of the art. The minor comments are primarily typographical and presentational. I see no reason to doubt the correctness of the central claims. The paper fits well within the scope of the journal."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper does three things: improves the overhead bound for (ε log n)-relaxed broadcast graphs from O(n^{1-ε}) to O(n^{1-ε/α}), proves the first non-trivial lower bound (Ω(n)) for 1-relaxed graphs at powers of two, and slightly improves the 1-relaxed construction from 2n−log n to 2n−4 log n edges. The upper bound is the main result and is genuinely new — the construction replaces the hypercube-based approach from Averbuch–Peeri–Roditty with truncated binomial trees hung off a sparse core graph, which is a cleaner and more natural idea. The lower bound is the first of its kind for any τ>0 relaxation, which is notable given how notoriously hard lower bounds are in this area. The 1-relaxed improvement is minor but correct, and it feeds back into the upper bound proof as the core graph choice, so it earns its keep. The proofs are combinatorial and checkable. I worked through the upper bound argument in Section 2 — the optimization over d, k, m is set up correctly, Lemma 2.1 is applied legitimately, and the o(1) terms are absorbed cleanly since t−d grows as roughly 2ε log n. The stress-test note worried about the pruning step (removing nodes from truncated binomial trees to hit exactly n), but the argument holds: pruning leaves from a subtree of B_k preserves b(T,r) ≤ k, and the three-phase broadcast protocol still works. The lower bound in Section 3 handles two cases (δ(G)≥2 and δ(G)=1) with a careful degree-distribution argument. The δ(G)=1 case is the harder one and the accounting there is intricate but sound for k≥6. The soft spots are minor. The lower bound only works for n=2^k, so it's an infinite-but-sparse set of n values. The 1-relaxed improvement is small (saving 3k edges) and the authors acknowledge this. The conjectures at the end are reasonable but unproven. This is a paper for researchers in broadcast network design and combinatorial graph theory. The main result advances the state of the art on a well-studied problem, the lower bound opens a new direction, and the proofs hold up. It deserves a serious referee.","headline":"Solid paper improving the overhead bound for relaxed broadcast graphs from O(n^{1-ε}) to O(n^{1-ε/α}), plus a first linear lower bound for τ=1.","tokens_in":20548,"tokens_out":570,"would_cite":true,"duration_ms":201192,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35"],"pacs":[],"model":"glm-5.2","headline":"Golden ratio governs the price of near-optimal broadcast networks","keywords":["broadcasting","minimum broadcast graph","binomial tree","golden ratio","graph sparsity","network design","information dissemination"],"falsifier":"An explicit construction of n-node graphs with broadcast time (1+epsilon)*log_2(n) and n + o(n^{1-epsilon/alpha}) edges for some fixed epsilon in (0, alpha) would falsify the claim that the exponent 1-epsilon/alpha is tight. Conversely, a lower bound exceeding n^{1-epsilon/alpha} for some epsilon would show the upper bound is not tight and the true overhead is larger.","tokens_in":19967,"feed_emoji":"📡","tokens_out":1496,"duration_ms":300099,"temperature":0.7,"pith_summary":"The paper studies how many extra communication links one must add to a tree on n nodes so that information can spread from any source to all nodes in nearly the minimum possible number of rounds. The information-theoretic floor for broadcasting to n nodes is ceil(log_2 n) rounds, since each informed node can inform at most one neighbor per round. The golden ratio phi = (1+sqrt(5))/2 enters through the constant alpha = 1/log_2(phi) - 1, which is approximately 0.44. This constant marks a natural threshold: when the allowed broadcast time exceeds (1+alpha)*log_2 n, a bare tree suffices with zero extra edges; below that threshold, extra edges are needed. The paper's central result is that for any relaxation epsilon between 0 and alpha, the overhead — the number of edges beyond the n-1 that a tree already provides — is O(n^{1-epsilon/alpha}). This improves the previous best bound of O(n^{1-epsilon}) and interpolates smoothly between the two extremes: linear overhead when epsilon approaches zero (matching a new lower bound of n/8 for powers of two), and zero overhead when epsilon reaches alpha. The construction attaches truncated binomial trees to a sparse core graph, and the edge count is optimized by a classical identity: the maximum partial sum of binomial coefficients is governed asymptotically by phi raised to the relevant power.","feed_headline":"Golden ratio governs the price of near-optimal broadcast networks","feed_subtitle":"How many extra links does a tree need to broadcast in near-optimal time? The answer decays as n^{1-ε/α}, where α is set by the golden ratio.","key_machinery":"The construction builds a graph from a core graph C (a 1-relaxed broadcast graph with at most 2*|V(C)| edges and broadcast time ceil(log_2 |V(C)|) + 1) with a truncated binomial tree B_k attached at each core node, keeping only levels 0 through m. The broadcast time of the resulting graph is at most m + d + k where d = b(C). The edge count is minimized by choosing m to maximize the partial binomial sum sum_{i=0}^{m} C(k, i), whose maximum over m is asymptotically phi^{k} (Lemma 2.1, from prior work on binomial tree broadcasting). The parameter d is set to approximately (1 - epsilon/alpha) * log_2 n, which yields the exponent 1 - epsilon/alpha in the overhead. For the lower bound, the proof (","core_discovery":"The overhead function h(n, tau) — the number of edges beyond a spanning tree needed to achieve broadcast time ceil(log_2 n) + tau — satisfies h(n, epsilon*log_2 n) = O(n^{1-epsilon/alpha}) for 0 < epsilon < alpha, where alpha = 1/log_2(phi) - 1 and phi is the golden ratio. This bound is asymptotically tight at both endpoints of the interval: it gives O(n) as epsilon approaches 0 (confirmed by a linear lower bound for 1-relaxed graphs on powers of two) and O(1) when epsilon = alpha (where trees alone suffice). The exponent 1 - epsilon/alpha arises from optimizing a tradeoff between the size of a core graph and the depth of truncated binomial trees attached to it, where the golden ratio govern","pith_inferences":["If Conjecture 2 in the paper holds — that every n-node graph with broadcast time ceil(log_2 n) + c for constant c requires n + Omega(n) edges — then the broadcast cost lower bound n*log_2(n) + Omega(n) would be tight, since one could not do better than linear overhead for any constant relaxation. This would close the gap between the cost upper and lower bounds.","The golden-ratio threshold alpha likely reflects a deeper structural constraint: binomial trees achieve the optimal broadcast-time-to-size ratio for trees, and the partial-sum identity governing their truncation is inherently tied to the Fibonacci recurrence. Networks that beat this ratio must add edges, and the rate at which the required edges decay is governed by the same constant.","The construction's reliance on a core graph with 1-relaxed broadcast time suggests a recursive or hierarchical composition strategy: one could potentially iterate the construction, using relaxed broadcast graphs as cores within larger constructions, though the paper does not explore this."],"forward_implications":["The minimum broadcast cost cost(n) = min over n-node graphs G of b(G)*|E(G)| satisfies cost(n) = n*log_2(n) + alpha*n*log_2(log_2(n)) + O(n), matching the known upper bound and approaching the lower bound of n*log_2(n) + Omega(n).","The linear lower bound of n/8 for 1-relaxed broadcast graphs on powers of two confirms that even a single round of relaxation from optimal does not eliminate the need for a linear number of extra edges, settling the order of magnitude for the smallest nontrivial relaxation.","The upper bound O(n^{1-epsilon/alpha}) provides a smooth interpolation between the linear-overhead regime (small epsilon) and the zero-overhead tree regime (epsilon = alpha), resolving the apparent discontinuity in the prior bound O(n^{1-epsilon}) which failed to reach zero at the threshold."],"fun_headline_variants":["Golden ratio sets the edge cost of near-optimal broadcast","How many links make a tree broadcast near-optimally? The golden ratio decides","Golden ratio governs tight edge bound for relaxed broadcast graphs","Near-optimal broadcast needs fewer extra edges than previously known","Golden ratio dictates sparse broadcast network overhead"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The edge-count optimization rests on an asymptotic identity (Lemma 2.1) stating that the maximum partial sum of binomial coefficients C(s-m, i) over m is (1 +/- o(1)) * phi^s, achieved at m approximately 0.28*s. The proof absorbs the o(1) terms into big-O notation, but if the convergence to this asymptotic is slow for the parameter ranges actually used — where the relevant quantity t-d grows as roughly 2*epsilon*log_2(n) — the hidden constants in the O(n^{1-epsilon/alpha})) ","fun_headline_variants_meta":{"raw":{"variants":["Golden ratio sets the edge cost of near-optimal broadcast","How many links make a tree broadcast near-optimally? The golden ratio decides","Golden ratio governs tight edge bound for relaxed broadcast graphs","Near-optimal broadcast needs fewer extra edges than previously known","Golden ratio dictates sparse broadcast network overhead","Trees plus O(n^{1-ε/α}) edges suffice for near-optimal broadcast","Golden ratio reveals tight overhead for relaxed broadcast graphs","Sparser broadcast graphs via the golden ratio","Golden ratio pins the cost of near-optimal information dissemination","Near-optimal broadcast overhead decays as n^{1-ε/α} with α from φ"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":1673,"prompt_tokens":858,"completion_tokens":815,"prompt_tokens_details":null},"tokens_in":858,"tokens_out":815,"duration_ms":45304,"temperature":1.0,"reasoning_tokens":664,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T15:45:48.669950+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"An explicit construction of n-node graphs with broadcast time (1+epsilon)*log_2(n) and n + o(n^{1-epsilon/alpha}) edges for some fixed epsilon in (0, alpha) would falsify the claim that the exponent 1-epsilon/alpha is tight. Conversely, a lower bound exceeding n^{1-epsilon/alpha} for some epsilon would show the upper bound is not tight and the true overhead is larger.","supporting_citations":[],"review_version":1}