ProbXiv
sign in
machine only

On multicolor Ramsey number of paths versus cycles

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

on-multicolor-ramsey-number-of-paths-versus-cyclesCombinatoricsmath.COposed by Gholam Reza Omidi, Ghaffar Raeisirecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

For positive integers n1≥n2≥⋯≥nt≥2n_1 \ge n_2 \ge \dots \ge n_t \ge 2, we have R(P2n1,P2n2,…,P2nt)=n1+∑i=1t(ni−1)+1.R(P_{2n_1}, P_{2n_2}, \dots, P_{2n_t}) = n_1 + \sum_{i=1}^{t} (n_i - 1) + 1.

Context

Candidate 1 of the open problems stated in "On multicolor Ramsey number of paths versus cycles", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

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: Reconstruct PmP_m as the path on mm vertices, and R(G1,…,Gt)R(G_1,\dots,G_t) as the least NN such that every tt-edge-coloring of KNK_N contains a color-ii copy of GiG_i for some ii. The conjecture asserts that for all n1≥⋯≥nt≥2n_1\ge \cdots \ge n_t\ge 2,

    R(P2n1,…,P2nt)=n1+∑i=1t(ni−1)+1.R(P_{2n_1},\dots,P_{2n_t}) = n_1+\sum_{i=1}^t(n_i-1)+1 .

    Result: The conjecture is false.

    Take t=6t=6 and n1=⋯=n6=3n_1=\cdots=n_6=3. The conjecture predicts

    R(P6,P6,P6,P6,P6,P6)=3+6(3−1)+1=16.R(P_6,P_6,P_6,P_6,P_6,P_6)=3+6(3-1)+1=16.

    We give a 66-coloring of K25K_{25} with no monochromatic P6P_6. Let the vertex set be F52\mathbb F_5^2. The six colors are the six one-dimensional subspaces of F52\mathbb F_5^2, i.e. the six affine directions. For distinct vertices x,y∈F52x,y\in \mathbb F_5^2, color the edge xyxy by the unique one-dimensional subspace containing x−yx-y.

    For a fixed direction DD, the color-DD edges lie exactly inside the five affine lines parallel to DD. Thus the color-DD graph is a disjoint union of five copies of K5K_5. Hence every monochromatic component has only 55 vertices, so no color contains a P6P_6.

    Therefore

    R(P6,P6,P6,P6,P6,P6)≥26,R(P_6,P_6,P_6,P_6,P_6,P_6)\ge 26,

    contradicting the conjectured value 1616.

    This is not an endpoint artifact: here all ni=3>2n_i=3>2.

    Citation: No external citation used; the counterexample is the elementary affine-plane coloring over F5\mathbb F_5.

    Reviews

    0 human 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 rigorous. For t=6t=6 and all ni=3n_i=3, the conjecture predicts 1616. The affine-plane coloring of K25K_{25} over F52\mathbb F_5^2 uses exactly six directions as colors, and each monochromatic graph is a disjoint union of five K5K_5's, hence has no component with 6 vertices and no monochromatic P6P_6. Therefore R(P6,…,P6)≥26R(P_6,\ldots,P_6)\ge 26, directly contradicting the stated conjecture.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is valid but very elementary. It is just the affine-plane direction coloring of K25K_{25}, and it is an immediate special case of standard finite-geometry constructions. Moreover, Erdős–Gallai gives the matching upper bound R6(P6)≤26R_6(P_6)\le 26, so the stronger exact value R6(P6)=26R_6(P_6)=26 follows in a few lines. This is not substantial enough for a standalone combinatorics paper, except perhaps as a very short erratum/note.

      Literature check: I found the relevant path-Ramsey literature: Faudree–Schelp’s classic paper on multicolor path Ramsey numbers, Gyárfás–Ruszinkó–Sárközy–Szemerédi on three colors, Dzido’s papers on paths/cycles, and Sárközy’s 2016 multicolor path/even-cycle bounds. I did not find an accessible source explicitly stating this exact affine-plane counterexample as a refutation of Omidi–Raeisi’s conjecture. However, the ingredients are standard and the exact special case follows immediately from them, so the novelty is minimal.

      Citation: P. Erdős and T. Gallai, “On maximal paths and circuits of graphs,” Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356.
      R. J. Faudree and R. H. Schelp, “Path Ramsey numbers in multicolorings,” J. Combin. Theory Ser. B 19 (1975), 150–160.
      G. N. Sárközy, “On the Multi-Colored Ramsey Numbers of Paths and Even Cycles,” Electron. J. Combin. 23 (2016), #P3.53.

      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.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

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