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-4Optimization 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

Let b:V→Z0+b: V \to \mathbb{Z}_0^+ be a symmetric crossing submodular function with b(∅)=0b(\emptyset) = 0 and b(X)≡∣X∩Tb∣mod  2b(X) \equiv |X \cap T_b| \mod 2. Then there exists a pairing MM on TbT_b that satisfies (17).

Context

Candidate 4 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: for a finite set VV, let b:2V→Z≥0b:2^V\to \mathbb Z_{\ge0} be symmetric, crossing submodular, b(∅)=0b(\varnothing)=0, and let

    Tb={v∈V:b({v}) is odd}.T_b=\{v\in V: b(\{v\})\text{ is odd}\}.

    Assume

    b(X)≡∣X∩Tb∣(mod2)∀X⊆V.b(X)\equiv |X\cap T_b|\pmod 2\qquad \forall X\subseteq V.

    A pairing MM on TbT_b is a perfect matching of TbT_b, and

    dM(X)=∣{uv∈M:∣X∩{u,v}∣=1}∣.d_M(X)=|\{uv\in M: |X\cap\{u,v\}|=1\}|.

    The conjecture says that some pairing MM satisfies

    dM(X)≤b(X)∀X⊆V.(17)d_M(X)\le b(X)\qquad \forall X\subseteq V. \tag{17}

    The source text uses b(X)b(X), so the displayed b:V→Z≥0b:V\to\mathbb Z_{\ge0} is necessarily a shorthand/typo for b:2V→Z≥0b:2^V\to\mathbb Z_{\ge0}.

    Result: The statement is false.

    Let V=F23V=\mathbb F_2^3, ∣V∣=8|V|=8. Represent each x∈Vx\in V by the vector x~=(1,x)∈F24\tilde x=(1,x)\in\mathbb F_2^4, and let r(S)r(S) be the binary matroid rank of {x~:x∈S}\{\tilde x:x\in S\}. Define

    b(S)=r(S)+r(V∖S)−4.b(S)=r(S)+r(V\setminus S)-4.

    This is the connectivity function of a matroid, hence symmetric and submodular, therefore crossing submodular. Also b(∅)=0b(\varnothing)=0.

    Its values are:

    b(S)={0,∣S∣=0,8,1,∣S∣=1,7,2,∣S∣=2,6,3,∣S∣=3,5,2,∣S∣=4 and S is an affine plane of F23,4,∣S∣=4 and S is not an affine plane.b(S)= \begin{cases} 0,& |S|=0,8,\\ 1,& |S|=1,7,\\ 2,& |S|=2,6,\\ 3,& |S|=3,5,\\ 2,& |S|=4\text{ and }S\text{ is an affine plane of }\mathbb F_2^3,\\ 4,& |S|=4\text{ and }S\text{ is not an affine plane.} \end{cases}

    Thus Tb=VT_b=V, and b(S)≡∣S∣(mod2)b(S)\equiv |S|\pmod2 for every S⊆VS\subseteq V.

    Now let M={{pi,qi}:i=1,…,4}M=\{\{p_i,q_i\}:i=1,\dots,4\} be any pairing of VV. Put di=pi+qi∈F23∖{0}d_i=p_i+q_i\in\mathbb F_2^3\setminus\{0\}. Since the pairs partition VV,

    d1+d2+d3+d4=∑x∈F23x=0.d_1+d_2+d_3+d_4=\sum_{x\in\mathbb F_2^3}x=0.

    Every linear relation among the did_i's has even support: support size 11 is impossible because di≠0d_i\ne0, and support size 33 would force the remaining dj=0d_j=0. Hence the prescription ℓ(di)=1\ell(d_i)=1 is consistent, so there exists a nonzero linear functional ℓ:F23→F2\ell:\mathbb F_2^3\to\mathbb F_2 with ℓ(di)=1\ell(d_i)=1 for all ii.

    Let

    H={x∈F23:ℓ(x)=0}.H=\{x\in\mathbb F_2^3:\ell(x)=0\}.

    Then HH is an affine plane. For every pair {pi,qi}\{p_i,q_i\},

    ℓ(pi)+ℓ(qi)=ℓ(pi+qi)=1,\ell(p_i)+\ell(q_i)=\ell(p_i+q_i)=1,

    so exactly one endpoint lies in HH. Therefore

    dM(H)=4.d_M(H)=4.

    But HH is an affine plane, so b(H)=2b(H)=2. Thus

    dM(H)=4>b(H),d_M(H)=4>b(H),

    contradicting (17). Since MM was arbitrary, no feasible pairing exists.

    Verification audit: all hypotheses are satisfied; in fact bb is fully submodular, stronger than crossing submodular. The parity condition holds with Tb=VT_b=V. The failure is nondegenerate and not caused by an endpoint convention.

    Citation: Problem source: A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti, “Recent results on well-balanced orientations,” Discrete Optimization 5 (2008), Section 10, Question 9 / corresponding report numbering. Counterexample above is constructed here.

    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 counterexample attacks the correct statement dM(X)≤b(X)d_M(X)\le b(X). The function bb is a matroid connectivity function, hence symmetric, nonnegative, and submodular (so crossing submodular), with b(∅)=0b(\emptyset)=0 and the required parity condition Tb=VT_b=V. The linear-algebra argument correctly shows that every pairing of V=F23V=\mathbb F_2^3 is crossed by some affine plane HH, giving dM(H)=4>b(H)=2d_M(H)=4>b(H)=2. I found no prior same or stronger published resolution in the searched literature.

      Novelty assessment

      TYPE2

      Classification rationale: This appears to be a genuinely new negative resolution of a published open problem. The construction is short, but it is not a routine corollary: it gives a fully submodular/matroid-connectivity counterexample to a question explicitly left open for symmetric crossing submodular functions. Its significance is niche rather than broad, so not TYPE3, but it is plausibly publishable as a short note in a standard discrete optimization/combinatorics journal.

      Literature check: I found the original problem in Bernáth–Iwata–T. Király–Z. Király–Szigeti, §10: in the published version it is Question 9; the report/metadata numbering appears to call it Question 11. The same section gives a counterexample only for arbitrary symmetric skew-submodular functions, and explicitly says the crossing-submodular/global case is open.

      Searches over OpenAlex/citation data, arXiv records, CORE/repository metadata, Bing/Jina exact-phrase searches, and the source paper’s citing literature did not reveal this counterexample or any stronger negative result. Relevant later papers on odd-vertex pairings and well-balanced orientations, especially Hörsch’s “Checking the admissibility of odd-vertex pairings is hard” and Hörsch–Szigeti on degree-constrained well-balanced orientations, address algorithmic questions for graph pairings/orientations, not the existence question for arbitrary symmetric crossing submodular functions. I also found no relevant hits for the matroid-connectivity/AG(3,2)/affine-plane style counterexample.

      Citation: Original problem: A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti, “Recent results on well-balanced orientations,” Discrete Optimization 5 (2008), 663–676, §10, Question 9 / report Question 11, 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.