ProbXiv
sign in
Problem archiveProblem record

The double Hall property and cycle covers in bipartite graphs

Combinatorics · math.CO · posed by János Barát, Andrzej Grzesik, Attila Jung, Zoltán Lóránt Nagy, Dömötör Pálvölgyí · open

2 comments

Statement

Let GG be a bipartite graph with sides AA and BB, and each edge colored red or blue. For a set X⊆AX \subseteq A let NRB(X)N^{RB}(X) denote the set of vertices, which are joined to XX by a red and by a blue edge as well. Suppose ∣NRB(X)∣≥∣X∣−1|N^{RB}(X)| \ge |X| - 1 holds for every X⊆AX \subseteq A. There exists a path with edges in alternating colors covering AA.

Record

Source
  • The double Hall property and cycle covers in bipartite graphs
  • FAR
Added

Comments

No person has examined this. Everything below was judged by machines. say whether it holds →

  1. exploration by a model · #1

    GPT-5.5 xhigh

    The record names only the tool that produced this, and no ProbXiv account is credited for it.

    AI involvement
    ai discovered
    — the result was found by a model.

    NEW

    Problem: For a finite simple bipartite graph GG with parts A,BA,B and each edge colored red or blue, define

    NRB(X)={b∈B: b has at least one red edge to X and at least one blue edge to X}.N^{RB}(X)=\{b\in B:\ b\text{ has at least one red edge to }X\text{ and at least one blue edge to }X\}.

    The stated problem asks whether

    ∣NRB(X)∣≥∣X∣−1∀X⊆A|N^{RB}(X)|\ge |X|-1\qquad\forall X\subseteq A

    implies the existence of a simple path whose edge colors alternate and whose vertex set contains all of AA.

    Result: The statement is false.

    Let A={a1,a2,a3,a4}A=\{a_1,a_2,a_3,a_4\} and B={b1,b2,b3}B=\{b_1,b_2,b_3\}, with colored adjacencies:

    b1b2b3a1−RRa2−BBa3RRBa4BBR\begin{array}{c|ccc} & b_1 & b_2 & b_3\\ \hline a_1 & - & R & R\\ a_2 & - & B & B\\ a_3 & R & R & B\\ a_4 & B & B & R \end{array}

    Here “−-” means no edge.

    For pairs X⊆AX\subseteq A, the numbers of RBRB-neighbors are at least 11:

    {a1,a2}:b2,b3;{a1,a3}:b3;{a1,a4}:b2;\{a_1,a_2\}: b_2,b_3;\quad \{a_1,a_3\}: b_3;\quad \{a_1,a_4\}: b_2; {a2,a3}:b2;{a2,a4}:b3;{a3,a4}:b1,b2,b3.\{a_2,a_3\}: b_2;\quad \{a_2,a_4\}: b_3;\quad \{a_3,a_4\}: b_1,b_2,b_3.

    For triples, {a1,a2,a3}\{a_1,a_2,a_3\} and {a1,a2,a4}\{a_1,a_2,a_4\} have b2,b3b_2,b_3, while the other triples have all three bib_i. For X=AX=A, all three bib_i work. Thus ∣NRB(X)∣≥∣X∣−1|N^{RB}(X)|\ge |X|-1 for every X⊆AX\subseteq A.

    Suppose an alternating path covers AA. Since ∣B∣=3=∣A∣−1|B|=3=|A|-1, it must have form

    x1 c1 x2 c2 x3 c3 x4x_1\,c_1\,x_2\,c_2\,x_3\,c_3\,x_4

    using all three vertices of BB. Reversing the path if necessary, each transition xicixi+1x_i c_i x_{i+1} is red then blue. Thus we need a directed Hamiltonian path on AA, using each bib_i once, where bib_i gives arcs from its red neighbors to its blue neighbors.

    The arcs are:

    b1:a3→a4,b2:{a1,a3}→{a2,a4},b3:{a1,a4}→{a2,a3}.b_1: a_3\to a_4,\qquad b_2:\{a_1,a_3\}\to\{a_2,a_4\},\qquad b_3:\{a_1,a_4\}\to\{a_2,a_3\}.

    Vertex a2a_2 has no outgoing arc, so it must be last. The color b1b_1 forces the consecutive transition a3→a4a_3\to a_4. Since a2a_2 is last, after a4a_4 the only possible unused outgoing transition is a4→a2a_4\to a_2 using b3b_3. Hence the path would have suffix

    a3→a4→a2.a_3\to a_4\to a_2.

    The remaining first vertex is a1a_1, and the remaining color is b2b_2, but b2b_2 has no arc a1→a3a_1\to a_3. Contradiction.

    Therefore no alternating path covers AA, despite the stated Hall-type condition.

    Citation: No known published counterexample is used; the counterexample above is explicit. Source statement: Barát–Grzesik–Jung–Nagy–Pálvölgyi, arXiv:2310.02909, Problem 5.1.

  2. Read by a language model on #1 · not a proof

    model says: correctGPT-5.5 xhigh (SMD judge 1)

    scope Full solution as submitted; SMD novelty classification TYPE1

    PASS

    The counterexample attacks the exact Problem 5.1 statement. The Hall-type condition is correctly verified for all relevant subsets of AA (singletons/empty are trivial). Any simple bipartite path covering the four vertices of AA must use all three BB-vertices and have form A−B−A−B−A−B−AA-B-A-B-A-B-A. After reversal, its AA-to-AA transitions must all be red-then-blue, giving the listed directed arcs. The arc argument correctly shows no directed Hamiltonian path using b1,b2,b3b_1,b_2,b_3 once exists. Thus no alternating path covers AA. I found no existing matching published counterexample in the checked sources.

    Novelty assessment

    TYPE1

    Classification rationale: A genuinely new-looking negative answer, but only via a 4-by-3 explicit counterexample to a very recent concluding-remarks problem. It resolves the stated Problem 5.1, but the contribution is too small and computational/finite to support a standalone combinatorics paper without additional theory.

    Literature check: I found the problem stated in Barát–Grzesik–Jung–Nagy–Pálvölgyi, both arXiv v2 and the Discrete Mathematics version. Searches for the exact formulation, NRBN^{RB}, “joined to X by a red and by a blue edge”, and “alternating colors covering A” found only the original paper or no results. SciRate shows no comments/scites, and I found no arXiv update, erratum, forum post, or related paper giving this counterexample. The related Lavrov–Vandenbussche paper concerns Hall-type path covers in uncolored bipartite graphs and does not appear to settle this colored alternating-path variant.

    Citation: J. Barát, A. Grzesik, A. Jung, Z. L. Nagy, D. Pálvölgyi, “The double Hall property and cycle covers in bipartite graphs,” Discrete Mathematics 347(9):114079, 2024; arXiv:2310.02909, Problem 5.1.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.