ProbXiv
sign in

Anti-van der Waerden numbers on Graphs

Combinatorics · math.CO · posed by Zhanar Berikkyzy, Alex Schulte, Elizabeth Sprangel, Shanise Walker, Nathan Warnberg, Michael Young · open

1 attempt · 1 machine check

Statement

If GG is a graph with a dominating vertex, then aw(G,k)≤k+1\text{aw}(G, k) \le k + 1.

Context

Candidate 2 of the open problems stated in "Anti-van der Waerden numbers on Graphs", 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 conjecture: for every finite simple graph GG and integer k≥3k\ge3, if GG has a dominating vertex, then

    aw⁡(G,k)≤k+1.\operatorname{aw}(G,k)\le k+1.

    Here a graph kk-AP is an ordered set v1,…,vkv_1,\dots,v_k of vertices with dG(vi,vi+1)=d<∞d_G(v_i,v_{i+1})=d<\infty constant; degenerate APs repeat vertices and cannot be rainbow. aw⁡(G,k)\operatorname{aw}(G,k) is the least rr such that every exact rr-coloring of V(G)V(G) contains a rainbow nondegenerate kk-AP.

    Result: The conjecture is false. For any k≥8k\ge8, let GkG_k have vertex set

    {u}∪C∪L,∣C∣=k−3,L={ℓ1,ℓ2,ℓ3},\{u\}\cup C\cup L,\qquad |C|=k-3,\quad L=\{\ell_1,\ell_2,\ell_3\},

    where {u}∪C\{u\}\cup C is a clique and each ℓi\ell_i is adjacent only to uu. Then uu is dominating and

    ∣V(Gk)∣=1+(k−3)+3=k+1.|V(G_k)|=1+(k-3)+3=k+1.

    Since diam⁡(Gk)=2\operatorname{diam}(G_k)=2, any nondegenerate kk-AP has common distance 11 or 22.

    If the common distance is 11, the AP is a simple path. After removing uu, the components are Kk−3K_{k-3} and three isolated vertices. A simple path can pass through uu at most once, so it meets at most two components of Gk−uG_k-u, hence has at most

    1+(k−3)+1=k−11+(k-3)+1=k-1

    vertices.

    If the common distance is 22, then uu cannot appear, and no two vertices of CC can be consecutive since they are adjacent. Thus vertices of CC must be separated by leaves. With only three leaves, such a sequence has length at most 4+3=7<k4+3=7<k.

    So GkG_k contains no nondegenerate kk-AP. Therefore, by the defining convention,

    aw⁡(Gk,k)=∣V(Gk)∣+1=k+2>k+1.\operatorname{aw}(G_k,k)=|V(G_k)|+1=k+2>k+1.

    Taking k=8k=8 gives a concrete counterexample.

    Citation: Original conjecture and definitions: Z. Berikkyzy, A. Schulte, E. Sprangel, S. Walker, N. Warnberg, and M. Young, “Anti-van der Waerden numbers on Graphs,” arXiv:1802.01509, Conjecture 5.3. The 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 claimed disproof attacks the correct Conjecture 5.3 and is rigorous. In the constructed graph, the universal vertex is dominating and ∣V∣=k+1|V|=k+1. Any nondegenerate kk-AP has common distance 11 or 22. Distance 11 APs are simple paths and have at most k−1k-1 vertices in this graph; distance 22 APs cannot include the dominating vertex, and clique vertices must be separated by the three leaves, giving length at most 7<k7<k for k≥8k\ge8. Thus no nondegenerate kk-AP exists, so aw⁡(Gk,k)=∣V∣+1=k+2>k+1\operatorname{aw}(G_k,k)=|V|+1=k+2>k+1.

      I found no indication in the accessible literature/search results that this counterexample or a stronger resolution was already known.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is genuinely new as far as I can tell, but it is very elementary: it exploits a dominating-vertex graph on k+1k+1 vertices with no nondegenerate kk-AP. This is a short observation/refutation rather than a standalone publishable combinatorics paper, unless combined with a broader corrected theory.

      Literature check: I found the original conjecture in Berikkyzy et al., arXiv:1802.01509, Conjecture 5.3. The URL in the input, arXiv:1906.09171, is unrelated. Searches around the exact conjecture, “dominating vertex” + “anti-van der Waerden,” aw(G,k)aw(G,k), “rainbow arithmetic progression” on graphs, and related anti-van der Waerden graph papers, including the later arXiv:2310.20462 paper on graph products with trees, did not reveal a known counterexample, erratum, or stronger published resolution.

      Citation: Z. Berikkyzy, A. Schulte, E. Sprangel, S. Walker, N. Warnberg, and M. Young, “Anti-van der Waerden numbers on Graphs,” arXiv:1802.01509, Conjecture 5.3.

      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.