ProbXiv
sign in
machine only

Recent results on well-balanced orientations

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

recent-results-on-well-balanced-orientations-3Optimization and Controlmath.COmath.OCposed by Attila Bernáth, Satoru Iwata, Tamás Király, Zoltán Király, Zoltán Szigetirecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

For every graph G=(V+s,E)G = (V + s, E) with d(s)≥4d(s) \ge 4 there exist rs,st∈Ers, st \in E such that for every best-balanced orientation G⃗rt\vec{G}_{rt} of GrtG_{rt}, G⃗:=G⃗rt−rt+rs+st\vec{G} := \vec{G}_{rt} - rt + rs + st is a best-balanced orientation of GG.

Context

Candidate 3 of the open problems stated in "Recent results on well-balanced orientations", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement: in finite loopless multigraphs, an orientation is best-balanced if it is smooth,

    ∣d+(v)−d−(v)∣≤1∀v,|d^+(v)-d^-(v)|\le 1\quad\forall v,

    and well-balanced,

    λG⃗(x,y)≥⌊λG(x,y)/2⌋∀x≠y,\lambda_{\vec G}(x,y)\ge \big\lfloor \lambda_G(x,y)/2\big\rfloor \quad\forall x\ne y,

    where λ\lambda denotes local edge/arc-connectivity. For edges rs,strs,st, GrtG_{rt} is obtained by deleting them and adding rtrt; lifting replaces r→tr\to t by r→s→tr\to s\to t. This is the standard Nash-Williams “best-balanced” terminology used in the cited splitting-off section.

    Result: The statement is false.

    Let

    V(G)={s,a,b,c,d,e,f}V(G)=\{s,a,b,c,d,e,f\}

    and

    E(G)={sa,sb,sc,sf,ac,ad,ae,af,be,bf,ce}.E(G)=\{sa,sb,sc,sf,ac,ad,ae,af,be,bf,ce\}.

    Then dG(s)=4d_G(s)=4. Also λG(s,a)=4\lambda_G(s,a)=4: the four edge-disjoint ss-aa paths are

    sa,sbea,sca,sfa,sa,\quad sbea,\quad sca,\quad sfa,

    and dG(s)=4d_G(s)=4 gives the matching upper bound.

    For every ordered split of two edges incident with ss, the following table gives a best-balanced orientation of the split graph whose lift is not well-balanced. In the table, x→yx\to y is the oriented new split edge, and repeated arcs mean parallel edges in the split graph.

    new arcorientation of Gxybad cut after liftinga→bs→c,f→s,a→c,a→d,e→a,f→a,b→e,b→f,c→e,a→ba→s, X={a,c,d,e}b→as→c,f→s,a→c,a→d,a→e,f→a,e→b,b→f,c→e,b→aa→s, X={a,c,d,e}a→cs→b,f→s,a→c,d→a,a→e,f→a,e→b,b→f,c→e,a→cs→a, X={s,b,c,e}c→as→b,f→s,a→c,a→d,e→a,f→a,e→b,b→f,c→e,c→aa→s, X={a,d}a→fs→b,c→s,a→c,a→d,e→a,f→a,e→b,b→f,c→e,a→fs→a, X={s,b,f}f→as→b,c→s,a→c,a→d,a→e,f→a,b→e,b→f,e→c,f→aa→s, X={a,c,d,e}b→cs→a,f→s,a→c,a→d,a→e,f→a,e→b,b→f,c→e,b→ca→s, X={a,c,d,e}c→bs→a,f→s,a→c,a→d,a→e,f→a,b→e,b→f,e→c,c→ba→s, X={a,c,d,e}b→fs→a,c→s,a→c,a→d,e→a,f→a,e→b,b→f,c→e,b→fa→s, X={a,d}f→bs→a,c→s,a→c,a→d,e→a,f→a,e→b,b→f,c→e,f→ba→s, X={a,d}c→fs→a,b→s,a→c,a→d,a→e,f→a,b→e,f→b,e→c,c→fa→s, X={a,c,d,e}f→cs→a,b→s,a→c,a→d,a→e,f→a,e→b,b→f,c→e,f→ca→s, X={a,c,d,e}\begin{array}{c|l|l} \text{new arc} & \text{orientation of }G_{xy} & \text{bad cut after lifting}\\ \hline a\to b & s\to c,f\to s,a\to c,a\to d,e\to a,f\to a,b\to e,b\to f,c\to e,a\to b & a\to s,\ X=\{a,c,d,e\}\\ b\to a & s\to c,f\to s,a\to c,a\to d,a\to e,f\to a,e\to b,b\to f,c\to e,b\to a & a\to s,\ X=\{a,c,d,e\}\\ a\to c & s\to b,f\to s,a\to c,d\to a,a\to e,f\to a,e\to b,b\to f,c\to e,a\to c & s\to a,\ X=\{s,b,c,e\}\\ c\to a & s\to b,f\to s,a\to c,a\to d,e\to a,f\to a,e\to b,b\to f,c\to e,c\to a & a\to s,\ X=\{a,d\}\\ a\to f & s\to b,c\to s,a\to c,a\to d,e\to a,f\to a,e\to b,b\to f,c\to e,a\to f & s\to a,\ X=\{s,b,f\}\\ f\to a & s\to b,c\to s,a\to c,a\to d,a\to e,f\to a,b\to e,b\to f,e\to c,f\to a & a\to s,\ X=\{a,c,d,e\}\\ b\to c & s\to a,f\to s,a\to c,a\to d,a\to e,f\to a,e\to b,b\to f,c\to e,b\to c & a\to s,\ X=\{a,c,d,e\}\\ c\to b & s\to a,f\to s,a\to c,a\to d,a\to e,f\to a,b\to e,b\to f,e\to c,c\to b & a\to s,\ X=\{a,c,d,e\}\\ b\to f & s\to a,c\to s,a\to c,a\to d,e\to a,f\to a,e\to b,b\to f,c\to e,b\to f & a\to s,\ X=\{a,d\}\\ f\to b & s\to a,c\to s,a\to c,a\to d,e\to a,f\to a,e\to b,b\to f,c\to e,f\to b & a\to s,\ X=\{a,d\}\\ c\to f & s\to a,b\to s,a\to c,a\to d,a\to e,f\to a,b\to e,f\to b,e\to c,c\to f & a\to s,\ X=\{a,c,d,e\}\\ f\to c & s\to a,b\to s,a\to c,a\to d,a\to e,f\to a,e\to b,b\to f,c\to e,f\to c & a\to s,\ X=\{a,c,d,e\} \end{array}

    Each listed split orientation is smooth by direct degree count. In every split graph, all local connectivities are at most 33, except pairs involving the pendant vertex dd, whose requirement is 00. The displayed orientations contain a directed closed walk through {s,a,b,c,e,f}\{s,a,b,c,e,f\}, hence are strongly connected on these six vertices, so they are well-balanced.

    After lifting, the bad cut XX contains the source but not the target and has exactly one outgoing arc. Thus the lifted orientation has directed local connectivity at most 11 between ss and aa in one direction, while ⌊λG(s,a)/2⌋=2\lfloor\lambda_G(s,a)/2\rfloor=2. Hence the lift is not best-balanced.

    Since all twelve ordered choices of two incident edges at ss fail, no pair rs,strs,st satisfies the proposed property.

    Citation: Original open problem: Bernáth, Iwata, T. Király, Z. Király, and Szigeti, “Recent results on well-balanced orientations,” Discrete Optimization 5 (2008), 663–676, Section 6, Question 5. The counterexample above is not cited there.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE2

      PASS

      The proposed counterexample attacks the stated universal splitting-off question. The graph has d(s)=4d(s)=4 and λG(s,a)=4\lambda_G(s,a)=4. For each ordered split at ss, the table gives a smooth orientation of the split graph; since all relevant undirected local connectivities in the split graph are at most 33 and the six non-pendant vertices are strongly connected, these orientations are best-balanced. After lifting, the listed cut separates ss and aa in one direction with only one outgoing arc, so the lifted orientation has directed local connectivity at most 1<⌊4/2⌋=21<\lfloor 4/2\rfloor=2. Thus every possible pair of incident edges at ss fails the required “for every best-balanced orientation” property. I found no evidence of an already-known counterexample in the available searches.

      Novelty assessment

      TYPE2

      Classification rationale: Genuinely new as far as I can determine. It gives a small counterexample to an explicit splitting-off question from Bernáth–Iwata–T. Király–Z. Király–Szigeti. The result is narrow and proof-by-case/checking rather than methodologically deep, so it is low-end TYPE2, not TYPE3. Still, because the question was a proposed route to a simpler proof of Nash-Williams’ best-balanced orientation theorem, a clean counterexample is plausibly publishable as a short note in a standard graph theory/combinatorial optimization journal.

      Literature check: I found no prior counterexample or stronger published disproof. Searches over OpenAlex for “best-balanced”, “splitting off”, “for every best-balanced orientation”, and exact fragments of Question 5 returned only the original paper, related theses/surveys, and later work on well-balanced-orientation complexity/odd-vertex pairings. The 2022 Hörsch–Szigeti paper still frames Nash-Williams’ best-balanced theorem as lacking a simple proof and does not mention a resolution of this splitting-off question. The cited works and later citations of the original paper do not appear to contain the proposed counterexample.

      Citation: Original open problem: A. Bernáth, S. Iwata, T. Király, Z. Király, and Z. Szigeti, “Recent results on well-balanced orientations,” Discrete Optimization 5 (2008), 663–676, Section 6, Question 5, DOI 10.1016/j.disopt.2008.03.001.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.