ProbXiv
sign in

The Maximum Number of Cliques in Graphs with Bounded Odd Circumference

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

1 attempt · 1 machine check

Statement

For an integer k≥2k \ge 2 and a sufficiently large nn. Let GG be an nn vertex C3ℓ+1C_{3\ell+1}-free graph for every integer ℓ≥k\ell \ge k. Then for every rr, 3k≥r≥23k \ge r \ge 2, the number of cliques of size rr in GG is at most n−13k−1(3kr).\frac{n-1}{3k-1} \binom{3k}{r}. Equality holds only for connected nn-vertex graphs consisting of n−13k−1\frac{n-1}{3k-1} maximal 2-connected blocks each isomorphic to K3kK_{3k}.

Context

Candidate 1 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: for every integer k≥2k\ge2, there is N(k)N(k) such that every n≥N(k)n\ge N(k) vertex simple graph GG containing no cycle C3ℓ+1C_{3\ell+1} for any integer ℓ≥k\ell\ge k satisfies, for every 2≤r≤3k2\le r\le 3k,

    kr(G)≤n−13k−1(3kr),k_r(G)\le \frac{n-1}{3k-1}\binom{3k}{r},

    where kr(G)k_r(G) is the number of rr-cliques. The quoted equality statement concerns block graphs made from copies of K3kK_{3k}.

    Result: The conjecture is false.

    Take k=2k=2 and, for any n≥14n\ge14, let

    G=K4,n−4.G=K_{4,n-4}.

    This graph is bipartite, so it has no odd cycles. Every cycle in K4,n−4K_{4,n-4} alternates between the two parts and therefore uses at most the four vertices in the smaller part, so every cycle has length at most 88. Hence GG contains no C3ℓ+1C_{3\ell+1} for any ℓ≥2\ell\ge2: the forbidden lengths are

    7,10,13,16,…,7,10,13,16,\dots,

    and GG has no odd cycles and no cycle of length at least 1010.

    For r=2r=2, the number of 22-cliques is the number of edges:

    k2(G)=e(G)=4(n−4).k_2(G)=e(G)=4(n-4).

    The conjectured bound gives

    n−13⋅2−1(62)=n−15⋅15=3(n−1).\frac{n-1}{3\cdot2-1}\binom{6}{2} =\frac{n-1}{5}\cdot15 =3(n-1).

    But

    4(n−4)>3(n−1)  ⟺  n>13.4(n-4)>3(n-1) \iff n>13.

    Thus for every n≥14n\ge14, GG satisfies the forbidden-cycle hypothesis but violates the claimed clique bound.

    This gives arbitrarily large counterexamples, so the phrase “sufficiently large nn” cannot save the statement. The defect is substantive: for even kk, the hypothesis allows bipartite graphs of even circumference 3k+23k+2, already giving too many edges.

    Citation: No known citation is needed for the counterexample. Source conjecture: Lv–Győri–He–Salia–Xiao–Zhu, “The Maximum Number of Cliques in Graphs with Bounded Odd Circumference,” arXiv:2212.01989.

    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. For k=2k=2, r=2r=2, G=K4,n−4G=K_{4,n-4} is bipartite, and every cycle has length at most 88, so it contains no C3ℓ+1C_{3\ell+1} for any ℓ≥2\ell\ge2. But

      e(G)=4(n−4)>3(n−1)=n−15(62)e(G)=4(n-4)>3(n-1)=\frac{n-1}{5}\binom62

      for every n>13n>13. Thus the conjectured bound fails for arbitrarily large nn. I found no evidence of a prior stronger/similar resolution.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is valid but very minor: it only uses the r=2r=2 edge case and the elementary graph K4,n−4K_{4,n-4}. This is an erratum-level observation rather than a standalone publishable combinatorics result.

      Literature check: I found the conjecture in the arXiv paper and published Annals of Combinatorics version. Searches for the title, arXiv ID, “Conjecture 2”, “C3ℓ+1C_{3\ell+1}-free”, “K4,n−4K_{4,n-4}”, and “bounded odd circumference counterexample” did not reveal an erratum, correction, forum note, or paper giving this counterexample. Nearby folklore about complete bipartite graphs and odd cycles is standard, but I found no explicit prior resolution of this conjecture.

      Citation: 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,” Annals of Combinatorics 28 (2024), 1119–1125, DOI: 10.1007/s00026-023-00682-y.

      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.