ProbXiv
sign in

The Maximum Number of Cliques in Graphs with Bounded Odd Circumference

Number theory · math.CO · math.NT · posed by Zequn Lv, Ervin Győri, Zhen He, Nika Salia, Chuanqi Xiao, Xiutao Zhu · open

1 attempt · 1 machine check

Statement

For integers nn, rr and a prime pp satisfying r<pr < p, we have ex(n,Kr,C≥pprime)≤n−1p−2(p−1r).\text{ex}(n, K_r, C_{\ge p}^{\text{prime}}) \le \frac{n-1}{p-2} \binom{p-1}{r}. Equality holds only for connected nn-vertex graphs consisting of n−1p−2\frac{n-1}{p-2} maximal 2-connected blocks each isomorphic to Kp−1K_{p-1}.

Context

Candidate 2 of the open problems stated in "The Maximum Number of Cliques in Graphs with Bounded Odd Circumference", 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: in finite simple graphs, let C≥pprime={Cq:q≥p, q prime}\mathcal C^{\mathrm{prime}}_{\ge p}=\{C_q:q\ge p,\ q\text{ prime}\}. The conjecture claims that for prime pp and r<pr<p,

    ex⁡(n,Kr,C≥pprime)≤n−1p−2(p−1r).\operatorname{ex}(n,K_r,\mathcal C^{\mathrm{prime}}_{\ge p}) \le \frac{n-1}{p-2}\binom{p-1}{r}.

    This is the nontrivial reading supported by the superscript “prime”; if instead C≥pprime\mathcal C^{\mathrm{prime}}_{\ge p} means all cycles of length at least pp, the statement is just Luo’s known theorem.

    Result: The reconstructed conjecture is false. Take r=2r=2, any odd prime pp, and G=Km,mG=K_{m,m} with m=2pm=2p, so n=4pn=4p. Since GG is bipartite, every cycle in GG has even length; the only even prime is 22, and simple graphs have no 22-cycles. Hence GG contains no cycle of prime length at least pp.

    But

    K2(G)=e(G)=m2=4p2,K_2(G)=e(G)=m^2=4p^2,

    whereas the conjectured bound gives

    n−1p−2(p−12)=4p−1p−2⋅(p−1)(p−2)2=(4p−1)(p−1)2<4p2.\frac{n-1}{p-2}\binom{p-1}{2} =\frac{4p-1}{p-2}\cdot \frac{(p-1)(p-2)}2 =\frac{(4p-1)(p-1)}2 <4p^2.

    Thus GG violates the claimed inequality. For instance, p=3,r=2,G=K2,3p=3,r=2,G=K_{2,3} already gives 6>46>4.

    Citation: No citation is needed for the counterexample. Under the alternative “all long cycles” reading, see Ruth Luo, The maximum number of cliques in graphs without long cycles, JCTB 128 (2018), 219–226.

    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 counterexample is valid and attacks the stated Conjecture 3. For p=3p=3, r=2r=2, G=K2,3G=K_{2,3} is bipartite, hence has no prime-length cycle ≥3\ge 3, but has 66 edges while the conjectured bound is

      5−13−2(22)=4.\frac{5-1}{3-2}\binom{2}{2}=4.

      Thus the claimed inequality is false. I found no prior published disproof in the searched literature.

      Novelty assessment

      TYPE1

      Classification rationale: The resolution is a very simple counterexample using bipartiteness: K2,3K_{2,3} (or Km,mK_{m,m}) has no odd, hence no prime-length, cycles ≥3\ge 3, but exceeds the conjectured r=2r=2 bound. This is an immediate observation from the standard characterization of bipartite graphs and is not substantial enough for a standalone paper, though it could merit an erratum/comment if the conjecture was indeed intended literally.

      Literature check: I found no published note, erratum, arXiv paper, forum post, alphaXiv/SciRate comment, or GitHub discussion explicitly giving this counterexample to Conjecture 3. Searches for the paper title, “Conjecture 3”, “bounded odd circumference”, “prime-length cycles”, K2,3K_{2,3}, and the extremal notation found only the original paper and unrelated work on prime-length cycles. The observation itself is standard folklore via “bipartite iff no odd cycles,” but I found no literature source presenting it as a disproof of this conjecture.

      Citation: No prior citation for the counterexample found. Original conjecture: Zequn Lv, Ervin Győri, Zhen He, Nika Salia, Chuanqi Xiao, Xiutao Zhu, “The maximum number of cliques in graphs with bounded odd circumference,” arXiv:2212.01989.

      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.