{"id":"aa50b961-845a-4b3a-9553-d6e47410ae67","arxiv_id":"2607.26606","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every strongly connected digraph with cyclic in/out-neighborhoods has at least 7n/3 arcs; every strongly 2-connected such digraph has at least 8n/3 arcs, and both bounds are tight.","lead":"This paper proves tight lower bounds on the number of arcs in strongly connected digraphs in which every vertex's in- and out-neighborhood contains a directed cycle. It answers natural extremal questions about sparse separators in digraphs and showcases discharging arguments for this setting.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 2 in Theorem 3 asserts d_D(v) ≥ 2ℓ+6 in the x=y case with no argument; the discharging bounds in Claims 7–9 rely on this degree threshold, so the proof of m ≥ 8n/3 is incomplete as written.","rationale":"The reader's weakest assumption is exactly the x=y degree bound in Claim 2. I agree that this is the single most load-bearing step for Theorem 3: the discharging proofs for vertices of degree 7–12 (Claims 4–9) invoke degree thresholds for the vertex v attached to a V4-path, and if that threshold is not rigorously established the final contradiction is unsupported. The concern is not fatal: the missing inference can plausibly be reconstructed from n≥9 and the fact that a component of D[V4] has no external adjacencies except through v and x. So the appropriate verdict remains CONDITIONAL: the main inequality is likely correct, but the proof needs a written justification of the x=y case. I do not see an internal inconsistency or a counterexample; hence no stronger action than CONDITIONAL is warranted. The reader's choice of weakest assumption was accurate, so agreement is 'agree' and no verdict adjustment is needed.","tokens_in":21990,"tokens_out":26454,"duration_ms":210916,"concrete_test":"Write out the missing case of Claim 2 in full: list all neighbors of V(P) away from P, use n≥9 to choose z outside P∪{v,x}, and prove from strong connectivity of D−x that v has at least one outgoing arc to a vertex outside P∪{v,x} and at least one incoming arc from such a vertex, so these add 2 to d_D(v). If this argument cannot be completed, then either weaken the bound to 2ℓ+4 and re-derive Claims 7–9, or find a strongly 2-connected neighborhood-cyclic digraph with n≥9 and a path component of D[V4] realizing the smaller degree; the latter would disprove Claim 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is the proof of Claim 2 (Proof of Theorem 3). For a path component P=u0...uℓ of D[V4], the proof shows V(P)∪{x,y}⊆N+(v)∩N-(v) and then states: 'If x=y, then, since D−x is strongly connected, we obtain that d_D(v)≥2ℓ+6' with no intermediate argument. In the x≠y case the bound is immediate: v has two opposite arcs to each of the ℓ+1 path vertices (2ℓ+2 arcs) and two opposite arcs to each of x and y (4 arcs), totaling 2ℓ+6. When x=y, only two arcs to x are present, giving only 2ℓ+4. The missing +2 must come from strong connectivity of D−x: because D[V4] is a component, every vertex of P has no neighbors outside P∪{v,x}; hence if n≥9 there is a vertex outside P∪{v,x}, and strong connectivity of D−x forces at least one arc from v to that outside set and one arc back into v, adding two incidences to d_D(v). The manuscript never supplies this. Claims 7, 8, and 9 repeatedly use d_D(w)≥6 or d_D(w)≥8 thresholds derived from this bound to limit how much charge a vertex sends; if the bound needed extra hypotheses (or only held with a smaller constant), the vertex-wise estimates c(u)≥16/3 could fail and the discharging contradiction would collapse. This is a genuine presentation gap in a load-bearing step, not a demonstrated counterexample.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies digraphs in which, for every vertex, both the out-neighborhood and the in-neighborhood induce a subdigraph containing a directed cycle (\"neighborhood-cyclic\"). It proves two extremal lower bounds. Theorem 2: every strongly connected neighborhood-cyclic digraph of order n≥5 and size m satisfies m≥7n/3, with equality if and only if the digraph belongs to a specified family D formed by cyclically arranged complete digraphs ↔K3 with exactly one arc between consecutive blocks. Theorem 3: every strongly 2-connected neighborhood-cyclic digraph of order n≥9 satisfies m≥8n/3. Both bounds are claimed best-possible. The proofs use discharging: in Theorem 2, initial charge d_D(u) is redistributed to degree-4 vertices to show final charge at least 14/3; in Theorem 3, a four-phase discharging argument shows final charge at least 16/3, contradicting m<8n/3.","tokens_in":22308,"tokens_out":21686,"duration_ms":190963,"significance":"If the proofs are correct, these are the first tight extremal results for neighborhood-cyclic digraphs and give a substantive directed analogue of recent undirected results on sparse cuts and cyclic neighborhoods. The discharging arguments are intricate and self-contained, with no fitted parameters; the extremal examples are explicit, and Theorem 2 includes a full equality characterization. The main value is the pair of tight bounds and the associated extremal family. However, two proof passages need expansion before the central claims are fully supported: the x=y case in Claim 2 of Theorem 3, and the global patching step in the equality case of Theorem 2.","major_comments":[{"comment":"The x=y case of Claim 2 is asserted without proof: \"If x=y, then, since D−x is strongly connected, we obtain that d_D(v)≥2ℓ+6.\" The arc count gives only 2ℓ+4. A proof is needed and can be supplied: since P is a component of D[V4], no vertex of P has an arc to/from x beyond the endpoint arcs x→u0 and uℓ→x, otherwise its degree would exceed 4. Since x∈V≥5 and n≥9, there is a vertex z outside {v}∪V(P)∪{x}. In D−x, vertices of P have no neighbours outside {v}∪V(P), so strong connectivity forces at least one arc from v to the outside and at least one arc from the outside to v; these two arcs add the missing +2. Please insert this or an equivalent argument. Claims 7–9 use degree thresholds derived from this bound, so this is load-bearing.","section":"Theorem 3, Claim 2 (Proof of Theorem 3)"},{"comment":"The final step \"Since D is strongly-connected and n≥5, this implies that D∈D\" is too compressed. The preceding paragraph proves only local alternatives for each degree-4 vertex. To establish the equality characterization one must argue globally: the K3 blocks are vertex-disjoint, there are no extra arcs between V≥5 and V4 beyond one incoming and one outgoing arc per block, the blocks are arranged in a directed cycle, and no other arcs exist. This patching is part of the theorem statement and should be proved explicitly.","section":"Theorem 2, equality case (end of proof)"}],"minor_comments":[{"comment":"The instruction \"For every arc e ... move ... from u to v\" should clarify that a double arc triggers two transfers, so that a vertex joined to u by a double arc receives twice the amount. This is the source of the factor 2 in later formulas (e.g., Case 2).","section":"Theorem 2, discharging definition"},{"comment":"The phrase \"adding ... an arc from some vertex\" should read \"exactly one arc\" for clarity, since the extremal family D permits exactly one arc between consecutive blocks.","section":"Definition of D"},{"comment":"The caption contains corrupted text: \"Double arcs are depicted as q q-.\"","section":"Figure 1 caption"},{"comment":"The line \"Since D is neighborhood-cyclic, there is a vertex v such that V(P)⊆N+(v)∩N-(v)\" repeats an argument from Theorem 2; a short justification or a reference to the earlier case would improve readability.","section":"Theorem 3, Claim 2"},{"comment":"Minor wording: \"arc between\" in the abstract and intro should probably be \"arc from ... to ...\" to avoid ambiguity about orientation.","section":"Abstract/Introduction"}],"recommendation":"major_revision","confidential_remarks":"The two proof gaps are local and repairable; the discharging framework appears sound and the bounds are likely correct. I recommend major revision rather than rejection. No circularity, fitted parameters, or invented entities were noted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two genuinely new extremal bounds here, and the main ideas are worth engaging with. But the proof of the second theorem is not complete as written.\n\nThe paper shows that a strongly connected neighborhood-cyclic digraph on n vertices has at least 7n/3 arcs, and a strongly 2-connected one at least 8n/3; both bounds are tight, with explicit extremal families. The discharging setup is adapted to digraphs with separate in/out neighborhoods, and that adaptation is the real contribution. Theorem 2's proof is detailed and mostly convincing, and the extremal digraph description in D is concrete.\n\nThe soft spots are in proportion. Theorem 2's equality characterization is a one-sentence jump from local configurations to the global D in D; that needs at least a paragraph. More importantly, Claim 2 in the proof of Theorem 3 asserts that when x=y, d_D(v) >= 2*ell + 6 for the path component P. The text says only that this follows from strong connectivity of D-x. It does not follow immediately: the direct count gives 2*ell + 4, and the extra +2 requires an argument that every vertex of P has no neighbors outside P union {v,x} and that strong connectivity of D-x forces arcs from v to the outside set and back. That argument is plausible — the stress-test reconstruction fills it in — but it is not in the manuscript. Since Claims 7-9 repeatedly use degree thresholds derived from this bound, the proof of m >= 8n/3 is incomplete as written.\n\nI don't think this is a counterexample to the theorem. The missing step is local and likely repairable. But it is exactly the kind of step that can hide a false subcase, and the authors should be asked to spell it out. The best-possible verification for the 8n/3 construction is also brief; I'd want that expanded.\n\nWho is this for: extremal digraph theorists working on sparse separators and neighborhood conditions. Outside that subfield, limited impact. It deserves a serious referee — the techniques are nontrivial and the results would be cited if they hold. My recommendation: send to peer review with a request for a revised proof of Claim 2 and the equality characterization, rather than desk reject.","headline":"Two genuinely new tight bounds for neighborhood-cyclic digraphs, with a fixable but load-bearing gap in the Theorem 3 proof.","tokens_in":22790,"tokens_out":2468,"would_cite":false,"duration_ms":22178,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C35","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"In every strongly connected digraph where each vertex has a cyclic out-neighborhood and in-neighborhood, the arc count must be at least 7n/3, and strong 2-connectivity pushes the floor to 8n/3; both bounds are best-possible.","keywords":["sparse separators","sparse vertex cuts","cyclic neighborhoods","digraphs","strong connectivity","strong 2-connectivity","extremal bounds","discharging method"],"falsifier":"A concrete way to test the paper's central claim is to search for a strongly 2-connected neighborhood-cyclic digraph with n≥9 and m<8n/3; any such digraph would refute Theorem 3. More locally, one can try to construct a strongly 2-connected neighborhood-cyclic digraph containing a directed path P=u0...uℓ inside V4 with a single external vertex x=y and d_D(v)≤2ℓ+5, which would directly contradict the unproved degree estimate in Claim 2.","tokens_in":21844,"feed_emoji":"📐","tokens_out":8307,"duration_ms":77363,"temperature":0.7,"pith_summary":"Let D be a digraph whose out-neighborhood and in-neighborhood at every vertex each contain a directed cycle. The paper establishes two tight lower bounds on the number of arcs of such a digraph: if D is strongly connected and has n≥5 vertices, then m≥7n/3, and if D is strongly 2-connected and n≥9, then m≥8n/3. Both bounds are best-possible, and the first has a complete equality characterization: extremal digraphs are built from disjoint complete digraphs of order 3 arranged in a directed cycle, with one arc between consecutive blocks. The motivation is the search for sparse separators: a digraph in which every neighborhood is cyclic is the natural obstruction to having an acyclic vertex cut, and these results show how strong connectivity combines with that obstruction to force density.","feed_headline":"Cyclic neighborhoods force 7n/3 arcs, or 8n/3 when 2-connected","feed_subtitle":"Two exact thresholds: strong connectivity alone gives 7n/3; strong 2-connectivity raises the floor to 8n/3.","key_machinery":"The proof mechanism is discharging. Vertices are grouped by total degree into classes V4, V5, etc. For Theorem 2, each vertex of degree at least 5 sends a fraction of its excess charge to its neighbors in V4, and the local analysis of the possible shapes of D[V4]—isolated vertices, directed cycles, and directed paths—shows every vertex finishes with charge at least 14/3. Since total initial charge is 2m, this gives m≥7n/3. For Theorem 3, a four-phase discharging scheme defines 'demanding' pairs (u, σ) for vertices of degree 4 or 5 with out-degree or in-degree 2, and high-degree vertices send their demands along specific arcs so that every final charge is at least 16/3. The key structural inp","core_discovery":"The central claim, on the paper's own terms, is that the neighborhood-cyclic condition is strong enough to force linear density once connectivity is imposed. A neighborhood-cyclic digraph has minimum out-degree and in-degree at least 2, so m≥2n trivially; the paper proves that strong connectivity raises this to m≥7n/3 for n≥5, with equality characterized by the family D, and that strong 2-connectivity raises it further to m≥8n/3 for n≥9. For the second bound, the paper shows it is best-possible by adding the arcs of a directed cycle through the extremal blocks of the first construction. The proofs are discharging arguments that track how many arcs must exist around vertices of low degree, an","pith_inferences":["A natural next question, left implicit by the paper, is whether strong 3-connectivity or general k-connectivity forces an even larger linear slope, and whether the coefficients 7/3 and 8/3 are the beginning of a sequence depending on k.","The target charge 16/3 in the second proof suggests that the extremal obstruction is a degree-4 vertex whose two out-neighbors and two in-neighbors each need compensation; a similar charging perspective may transfer to the undirected cyclic-neighborhood problem that motivated the paper.","One could test whether the equality cases for the 8n/3 bound admit a structural description as clean as the family D, since the paper proves best-possibility by example but does not characterize all extremal digraphs."],"forward_implications":["Every strongly connected neighborhood-cyclic digraph with n≥5 has m≥7n/3, improving the trivial m≥2n bound.","Every strongly 2-connected neighborhood-cyclic digraph with n≥9 has m≥8n/3, so the density threshold rises with connectivity.","The m≥7n/3 bound is tight exactly on the block-cycle family D: k≥2 disjoint complete digraphs of order 3 joined by one arc around a directed cycle.","The m≥8n/3 bound is also tight: a digraph realizing equality is obtained by taking a member of D and adding a directed cycle through vertices of degree 4.","As a direct contrapositive, any strongly connected neighborhood-cyclic digraph with fewer than 7n/3 arcs cannot be strongly connected, and any with fewer than 8n/3 arcs cannot be strongly 2-connected."],"fun_headline_variants":["Cyclic neighborhoods force 7n/3 arcs, 8n/3 if 2-connected","Tight arc bounds from cyclic neighborhoods: 7n/3, 8n/3","Strong connectivity raises cyclic-neighborhood arc floor to 7n/3","Minimum arcs in cyclic-neighborhood digraphs: 7n/3 or 8n/3","Cyclic neighborhoods need 7n/3 arcs, 8n/3 when 2-connected"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"In the proof of Theorem 3, Claim 2 asserts without an explicit argument that when a degree-4 path component P=u0...uℓ has its two outer neighbors x and y equal, the common doubly adjacent vertex v has total degree at least 2ℓ+6; the discharging estimates for vertices of degrees 6 through 12 rely on this bound, so if that step needs extra hypotheses, the 8n/3 conclusion may not follow.","fun_headline_variants_meta":{"raw":{"variants":["Cyclic neighborhoods force 7n/3 arcs, 8n/3 if 2-connected","Tight arc bounds from cyclic neighborhoods: 7n/3, 8n/3","Strong connectivity raises cyclic-neighborhood arc floor to 7n/3","Minimum arcs in cyclic-neighborhood digraphs: 7n/3 or 8n/3","Cyclic neighborhoods need 7n/3 arcs, 8n/3 when 2-connected"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000685,"raw_usage":{"total_tokens":2879,"prompt_tokens":617,"completion_tokens":2262,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":361,"completion_tokens_details":{"reasoning_tokens":2156}},"tokens_in":361,"tokens_out":2262,"duration_ms":17022,"temperature":1.0,"reasoning_tokens":2156,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T12:26:32.554371+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete way to test the paper's central claim is to search for a strongly 2-connected neighborhood-cyclic digraph with n≥9 and m<8n/3; any such digraph would refute Theorem 3. More locally, one can try to construct a strongly 2-connected neighborhood-cyclic digraph containing a directed path P=u0...uℓ inside V4 with a single external vertex x=y and d_D(v)≤2ℓ+5, which would directly contradict the unproved degree estimate in Claim 2.","supporting_citations":[],"review_version":1}