{"id":"068f07e3-0eb4-4a9e-9680-e6033e408441","arxiv_id":"2411.13202","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A connected graph admits a strong orientation for every crossing family whose members have at least two boundary edges, resolving a conjecture in the theory of disjoint dijoins.","lead":"A connected graph, together with a crossing family of vertex sets where each set has at least two boundary edges, always admits an orientation in which every set has both an incoming and an outgoing edge. The result proves a conjecture of Chudnovsky and others about packing dijoins, and it constrains any counterexample to the Edmonds-Giles conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the proof of Theorem 1 is sound, and the terse reductions in Section 4 can be filled in without changing the conclusion.","rationale":"The reader's ACCEPT is appropriate. I independently re-derived the two reductions the reader flagged and found them standard and valid. The central Theorem 1 proof relies only on cited box-TDI results and the algebraic manipulation of the divergence operator; no hidden assumption or circularity surfaced. Section 5's discussion of the two-component obstruction is a genuine limitation of the method, not an error in the proved theorems. The concrete test above would remove the only stylistic weakness, but it is a verification step, not a correctness risk.","tokens_in":8047,"tokens_out":36065,"duration_ms":371326,"concrete_test":"Write out the two Section 4 reductions as formal lemmas: (1) for a contracted cycle C, prove that every dicut U of D meeting V(C) properly has at least one outgoing C-arc in J'_1 and one in J'_2; (2) for deleted v0, show any dicut U of D' with weight less than 2 and C∩U nonempty yields a dicut U∪{v0} of D of the same weight, while if C∩U is empty then U lifts to a D-dicut of unchanged weight. If both proofs close, the induction in Theorem 2 is complete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the argument in good faith and do not find a load-bearing gap. The proof of Theorem 1 is a valid reduction to the box-TDI intersection theorem: x' is feasible for the two crossing-submodular systems, integrality of the polyhedron supplies an integral x, and weak connectivity of the arbitrary orientation supplies an integral transshipment y; the thresholding step converts integral y to a 0-1 solution. The only genuinely terse part is Section 4's two 'readily checked' reductions. They are not fully written out, but they are correct: contracting a cycle preserves the minimum dicut weight because every dicut of the contracted digraph lifts to a dicut of the original containing either all or none of the cycle, and for dicuts that split the cycle the two sets J'_1 and J'_2 each contain at least one outgoing cycle arc; deleting a vertex v0 not incident to weight-1 arcs is sound because a hypothetical new dicut U of D' with C∩U nonempty would force all in-neighbors of v0 into U, making U∪{v0} a dicut of D with the same outgoing weight, contradicting the hypothesis. Thus the theorems stand as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves two theorems in combinatorial optimization. Theorem 1 states that for a connected graph G=(V,E) and a crossing family C over V with |δ_G(U)| ≥ 2 for all U in C, there is an orientation of G in which every set in C has both an outgoing and an incoming arc. The proof reduces the problem to finding a 0-1 solution of a system of submodular-flow inequalities, obtains an integral solution via the box-TDI theorem for intersections of two crossing-submodular systems, and then rounds it to a 0-1 solution. Theorem 2 states that in a weighted digraph with 0/1 weights, minimum dicut weight at least 2, and weight-1 arcs forming a weakly bridge-connected subdigraph, there exist two disjoint dijoins contained in the weight-1 arcs. This is derived from Theorem 1 by induction, with two reduction steps (cycle contraction and deletion of a vertex not incident to weight-1 arcs) and a base case in which the weight-1 arcs form a spanning tree. The paper also includes a discussion of the difficulties in extending the approach to two weakly connected components and an appendix with a fractional example showing that a certain polytope is not integral.","tokens_in":8256,"tokens_out":17627,"duration_ms":162706,"significance":"If the results are correct, Theorem 1 resolves a conjecture of Chudnovsky, Edwards, Kim, Scott, and Seymour on disjoint dijoins, and Theorem 2 provides a unified proof of previously known planar and caterpillar cases as well as an extension to weakly bridge-connected weight-1 subdigraphs. The proof of Theorem 1 is clean and elegant: it formulates the orientation problem as a submodular-flow feasibility problem, uses the box-TDI property of the intersection of two crossing-submodular systems to obtain an integral transshipment, and then rounds it to a 0-1 solution. The paper is self-contained modulo standard theorems from combinatorial optimization, has no fitted parameters, and includes an explicit counterexample in the appendix, which is a sign of careful work. The main limitation, as the authors themselves state, is that the induction in Theorem 2 relies on two reductions that are asserted as 'readily checked' rather than proved in full; these reductions are routine and correct, but a skeptical reader would want them written out.","major_comments":[],"minor_comments":[{"comment":"The two claims introduced by 'It can be readily checked' are load-bearing for the induction in Theorem 2 and should be expanded into brief proofs. In Step 1, please explain why any dicut of D contains either all or none of the contracted cycle (otherwise an arc of the cycle would enter the dicut), and why the lifted dicuts in D/C have the same outgoing weight. In Step 2, please spell out the case distinction for a dicut U of D' based on whether U contains an out-neighbor of v0; if it does not, U is already a dicut of D, and if it does, then all in-neighbors of v0 must lie in U and U∪{v0} is a dicut of D with the same outgoing weight.","section":"Section 4, Steps 1 and 2"},{"comment":"In the displayed derivation of x'(U) ≤ f_i(U), the inequality |δ(U)| ≥ 2 is used for U in C2 as well as for U in C1. This is true because U = V\\W for some W in C and |δ(U)| = |δ(W)| ≥ 2, but it is not stated explicitly; please add a short sentence to make the step fully transparent.","section":"Section 3, Step 3"},{"comment":"The term 'cycle' in 'Suppose A1 contains a cycle C' and in 'A1 contains no cycle' should be clarified to mean a cycle in the underlying undirected graph. If 'cycle' meant a directed cycle, the claim that the underlying graph is a tree would be false, since a digraph with no directed cycle can still have an undirected cycle (e.g., a directed acyclic orientation of a triangle).","section":"Section 4, Step 3"},{"comment":"There are several typographical errors in the list of tight constraints: some closing parentheses are missing, for example 'x⋆({2, 3, 4, 9, 10} = f1(...)' and 'x⋆({0, 1, 2, 3, 4, 7, 8, 9, 10} = f1(...)', and 'Schriver' should be 'Schrijver'.","section":"Appendix A"},{"comment":"The phrase 'at most two weakly bridge-connected components' appears to be a typo for 'at most two weakly connected components', based on the subsequent sentence that mentions a spanning forest with two weakly connected components. Please correct this.","section":"Section 5"},{"comment":"The sentence 'surprisingly, this system is TDI [1]' cites the authors' own paper [1] as a side remark. This is fine, but it is not needed for the main proof and could be omitted to avoid any appearance of relying on an unpublished result.","section":"Section 3, final note"}],"recommendation":"minor_revision","confidential_remarks":"The paper is sound and well within the scope of math.CO. The proof of Theorem 1 is a clean and correct reduction to known box-TDI results, and Theorem 2 follows from it via standard but somewhat terse reductions. The only request is to expand the two 'readily checked' reductions in Section 4 and fix the minor typographical issues. I see no citation concerns or novelty disclosure issues; the paper honestly discusses limitations and provides a counterexample in the appendix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should read this one before it gets too deeply into the pipeline. The paper proves the main conjecture of Chudnovsky, Edwards, Kim, Scott and Seymour on disjoint dijoins: every weighted digraph with 0/1 weights, all dicuts weight at least 2, and weight-1 arcs weakly bridge-connected, admits two disjoint dijoins in the weight-1 arcs. That alone is a substantive result. But the real engine is Theorem 1, a clean strong-orientation statement for crossing families: if every set in the family has edge cut size at least 2, there is an orientation where each set has both an outgoing and an incoming arc. That theorem is new and is proved through an intersection of two crossing-submodular systems, invoking box-TDI and an integral transshipment argument. The proof of Theorem 1 is compact and sound: the 0/1 rounding step, the integrality step, and the transshipment step all check out. I tried to find a gap and did not. The paper is honest about what the method does not do, with a whole section on why the two-component case fails and an explicit fractional example in the appendix.\n\nThe only soft spot is Section 4, where the two induction reductions are described as 'readily checked' and not written out fully. They are load-bearing for Theorem 2. I went through them: contracting a cycle works because each dicut of the contracted digraph lifts to a dicut that contains either all or none of the cycle, and if it splits the cycle then each of the two half-cycles contributes an outgoing arc; deleting a vertex with no weight-1 incident arcs works because any new dicut in the reduced digraph can be lifted to one in the original with no larger weight. Both are correct as stated, but a referee should ask for them to be expanded, since the paper's main result depends on them.\n\nWho gets value: anyone working on dijoins, dicuts, or strong orientations, and people who like seeing box-TDI used as a hammer. The citation pattern is appropriate — the paper does not oversell its novelty, and the self-citation [1] is only tangential. I would send this to a strong referee rather than desk-reject, and I expect it to land in a good combinatorics journal after the reductions in Section 4 are written out properly.","headline":"Strong, clean proof of the main disjoint dijoins conjecture; the only terse spots are two standard reductions that a referee should ask to have expanded.","tokens_in":8813,"tokens_out":2215,"would_cite":true,"duration_ms":17372,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every connected graph admits a strong orientation for any crossing family whose cuts have size at least two.","keywords":["crossing family","strong orientation","dijoin","Edmonds-Giles conjecture","Woodall's conjecture","submodular flow","total dual integrality","0-1 weights"],"falsifier":"A single connected graph $G$ with a crossing family $\\mathcal{C}$ satisfying $|\\delta_G(U)| \\ge 2$ for all $U\\in\\mathcal{C}$ but admitting no strong orientation would refute Theorem 1; equivalently, a weighted digraph with 0/1 weights, minimum dicut weight 2, and weakly bridge-connected weight-1 arcs that has no two disjoint dijoins inside those arcs would refute Theorem 2.","tokens_in":7853,"feed_emoji":"🧭","tokens_out":10801,"duration_ms":89682,"temperature":0.7,"pith_summary":"The paper proves that every connected graph $G=(V,E)$ carries a strong orientation for any crossing family $\\mathcal{C}$ over $V$ whose cuts all have size at least two: one can direct the edges so that every set in $\\mathcal{C}$ receives at least one outgoing and one incoming arc. This is Theorem 1, and it is the missing step that confirms the main conjecture of [3] on disjoint dijoins. As Theorem 2, the paper derives that in any weighted digraph with 0/1 weights, minimum dicut weight at least two, and weakly bridge-connected weight-1 arcs, there are two disjoint dijoins lying inside the weight-1 arcs. If correct, this pins down the counterexample of [9] to the Edmonds-Giles conjecture: the nonzero-weight arcs in a minimal counterexample with minimum dicut weight two must be disconnected.","feed_headline":"Every connected graph admits a strong orientation for any crossing family","feed_subtitle":"This proves the 2016 disjoint-dijoins conjecture and sharpens the Edmonds-Giles counterexample picture.","key_machinery":"The load-bearing objects are crossing families and the crossing-submodular functions $f_i(U)=|\\delta^+_D(U)|-1$ defined on $\\mathcal{C}$ and on the complementary family $\\{V\\setminus U: U\\in\\mathcal{C}\\}$. The orientation problem is encoded as the system $y(\\delta^+(U))-y(\\delta^-(U))\\le f_i(U)$ for all $i=1,2$ and all $U$ in the respective family. This system is the intersection of two submodular flow systems and is therefore box-TDI by a standard theorem quoted as Theorem 4 in the paper; the generalized set-covering form of the inequalities is what permits rounding an integral solution to a 0/1 solution, and the transshipment theorem quoted as Theorem 3 supplies the integral solution once a vertex potential $x'$ with $x'(V)=0$ is exhibited.","core_discovery":"Theorem 1 states that a connected graph admits a strong orientation for a crossing family provided every cut in the family has at least two edges. The proof works by orienting the graph arbitrarily and asking whether some subset of arcs can be flipped so that each member of the family ends up with both an outgoing and an incoming arc. This is modelled as a 0/1 feasibility problem over a system of generalized set-covering inequalities, which is shown to be integral through the intersection of two submodular-flow systems. An integral solution is obtained from a feasible vertex-potential vector via a transshipment, and a rounding argument turns it into a 0/1 solution, i.e., an actual re-orientation. Theorem 2 then follows by an induction whose base case is exactly the tree case of Theorem 1, converting the strong orientation into two disjoint dijoins contained in the weight-1 arcs.","pith_inferences":["A likely algorithmic reading of the proof is that the strong orientation can be found in polynomial time: the underlying system is box-TDI, so a 0/1 solution can be obtained by linear programming, though the paper does not discuss complexity.","One could test whether the crossing condition is necessary by building a non-crossing set family with all cuts of size at least two on a connected graph and checking whether a strong orientation always exists; a counterexample would show that crossing is the essential hypothesis.","Written out in full, the two 'readily checked' reduction lemmas in the induction might yield an explicit construction of the two dijoins from the orientation, turning Theorem 2 into a constructive packing statement.","The equivalence in Section 6 suggests that the same orientation theorem likely applies to other problems that can be phrased as finding 0/1 points in submodular-flow systems with set-covering inequalities."],"forward_implications":["Theorem 2 verifies the main conjecture of [3] on disjoint dijoins for weakly bridge-connected weight-1 arcs.","In every minimal counterexample to the Edmonds-Giles conjecture with minimum dicut weight 2, the nonzero-weight arcs must be disconnected; the weakly bridge-connected case is now settled.","The result extends the earlier theorem of [12] from subgraphs whose components are all 2-edge-connected to the weakly bridge-connected case.","The proof shows that Theorem 1 is exactly the $\\tau=2$ case of a proposed strengthening-set partition conjecture, a conjecture that would imply Woodall's conjecture.","The Appendix A example shows that the natural extension to two weakly connected components does not preserve integrality of the corresponding linear system, so that case requires new machinery."],"supporting_citations":[{"why":"Supplies the recent total dual integrality result for the specific submodular-flow system used in the rounding step.","marker":"[1]"},{"why":"States the disjoint-dijoin conjecture that Theorem 2 verifies and the special cases the paper builds on.","marker":"[3]"},{"why":"Introduces the weighted Woodall conjecture (Edmonds-Giles) that Theorem 2 addresses.","marker":"[6]"},{"why":"Provides the counterexample showing that dicut weight 2 alone does not imply two disjoint dijoins when the weight-1 arcs are disconnected.","marker":"[9]"},{"why":"Gives the transshipment theorem (Theorem 3) used to obtain an integral solution from a vertex potential.","marker":"[10]"},{"why":"Gives the box-TDI theorem for intersections of two submodular flow systems (Theorem 4), the integrality engine of the proof.","marker":"[11]"},{"why":"Contains the earlier dijoin-packing result for 2-edge-connected components that Theorem 2 extends to weakly bridge-connected subgraphs.","marker":"[12]"}],"fun_headline_variants":["Strong orientation always exists for crossing families","Disjoint-dijoins conjecture settled by strong orientations","Crossing families now admit strong orientations","Graph orientation proves crossing family conjecture","Strong orientation solves disjoint-dijoins conjecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The induction proving Theorem 2 rests on two reduction steps—contracting a cycle in the weight-1 arcs and deleting a vertex with no incident weight-1 arc—that the paper asserts are 'readily checked' but does not prove in detail; the entire dijoin result depends on both steps preserving the minimum dicut weight and the dijoin property.","fun_headline_variants_meta":{"raw":{"variants":["Strong orientation always exists for crossing families","Disjoint-dijoins conjecture settled by strong orientations","Crossing families now admit strong orientations","Graph orientation proves crossing family conjecture","Strong orientation solves disjoint-dijoins conjecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00021,"raw_usage":{"total_tokens":1367,"prompt_tokens":858,"completion_tokens":509,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":445}},"tokens_in":474,"tokens_out":509,"duration_ms":5560,"temperature":1.0,"reasoning_tokens":445,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:46:28.124420+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single connected graph $G$ with a crossing family $\\mathcal{C}$ satisfying $|\\delta_G(U)| \\ge 2$ for all $U\\in\\mathcal{C}$ but admitting no strong orientation would refute Theorem 1; equivalently, a weighted digraph with 0/1 weights, minimum dicut weight 2, and weakly bridge-connected weight-1 arcs that has no two disjoint dijoins inside those arcs would refute Theorem 2.","supporting_citations":[{"cited_title":"Combinatorica, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the recent total dual integrality result for the specific submodular-flow system used in the rounding step."},{"cited_title":"Disjoint dijoins","cited_arxiv_id":null,"evidence_quote":"States the disjoint-dijoin conjecture that Theorem 2 verifies and the special cases the paper builds on."},{"cited_title":"A min-max relation for submodular functions on graphs","cited_arxiv_id":null,"evidence_quote":"Introduces the weighted Woodall conjecture (Edmonds-Giles) that Theorem 2 addresses."},{"cited_title":"Combinatorial Optimization: Polyhedra and Efficiency Volume 1","cited_arxiv_id":null,"evidence_quote":"Gives the transshipment theorem (Theorem 3) used to obtain an integral solution from a vertex potential."},{"cited_title":"Combinatorial Optimization: Polyhedra and Efficiency Volume 2","cited_arxiv_id":null,"evidence_quote":"Gives the box-TDI theorem for intersections of two submodular flow systems (Theorem 4), the integrality engine of the proof."},{"cited_title":"Visualizing, finding a nd packing dijoins","cited_arxiv_id":null,"evidence_quote":"Contains the earlier dijoin-packing result for 2-edge-connected components that Theorem 2 extends to weakly bridge-connected subgraphs."}],"review_version":1}