{"id":"a4b5e855-712d-4133-a853-12527c6cf3ff","arxiv_id":"2607.27455","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"R(d)<e d, so every additive fair-division instance has a partial (1−ε)-EFX allocation with O(√(n/ε)) unallocated goods, found by a randomized poly-time algorithm.","lead":"The paper proves the rainbow cycle number satisfies R(d)<e·d, resolving the conjecture that it is linear. That bound yields partial (1−ε)-EFX allocations with only O(√(n/ε)) unallocated goods—the best asymptotic guarantee the standard rainbow-cycle reduction can give.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader’s strongest claim is precisely Theorem 3, whose short combinatorial proof I re-checked. The injectivity map, the counting that produces the packing inequality, the AM-GM/Stirling passage to R(d)<e d, and the identical counting that underlies the randomized algorithm are all sound. The only external dependency is Proposition 2, which the paper quotes and uses correctly; any flaw there would affect only the EFX corollary, not the resolution of the rainbow-cycle conjecture itself. Residual risk is ordinary transcription error, not conceptual fragility. Consequently the ACCEPT verdict stands and no adjustment is warranted.","tokens_in":10263,"tokens_out":483,"duration_ms":8286,"concrete_test":"Independently re-derive the packing inequality for the special case of equal part sizes n_i = d: confirm that the number of (permutation, terminal) pairs is exactly k! d and that injectivity still forces k! ≤ d^{k-1}, then check that Stirling’s lower bound k! > (k/e)^k already contradicts k ≥ e d. If this elementary special case holds, the general argument is secure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central packing argument of Theorem 3 is elementary and appears correct: after selecting one in-neighbor per other class, each (permutation, terminal vertex) pair produces a unique transversal of the parts; distinct permutations on the same transversal would yield oppositely oriented subpaths whose union contains a rainbow cycle, a contradiction. Injectivity immediately yields (k-1)! ∑ n_i ≤ ∏ n_i. AM-GM plus Stirling then forces k < e d whenever every part has size ≤ d, so R(d) < e d. The randomized recovery (Lemma 4) re-uses the same counting and gives success probability > 1-1/d. The EFX corollary is the standard payoff of any linear upper bound once Proposition 2 (quoted from Chaudhury et al.) is granted; the paper itself notes that the √(n/ε) barrier is inherent to that reduction. No hidden assumption, free parameter, or circular step is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the rainbow cycle number R(d): the largest number of parts in a directed multipartite graph with parts of size at most d, the in-neighbor condition (every vertex has an in-neighbor in every other part), and no rainbow directed cycle. The authors prove the packing inequality (k-1)! ∑ |V_i| ≤ ∏ |V_i| for any such rainbow-cycle-free graph on k parts (Theorem 3). Combined with AM–GM and Stirling, this yields R(d) < e d, resolving the conjecture that R(d) is linear and matching the known lower bound R(d) ≥ d up to a constant factor. Via the reduction of Chaudhury et al., this implies every additive n-agent instance admits a partial (1-ε)-EFX allocation with O(√(n/ε)) unallocated goods (Theorem 1), which is asymptotically optimal for that reduction; a randomized algorithm finds such an allocation in expected polynomial time (Lemma 4). The same counting idea gives H(ℓ) = Θ(ℓ²) for the rainbow path degree, with brief applications to few valuation types, Nash welfare, and zero-sum cycles in groups.","tokens_in":10415,"tokens_out":1109,"duration_ms":31341,"significance":"The result closes the main open conjecture on R(d) with a short, elementary packing argument and immediately improves the best known guarantee on unallocated goods for approximate EFX from O_ε(√(n log n)) to O(√(n/ε)). The bound is asymptotically tight for the rainbow-cycle reduction itself, which the authors correctly identify as a square-root barrier inherent to that method rather than a limitation of their combinatorial bound. Strengths include a fully written self-contained proof of the packing inequality, an explicit constant e, a matching randomized recovery algorithm with concrete success probability > 1-1/d, and clean corollaries (quadratic rainbow path degree; short alternate O(|Γ|) proof for zero-sum cycles). This is a clear, high-value contribution to discrete fair division and combinatorial extremal graph theory.","major_comments":[],"minor_comments":[{"comment":"Title line and running header contain a spurious space: \"APPROXIMA TE EFX\". Fix throughout.","section":"Title"},{"comment":"In the proof of Theorem 3, the phrase \"Retaining only these chosen edges cannot create a rainbow cycle\" is correct but slightly abrupt; a half-sentence noting that any rainbow cycle in the thinned graph is already a rainbow cycle in G would make the reduction fully explicit for non-specialist readers.","section":"Section 3, Theorem 3"},{"comment":"Lemma 4 states expected O(k²) time after preprocessing. It would help to state the preprocessing cost explicitly (O(k ∑ n_i) or O(k² d) when parts have size ≤ d) so that the end-to-end claim in Proposition 2/Theorem 1 is self-contained.","section":"Lemma 4"},{"comment":"Table 1 header \"O(√n)\" for this paper omits the 1/√ε dependence that Theorem 1 states; writing O(√(n/ε)) (or \"O_ε(√n)\") would match the theorem and the earlier rows' ε-dependence.","section":"Table 1"},{"comment":"Section 5: the cyclic construction proving R(d) ≥ d is standard; a one-line pointer that it is exactly the construction of Chaudhury et al. [12] (already cited) would avoid any impression of a new lower-bound argument.","section":"Section 5"},{"comment":"Minor typography: \"Mészáros\" appears with encoding artifacts in the references and body (\"M´ esz´ aros\"); normalize accented names.","section":"References / Section 7"}],"recommendation":"accept","confidential_remarks":"The central combinatorial argument is short, correct, and of the quality one expects for a strong theory acceptance. The quantitative EFX claim rests entirely on the black-box reduction of Chaudhury et al. (Proposition 2); that is ordinary and properly attributed, and the authors are explicit that the √(n/ε) barrier is inherent to the reduction. The AI-use declaration is unusually candid but does not affect correctness; the mathematics checks out independently. Suitable for acceptance with only copy-editing."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing to know is that the packing inequality in Theorem 3 is short, correct, and new: after fixing one in-neighbor per other class, the map from (permutation, terminal vertex) to transversal is injective because opposing orders on the same set would close a rainbow cycle. Double counting plus AM-GM plus Stirling immediately forces R(d)<ed. That settles the O(d) conjecture and, via the existing Chaudhury et al. reduction, yields partial (1-ε)-EFX with O(√(n/ε)) unallocated goods—the best asymptotic the reduction can give, since R(d)≥d already forces the square-root barrier.\n\nWhat the paper does well: the argument is self-contained and elementary, the randomized recovery lemma re-uses the same counting with success probability >1-1/d and expected O(k²) time, and the same idea pins H(ℓ)=Θ(ℓ²). The write-up is honest about the barrier and about the remaining gap to the conjectured R(d)=d. Citations look complete and the AI-use disclosure is explicit; neither affects the math.\n\nSoft spots are minor and proportional. The EFX numerical claim rides entirely on Proposition 2 from prior work; if that accounting were off the combinatorial bound would still stand. The algorithm is randomized and the author notes they do not know how to derandomize at the linear threshold. The constant e is not tight, and the zero-sum-cycle corollary is only an alternate proof of a known linear bound. None of these undercut the main result.\n\nThis is for people who work on approximate EFX, rainbow-cycle combinatorics, or zero-sum problems in groups. The proof is short enough that a reading group can check it live. I would send it to peer review without hesitation; a serious editor should too. Engage with it—cite the packing inequality and the R(d)<ed bound when you need the linear guarantee.","headline":"Clean elementary proof that R(d)<ed, resolving the linear conjecture and giving the best asymptotic unallocated-goods bound the rainbow-cycle reduction can deliver.","tokens_in":11083,"tokens_out":504,"would_cite":true,"duration_ms":13244,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","05C20","68R10"],"pacs":[],"model":"grok-4.5","headline":"The rainbow cycle number is linear: every multipartite digraph with the in-neighbor property and no rainbow cycle has fewer than e·d parts of size at most d, which yields partial (1−ε)-EFX with only O(√(n/ε)) unallocated goods.","keywords":["EFX","fair division","rainbow cycle number","additive valuations","approximate envy-freeness","multipartite digraphs","zero-sum cycles"],"falsifier":"Exhibit a directed multipartite digraph with the in-neighbor property, part size at most d, no rainbow cycle, and at least ⌈e d⌉ parts; or, for a concrete small d, decide by exhaustive or SAT search whether R(d) already meets or exceeds ⌊e d⌋.","tokens_in":11110,"feed_emoji":"⚖️","tokens_out":1024,"duration_ms":32204,"temperature":0.7,"pith_summary":"Whether every additive fair-division instance has a complete EFX allocation is still open. A standard workaround leaves some goods unallocated and asks only for (1−ε)-EFX. Bounds on a combinatorial quantity called the rainbow cycle number R(d) convert directly into bounds on how many goods must be left out. This paper proves the long-conjectured linear upper bound R(d) < e d, improving the previous O(d log d). The resulting guarantee is a partial (1−ε)-EFX allocation with O(√(n/ε)) unallocated goods—the best asymptotic number the rainbow-cycle reduction can ever deliver—and a randomized algorithm finds it in expected polynomial time.","feed_headline":"Rainbow cycle number is linear: R(d) under e·d","feed_subtitle":"Partial (1−ε)-EFX now leaves only O(√(n/ε)) goods unallocated—the best this reduction can give.","key_machinery":"The packing inequality: after choosing one in-neighbor from each other class for every vertex, each pair (permutation of the classes, terminal vertex) builds a unique rainbow path; distinct pairs produce distinct transversals, because two different orders on the same vertex set would create a rainbow cycle. Counting these paths yields the factorial-versus-product inequality.","core_discovery":"In any directed k-partite graph whose every vertex has an in-neighbor in every other part and that contains no rainbow cycle, the packing inequality (k−1)! ∑|V_i| ≤ ∏|V_i| holds. When every part has size at most d this forces k! ≤ d^{k−1}, hence k < e d, so the rainbow cycle number satisfies R(d) < e d.","pith_inferences":["Because R(d) ≥ d is already known, the expression 2n/(ε d) + R(d) is minimized at Θ(√(n/ε)); further improvements inside the rainbow-cycle framework cannot beat this square-root barrier.","The still-open conjecture R(d) = d would simultaneously give the sharp zero-sum bound n(Γ) ≤ |Γ| + 1 for every finite group and the cleanest possible constant in the EFX reduction.","Derandomizing the O(k²)-time rainbow-cycle finder at the linear threshold remains open and would turn the whole EFX procedure deterministic."],"forward_implications":["Every additive n-agent instance admits a partial (1−ε)-EFX allocation with O(√(n/ε)) unallocated goods, found by a randomized expected polynomial-time algorithm.","When agents use only q distinct valuations the same argument leaves only O(√(q/ε)) goods unallocated.","Starting from a suitable high-Nash-welfare seed yields the same unallocated-goods bound while preserving a (1/(2−ε))-approximation to maximum Nash welfare.","The same counting shows the rainbow path degree H(ℓ) is Θ(ℓ²).","The bound supplies a short alternate proof that every finite group Γ has zero-sum cycle number n(Γ) = O(|Γ|)."],"fun_headline_variants":["Rainbow cycle number is linear: R(d) < e·d","R(d) < ed proves linear bound for rainbow cycles","Linear R(d) gives partial (1-ε)-EFX with O(√(n/ε)) left","Conjecture resolved: rainbow cycle number R(d) under ed","Best rainbow-cycle EFX reduction: O(√(n/ε)) unallocated"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The translation from the combinatorial bound into an EFX guarantee rests entirely on an earlier reduction that splits leftover goods into high-demand items (at most 2n/(ε d) of them) and low-demand items whose “champion graph” is rainbow-cycle-free and therefore of size at most R(d).","fun_headline_variants_meta":{"raw":{"variants":["Rainbow cycle number is linear: R(d) < e·d","R(d) < ed proves linear bound for rainbow cycles","Linear R(d) gives partial (1-ε)-EFX with O(√(n/ε)) left","Conjecture resolved: rainbow cycle number R(d) under ed","Best rainbow-cycle EFX reduction: O(√(n/ε)) unallocated"]},"model":"grok-4.5","effort":"low","cost_usd":0.004195,"raw_usage":{"total_tokens":1287,"prompt_tokens":773,"num_sources_used":0,"completion_tokens":110,"cost_in_usd_ticks":41948000,"prompt_tokens_details":{"text_tokens":773,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":404,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":773,"tokens_out":110,"duration_ms":7941,"temperature":1.0,"reasoning_tokens":404,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T00:21:42.961515+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a directed multipartite digraph with the in-neighbor property, part size at most d, no rainbow cycle, and at least ⌈e d⌉ parts; or, for a concrete small d, decide by exhaustive or SAT search whether R(d) already meets or exceeds ⌊e d⌋.","supporting_citations":[],"review_version":1}