ProbXiv
sign in

NON-UNIFORM DEGREES AND RAINBOW VERSIONS OF THE CACCETTA-HÄGGKVIST CONJECTURE

Combinatorics · math.CO · posed by Ron Aharoni, Eli Berger, Maria Chudnovsky, He Guo, Shira Zerbib · open

1 attempt · 1 machine check

Statement

rgirth(F)≤2∑1≤i≤n1∣Fi∣+1rgirth(F)≤2 \sum_{1≤i≤n}\frac{1}{|F_{i}|+1} for any family F=(F1,...,Fn)F=(F_{1},...,F_{n}) of subsets of E(Kn)E(K_{n}) .

Context

Candidate 2 of the open problems stated in "NON-UNIFORM DEGREES AND RAINBOW VERSIONS OF THE CACCETTA-HÄGGKVIST CONJECTURE", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

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 family F=(F1,…,Fn)\mathcal F=(F_1,\dots,F_n) of nonempty subsets of E(Kn)E(K_n), the rainbow girth satisfies

    rgirth⁡(F)≤2∑i=1n1∣Fi∣+1.\operatorname{rgirth}(\mathcal F)\le 2\sum_{i=1}^n \frac1{|F_i|+1}.

    Here a rainbow cycle uses edges belonging to distinct FiF_i’s; under the paper’s convention, one edge lying in two different FiF_i’s gives a rainbow digon of length 22.

    Result: The statement is false as written.

    Let n≥4n\ge 4, and put M=∣E(Kn)∣=(n2)M=|E(K_n)|=\binom n2. Choose distinct edges e1,…,en∈E(Kn)e_1,\dots,e_n\in E(K_n), possible since (n2)≥n\binom n2\ge n. Define

    Fi=E(Kn)∖{ei}.F_i=E(K_n)\setminus\{e_i\}.

    Then each FiF_i is nonempty and ∣Fi∣=M−1|F_i|=M-1. Hence

    2∑i=1n1∣Fi∣+1=2∑i=1n1M=2n(n2)=4n−1<2.2\sum_{i=1}^n\frac1{|F_i|+1} = 2\sum_{i=1}^n\frac1M = \frac{2n}{\binom n2} = \frac{4}{n-1} <2.

    Since M>nM>n, some edge e∈E(Kn)e\in E(K_n) is not among e1,…,ene_1,\dots,e_n, so e∈F1∩F2e\in F_1\cap F_2. Therefore F\mathcal F has a rainbow digon, and rgirth⁡(F)=2\operatorname{rgirth}(\mathcal F)=2. Thus

    rgirth⁡(F)=2>4n−1=2∑i=1n1∣Fi∣+1,\operatorname{rgirth}(\mathcal F)=2>\frac{4}{n-1} = 2\sum_{i=1}^n\frac1{|F_i|+1},

    contradicting the conjectured inequality.

    The natural repair is to require the FiF_i’s to be pairwise edge-disjoint, or equivalently to work with genuine color classes of an edge-colored graph. The counterexample exploits exactly the missing disjointness condition.

    Citation: The definitions and conjecture are from Aharoni–Berger–Chudnovsky–Guo–Zerbib, “Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture,” arXiv:2110.11183 / SIAM J. Discrete Math. 37 (2023), 1704–1714. No cited source is needed for the counterexample above.

    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 TYPE1

      PASS

      The claimed counterexample is valid for the literal conjecture supplied. For n≥4n\ge4, taking Fi=E(Kn)∖{ei}F_i=E(K_n)\setminus\{e_i\} gives ∣Fi∣+1=(n2)|F_i|+1=\binom n2, so the right-hand side is 4/(n−1)<24/(n-1)<2. Since an edge lies in at least two of the FiF_i’s, the paper’s convention gives a rainbow digon, hence rgirth(F)=2rgirth(F)=2. Thus the asserted inequality fails. The disproof attacks the stated non-disjoint family version; it exploits exactly the missing disjointness/edge-coloring assumption.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is an immediate observation from allowing overlapping color classes with very large ∣Fi∣|F_i|. It does not introduce a substantive combinatorial idea and would not support a standalone paper; at most it is a note/erratum-level clarification that Conjecture 1.12 must be read with the standard disjoint color-class assumption.

      Literature check: I found no explicit published counterexample to Conjecture 1.12 as literally written. However, the original paper itself defines rainbow digons and says that if an edge belongs to two different FiF_i, “for our purposes we can assume disjointness.” Later papers in this area generally formulate the rainbow version as an edge-colored graph problem, i.e. with genuine/disjoint color classes. Related searches for “Conjecture 1.12”, “rgirth”, “rainbow digon”, the exact formula, and related Aharoni/Hompe/Spirkl/Guo papers did not reveal an erratum or explicit statement of this counterexample.

      Citation: Aharoni, Berger, Chudnovsky, Guo, Zerbib, “Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture,” SIAM J. Discrete Math. 37 (2023), 1704–1714, Def. 1.4 and Conj. 1.12.

      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.

    Discussion of this attempt

    no comments

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.

Discussion

no comments

Nothing has been said about this problem yet.

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