{"id":"3fbcd3d8-cb76-4b18-ad10-2838f3fcb362","arxiv_id":"2509.08531","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A new recoloring phase for a local greedy algorithm shows that random 5-regular graphs have bisection width below 0.496488n and, as a consequence, almost surely admit an internal partition.","lead":"The paper adds a recoloring phase to a known greedy algorithm and computes tighter bounds on the bisection width and max-cut of random 5-regular graphs, proving that almost all such graphs admit an internal partition. It is a concrete step toward understanding friendly partitions in odd-regular graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The numerical threshold in Theorem 1.2 is not certified: Table 1 gives floating-point output with no error bounds, so the strict inequality below 0.496488n is not established.","rationale":"I agree with the reader that the main vulnerability is in the tree computation and its transfer to random graphs, and that the strict inequality is not certified by the table. I focus on the numerical certification as the single most load-bearing concern because all downstream claims depend on the exact constant 0.496488, and no amount of coupling between tree and graph can rescue the proof if the floating-point recursion is off by even a few units in the sixth decimal. The paper does provide source code, which makes the concern concretely checkable, but no certified numerical computation is included. The reader already assigns a conditional verdict; my analysis does not move that verdict, so I recommend UNCHANGED. I say partial agreement because I emphasize the numerical margin more strongly than the coupling sketch, while the reader lists both with roughly equal weight.","tokens_in":15404,"tokens_out":18235,"duration_ms":457325,"concrete_test":"Take the published source code and recompute the Section 2.6 recursion for d=5 and 1/epsilon = 5e4 using directed-rounding interval arithmetic (for example, Arb or MPFR with rigorous error propagation) for q_t, qhat_t, and the improved cut density, recording the certified upper endpoint. If the certified upper endpoint is at least 0.496488, the numerical basis for Theorem 1.2 collapses. A secondary check is to run the algorithm with the same D_t and q_t sequence on random 5-regular graphs with n = 1e6 and compare the empirical mean cut to the tree prediction; the interval computation is the decisive test.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim is the constant 0.496488n, and Theorems 1.3 and 1.4 inherit it. The proof of Theorem 1.2 rests on the Section 2.6 recursion, which is executed in floating point. Table 1 reports six decimal digits without interval bounds, and the paper explicitly uses the 1/epsilon = 5e4 row, where the improved cut size is printed as 0.496488. If the true value is 0.4964884 or larger, the strict inequality in Theorem 1.2 fails. Remark 2.8 concedes that the simplified rows omit higher-order terms; even the unstarred row leaves accumulated rounding and discretization error over roughly 5e4 steps uncontrolled. The transfer argument in Section 2.7 does not repair this: even granting the tree-to-graph coupling, it only bounds the graph-versus-tree discrepancy by p_l, while the theorem additionally requires the true tree value to lie below 0.496488 by a positive margin exceeding all numerical and coupling errors. No such margin is quantified anywhere in the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new factor-of-IID local algorithm for random d-regular graphs, based on the greedy algorithm of Díaz, Serna, and Wormald, augmented by a recoloring phase. The algorithm is analyzed on the infinite d-regular tree via a recursion for the law of the colored two-neighborhood, with the sequence of dominant types and thresholds treated as precomputed parameters. For d=5, numerical evaluation of the recursion yields an improved cut density of 0.496488, from which the paper derives Theorem 1.2 (bisection width of a random 5-regular graph is a.a.s. smaller than 0.496488n), Theorem 1.3 (max-cut is a.a.s. larger than 2.003n), and Theorem 1.4 (almost every 5-regular graph has an internal partition). Section 2.7 sketches a transfer argument from the infinite tree to random graphs, and Section 3 derives the max-cut and internal-partition consequences.","tokens_in":15486,"tokens_out":18233,"duration_ms":162101,"significance":"If made rigorous, the main result would improve the known upper bound for the bisection width of random 5-regular graphs from about 0.5028n to below 0.5n, and would settle the existence of internal partitions for random 5-regular graphs, the first odd degree d>3 for which this is known. The algorithmic idea of appending a recoloring phase and analyzing the process through marginals on the infinite d-regular tree is natural and potentially useful for other parameter regimes. The authors also provide source code for the recursion, and the transition formulas in Section 2.5 are internally consistent. The significance is conditional, however, because the central numerical constant is not certified and the tree-to-graph transfer is only sketched.","major_comments":[{"comment":"The proof of Theorem 1.2 rests on the value 0.496488 obtained from a floating-point recursion over 5·10^4 steps. No rounding or discretization error bounds are provided, and Remark 2.8 explicitly concedes that the last two rows of Table 1 were computed with simplified formulas in which higher-order terms are omitted. The table therefore supplies numerical evidence, not a proven upper bound. To make the theorem rigorous, the computation must be repeated with certified interval arithmetic or an a priori bound on the accumulated error, and the final constant must be a proven upper bound rather than a printed floating-point value.","section":"Section 2.6 / Table 1"},{"comment":"Even if the computation were exact, the displayed value supports only 'at most 0.496488', not 'a.a.s. smaller than 0.496488n'. The cut size is integer-valued, so for values of n with 0.496488n an integer, an upper bound of 0.496488n does not imply a strict inequality unless a positive margin is established. The applications only require a bound below n/2, so the authors could state the theorem with a slightly larger certified constant or with a non-strict inequality; as written, the strict inequality is not justified.","section":"Theorem 1.2 / Section 2.6"},{"comment":"The transfer argument from the infinite tree to random graphs is asserted rather than proved. After bounding the probability p_l that a random vertex has a cycle in its R-neighborhood, the text says that p_l 'also gives an upper bound on the L∞-distance of the empirical and the calculated distribution'. A proof requires two ingredients: (i) for every vertex whose R-neighborhood is acyclic, the joint law of its colored two-neighborhood after N steps under the precomputed sequence (D_t, q_t) equals the tree marginal, and (ii) the empirical average over the n vertices is concentrated around the tree expectation up to an O(p_l) error. The current text only counts vertices near short cycles and does not establish either ingredient.","section":"Section 2.7"},{"comment":"The algorithm is not shown to produce a bisection. In the original DSW procedure, vertices are colored in asymmetric pairs to maintain exact balance between the color classes; here vertices are colored independently in parallel, and the final random coloring of uncolored vertices makes the expected class sizes equal but not the actual ones. The difference between the numbers of red and blue vertices is of order sqrt(n), and the recoloring phase swaps equal numbers of red and blue vertices, so it cannot repair this imbalance. The paper should either specify a balancing step that changes the cut by o(n) edges or prove that the imbalance is o(1); as written, the constructed partition need not satisfy the definition of a bisection.","section":"Section 2.3"}],"minor_comments":[{"comment":"The sentence 'The number of steps is denoted by by N' contains a duplicated word 'by'.","section":"Section 2.3"},{"comment":"The first row appears internally inconsistent: the improvement is 0.501778−0.501257=0.000521, whereas μ(3)·0.0199445≈0.00680, which is not consistent with the other rows if the improvement is μ(3) times the miscolored-vertex density. Please check the reported values.","section":"Table 1"},{"comment":"The sentence 'Probability p_l also gives an upper bound on the L∞-distance of the empirical and the calculated distribution' conflates the probability of a bad event with a distance bound on distributions; a formal lemma with the precise coupling would clarify the argument.","section":"Section 2.7"},{"comment":"The formula for q̂_t is load-bearing for the recursion but is justified only by 'One can check'; a short derivation would improve the paper's rigor and readability.","section":"Section 2.5"},{"comment":"The induction in the proof of Lemma 2.6 is terse, especially the notation B_t and the handling of the conditioning events; expanding the argument would make the independence claim easier to verify.","section":"Lemma 2.6"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the gap between the floating-point computation and a rigorous proof of the stated numerical theorems. If the authors obtain a certified interval for the tree computation and write out the transfer lemma, the paper would be a solid contribution to the topic. The current version, however, does not yet prove the theorems as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nHere is my honest take. The paper has a genuinely new algorithmic idea—adding a terminal recoloring phase to the Díaz–Serna–Wormald greedy bisection and analyzing it via a density recursion on the infinite 5-regular tree—and it uses that to settle the open internal-partition case for 5-regular graphs, conditional on the numerical bound. The finite-round local algorithm in Section 2.3 is a nice contribution in itself, and the tree recursion in Section 2.5 is coherent; I checked the q_t definition and the transition structure and it hangs together. The application to internal partitions via the Bárnkopf–Nagy–Paulovics theorem is clean and not circular.\n\nThe soft spot is exactly where the stress-test points. The number 0.496488 is not established by the computation in Table 1. It is floating-point output with no interval bounds, and the strict inequality in Theorem 1.2 requires the true tree value to be below 0.496488 by a positive margin. If the true value is 0.4964884, the theorem as stated fails. Remark 2.8 concedes that the starred rows use simplified formulas, and even the unstarred row accumulates rounding and discretization error over 50,000 steps with nothing controlling it. This is fixable: run the same recursion with interval arithmetic, or state the theorem with a safely rounded constant such as 0.49649 and prove that value. But as it stands, Theorem 1.2 (and therefore Theorems 1.3 and 1.4) is not rigorously proved.\n\nThe transfer from the infinite tree to random graphs in Section 2.7 is also a sketch. The cycle-counting argument gives p_l→0, and it is plausible that this bounds the discrepancy of the empirical distribution, but the sentence 'p_l also gives an upper bound on the L∞-distance' is doing work that needs a real argument. I would call this a moderate gap, not a fatal one; for a local algorithm with bounded dependence radius, the standard local-weak-convergence argument should work, but it needs to be written out.\n\nMinor but real: the abstract says d>4 while only d=5 is quantified. That should be corrected.\n\nOverall: the algorithmic idea is good, the internal-partition application is the kind of result people in this area will care about, and the flaws are numerical rigor and a sketched transfer, not a conceptual dead end. I would send it to a serious referee with a request for the authors to either certify the computation or soften the theorem. It deserves referee time, but it is not ready as is.","headline":"Genuinely new algorithmic idea and a clean internal-partition application, but the headline numerical bound is not rigorously established because Table 1 is uncertified floating-point output.","tokens_in":16171,"tokens_out":3014,"would_cite":false,"duration_ms":27865,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random 5-regular graphs can be bisected with fewer than 0.496488n crossing edges almost surely, which also gives them an internal partition.","keywords":["bisection width","max-cut","random regular graphs","internal partitions","local algorithms","factor of IID","recoloring","infinite regular tree"],"falsifier":"Compute the tree Markov recursion with exact rational or interval arithmetic at 1/ε = 5·$10^{4}$: if the improved cut density is not strictly below 0.496488, the strict inequality in Theorem 1.2 fails. Alternatively, simulate the algorithm on large random 5-regular graphs and check whether the empirical average cut size stays below 0.496488n by an o(n) margin.","tokens_in":15111,"feed_emoji":"✂️","tokens_out":8725,"duration_ms":70723,"temperature":0.7,"pith_summary":"Random 5-regular graphs can be split into two nearly equal halves with fewer than 0.496488n crossing edges, asymptotically almost surely. The paper obtains this with a new factor of IID process — a local random rule applied identically at every vertex — that runs the earlier greedy bisection algorithm in bulk rounds and then recolors a set of 'miscolored' vertices to repair bad local decisions. The cut density is computed numerically on the infinite 5-regular tree and then transferred to finite random graphs through their locally tree-like structure. Because the improved value lies strictly below n/2, the same construction proves that asymptotically almost every 5-regular graph has an internal partition, and it also yields a max cut larger than 2.003n.","feed_headline":"Random 5-regular graphs bisect below 0.496488n","feed_subtitle":"A local recoloring algorithm also yields max cuts above 2.003n and guarantees a friendly partition.","key_machinery":"The carrying object is a Markov chain for the color distribution on the rooted two-neighborhood of the infinite 5-regular tree. At each of about 1/ε steps the algorithm selects a dominant vertex type, the highest-priority type whose uncolored measure is at least ε, and uses threshold probabilities to color vertices of that type; the transition table for the second neighborhood gives the exact law after each step. The recoloring phase then builds a balanced bipartite graph from vertices whose final color disagrees with their terminal neighborhood, and a known theorem guarantees a large bihole — an independent set with equally many vertices on both sides — whose color swap lowers the cut by a positive constant per vertex. The numerical recursion on this tree object yields the claimed 0.496488 cut density.","core_discovery":"On the paper's own terms, the central discovery is a local factor-of-IID bisection algorithm whose expected cut density on a random 5-regular graph is asymptotically at most 0.496488 edges per vertex, strictly below the earlier numerical upper bound of about 0.5028 and below one half. The algorithm runs the earlier greedy coloring in a constant number of bulk rounds, independent of n, and then flips a set of miscolored vertices whose existence is guaranteed by a bounded-degree bipartite independence theorem. The performance is computed numerically on the infinite 5-regular tree through a Markov process on the rooted two-neighborhood, and the paper argues that the transfer to random n-vertex graphs carries only an o(n) error with high probability. The strict inequality below n/2 is then used to prove that asymptotically almost every 5-regular graph has an internal partition.","pith_inferences":["The tree computation at 1/ε = 2.5·10^6 suggests the improved cut density may be as low as 0.496392n; the paper stops at 0.496488 because it only certifies the coarser step, so a tighter bound may be within reach without new ideas.","A direct simulation on large random 5-regular graphs comparing the empirical bisection size with the predicted tree value would test the assumed o(n) transfer error.","The recoloring phase currently uses only about a third of the available miscolored vertices; tracking second neighborhoods could enlarge the gain, as the paper itself notes in its conclusion.","For d at least 7 the same route is blocked because the paper does not expect bisection width below n/2; internal partitions for larger odd degrees would need a different mechanism."],"forward_implications":["The bisection width of a random 5-regular graph is asymptotically almost surely below 0.496488n, improving the earlier upper bound of roughly 0.5028n.","The maximum cut of a random 5-regular graph is asymptotically almost surely larger than 2.003n.","Asymptotically almost every 5-regular graph admits an internal partition, meaning every vertex has at least as many neighbors in its own class as in the other.","The same two-phase local algorithm gives improved upper bounds on bisection width and lower bounds on max-cut for random d-regular graphs for every constant d greater than 4.","The bulk-coloring variant of the greedy algorithm terminates in a constant number of rounds independent of n, and its tree-based analysis avoids the differential equation method."],"supporting_citations":[{"why":"Supplies the base greedy bisection algorithm and the first-phase cut-size estimate that the new recoloring phase improves.","marker":"[17]"},{"why":"Provides the balanced bipartite graph theorem used to find the large independent set of miscolored vertices to flip.","marker":"[2]"},{"why":"Gives the lemma that a bisection of a 5-regular graph with at most n/2 + 5 crossing edges yields an internal partition.","marker":"[5]"},{"why":"Supplies the Poisson convergence of cycle counts in random regular graphs used to bound the number of non-tree-like vertices.","marker":"[9]"},{"why":"Provides the random regular graph models and the transfer principle for local algorithms on large-girth graphs.","marker":"[38]"}],"fun_headline_variants":["Almost all 5-regular graphs admit an internal partition","Bisection bound for random 5-regular graphs dips below half","New local algorithm tightens bisection and max-cut bounds","Random 5-regular graphs split with cut under 0.4965 per vertex","Guaranteed friendly splits in random 5-regular graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the cut density computed numerically on the infinite 5-regular tree transfers to random n-vertex graphs up to an o(n) error, and that the strict inequality below 0.496488n is real rather than an artifact of four-decimal rounding.","fun_headline_variants_meta":{"raw":{"variants":["Almost all 5-regular graphs admit an internal partition","Bisection bound for random 5-regular graphs dips below half","New local algorithm tightens bisection and max-cut bounds","Random 5-regular graphs split with cut under 0.4965 per vertex","Guaranteed friendly splits in random 5-regular graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000386,"raw_usage":{"total_tokens":1986,"prompt_tokens":836,"completion_tokens":1150,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":452,"completion_tokens_details":{"reasoning_tokens":1059}},"tokens_in":452,"tokens_out":1150,"duration_ms":10274,"temperature":1.0,"reasoning_tokens":1059,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:02:05.923468+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the tree Markov recursion with exact rational or interval arithmetic at 1/ε = 5·$10^{4}$: if the improved cut density is not strictly below 0.496488, the strict inequality in Theorem 1.2 fails. Alternatively, simulate the algorithm on large random 5-regular graphs and check whether the empirical average cut size stays below 0.496488n by an o(n) margin.","supporting_citations":[{"cited_title":"D´ ıaz, M","cited_arxiv_id":null,"evidence_quote":"Supplies the base greedy bisection algorithm and the first-phase cut-size estimate that the new recoloring phase improves."},{"cited_title":"Axenovich, J.-S","cited_arxiv_id":null,"evidence_quote":"Provides the balanced bipartite graph theorem used to find the large independent set of miscolored vertices to flip."},{"cited_title":"B¨ arnkopf, Z","cited_arxiv_id":null,"evidence_quote":"Gives the lemma that a bisection of a 5-regular graph with at most n/2 + 5 crossing edges yields an internal partition."},{"cited_title":"Bollob´ as","cited_arxiv_id":null,"evidence_quote":"Supplies the Poisson convergence of cycle counts in random regular graphs used to bound the number of non-tree-like vertices."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the random regular graph models and the transfer principle for local algorithms on large-girth graphs."}],"review_version":2}