ProbXiv
sign in

Generalized regular Turán numbers

Combinatorics · math.CO · posed by Dániel Gerbner, Hilal Hama Karim · open

1 attempt · 1 machine check

Statement

Let χ(H)≤k≥3\chi(H)\le k\ge 3 . Then rex(n,H,Kk+1)=(1+o(1))N(H,T(n,k))rex(n,H,K_{k+1})=(1+o(1))N(H,T(n,k)) .Moreover, if n is sufficiently large and is divisible by k, then rex(n,H,Kk+1)=N(H,T(n,k))rex(n,H,K_{k+1})=N(H,T(n,k)) .

Context

Candidate 1 of the open problems stated in "Generalized regular Turán numbers", 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 finite simple graphs, with N(H,G)\mathcal N(H,G) the number of not necessarily induced copies of HH in GG, and

    rex⁡(n,H,F)=max⁡{N(H,G):∣V(G)∣=n, G regular and F-free},\operatorname{rex}(n,H,F)=\max\{\mathcal N(H,G): |V(G)|=n,\ G\text{ regular and }F\text{-free}\},

    Conjecture 1.4 asserts that if k≥3k\ge3 and χ(H)≤k\chi(H)\le k, then

    rex⁡(n,H,Kk+1)=(1+o(1))N(H,T(n,k)),\operatorname{rex}(n,H,K_{k+1})=(1+o(1))\mathcal N(H,T(n,k)),

    and, for all sufficiently large nn divisible by kk,

    rex⁡(n,H,Kk+1)=N(H,T(n,k)).\operatorname{rex}(n,H,K_{k+1})=\mathcal N(H,T(n,k)).

    Result: The conjecture is false.

    Take k=3k=3 and H=K10,1,1H=K_{10,1,1}, the complete tripartite graph with parts of sizes 10,1,110,1,1. Then χ(H)=3\chi(H)=3.

    Let nn be divisible by 3030. Construct GnG_n with parts

    ∣A∣=2n/5,∣B∣=∣C∣=3n/10.|A|=2n/5,\qquad |B|=|C|=3n/10.

    Put all edges between AA and BB, all edges between AA and CC, and put an n/5n/5-regular bipartite graph between BB and CC. This exists, e.g. cyclically. Then every vertex has degree 3n/53n/5, so GnG_n is regular. Since GnG_n is tripartite, it is K4K_4-free.

    Let inj⁡(H,G)\operatorname{inj}(H,G) denote injective homomorphisms. Since N(H,G)=inj⁡(H,G)/∣Aut⁡(H)∣\mathcal N(H,G)=\operatorname{inj}(H,G)/|\operatorname{Aut}(H)|, comparing injective counts suffices.

    For T(n,3)T(n,3), with parts of size m=n/3m=n/3,

    inj⁡(H,T(n,3))=6m2(m)10.\operatorname{inj}(H,T(n,3))=6m^2(m)_{10}.

    Indeed, the two singleton vertices must go to two distinct parts, and the 1010-vertex independent part is forced into the third part.

    In GnG_n, count only embeddings sending the 1010-vertex part into AA and the two singleton vertices to an edge between BB and CC. Since

    e(B,C)=3n10⋅n5=3n250,e(B,C)=\frac{3n}{10}\cdot\frac n5=\frac{3n^2}{50},

    we get

    inj⁡(H,Gn)≥2e(B,C)(2n/5)10=3n225(2n/5)10.\operatorname{inj}(H,G_n)\ge 2e(B,C)(2n/5)_{10} =\frac{3n^2}{25}(2n/5)_{10}.

    Hence

    inj⁡(H,Gn)inj⁡(H,T(n,3))≥950∏i=092n/5−in/3−i→950(65)10>1.\frac{\operatorname{inj}(H,G_n)}{\operatorname{inj}(H,T(n,3))} \ge \frac{9}{50}\prod_{i=0}^{9}\frac{2n/5-i}{n/3-i} \to \frac{9}{50}\left(\frac65\right)^{10}>1.

    Therefore, for all sufficiently large multiples of 3030,

    N(H,Gn)>N(H,T(n,3)).\mathcal N(H,G_n)>\mathcal N(H,T(n,3)).

    Thus

    rex⁡(n,H,K4)>N(H,T(n,3))\operatorname{rex}(n,H,K_4)>\mathcal N(H,T(n,3))

    on an infinite sequence of nn divisible by 33, disproving both the exact and asymptotic claims.

    This is not a degenerate boundary case: HH is connected, has no isolated vertices, and satisfies χ(H)=k=3\chi(H)=k=3.

    Citation: Definitions and target conjecture: Gerbner–Karim, “Generalized regular Turán numbers,” arXiv:2311.01579, Conjecture 1.4. Counterexample above is constructed here.

    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 attacks the stated conjecture correctly. For k=3k=3 and H=K10,1,1H=K_{10,1,1}, the constructed graph GnG_n is 3n/53n/5-regular and K4K_4-free. The count in T(n,3)T(n,3) is exactly 6(n/3)2(n/3)106(n/3)^2(n/3)_{10}, while GnG_n already has at least 3n225(2n/5)10\frac{3n^2}{25}(2n/5)_{10} injective copies. The ratio tends to

      950(65)10>1,\frac{9}{50}\left(\frac65\right)^{10}>1,

      so for infinitely many large nn divisible by 33, rex(n,H,K4)>N(H,T(n,3))rex(n,H,K_4)>N(H,T(n,3)). This disproves both the exact and asymptotic claims. I found no prior similar result in the available literature search.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample appears genuinely new, but it is a short elementary construction and copy-count comparison against T(n,3)T(n,3). It disproves a recent conjecture, but likely would not support a standalone standard-journal paper without broader classification/corrected conjectures.

      Literature check: I found no published or preprint source giving this counterexample or otherwise stating Conjecture 1.4 is false. The original arXiv paper still has only its initial version. Later related sources, including Gerbner–Palmer’s generalized Turán survey and Gerbner–Karim–Kucheriya’s abstract chromatic-number paper, discuss related ordinary/regular Turán frameworks but do not contain this regular counterexample. Ordinary generalized Turán literature already notes that balanced Turán graphs need not optimize arbitrary complete multipartite HH, but that does not by itself resolve the regular version here.

      Citation: D. Gerbner and H. Hama Karim, “Generalized regular Turán numbers,” arXiv:2311.01579, Conjecture 1.4. Related background: E. Győri, J. Pach, M. Simonovits, Graphs Combin. 7 (1991), 31–37; D. Gerbner and C. Palmer, arXiv:2506.03418.

      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.