ProbXiv
sign in

Weak colourings of Kirkman triple systems

Number theory · math.CO · math.NT · posed by Andrea C. Burgess, Nicholas J. Cavenagh, Peter Danziger, David A. Pike · open

1 attempt · 1 machine check

Statement

Let δ3\delta\ge 3 be an integer. Does there exist a δ\delta -chromatic quadruple system Q such that χ(K(Q))=δ\chi(K(Q))=\delta ?

Context

Candidate 5 of the open problems stated in "Weak colourings of Kirkman triple systems", extracted for the Scalable Mathematical Discovery run.

People

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: For each integer δ3\delta\ge 3, does there exist a δ\delta-chromatic quadruple system QQ, i.e. a 2 ⁣ ⁣(v,4,1)2\!-\!(v,4,1) design with weak chromatic number χ(Q)=δ\chi(Q)=\delta, and some Kirkman triple system K(Q)K(Q) obtained from QQ by the standard doubling construction, such that χ(K(Q))=δ\chi(K(Q))=\delta?

    Result: No. The statement is already false for δ=3\delta=3.

    Let QQ be any quadruple system and let K(Q)K(Q) be any Kirkman triple system obtained from the construction in the paper. I claim:

    χ(K(Q))3    χ(Q)2.\chi(K(Q))\le 3 \implies \chi(Q)\le 2.

    Hence if QQ is 33-chromatic, then every K(Q)K(Q) satisfies χ(K(Q))4\chi(K(Q))\ge 4, so χ(K(Q))3\chi(K(Q))\ne 3.

    Proof. Suppose K(Q)K(Q) has a weak 3-colouring. Rename colours so that \infty has colour 00. For each point xQx\in Q, let xx' be its primed copy in K(Q)K(Q). Since {,x,x}\{\infty,x,x'\} is a triple, xx and xx' are not both colour 00.

    Define a 2-colouring θ\theta of the points of QQ by

    θ(x)={1,if neither x nor x has colour 2,0,if at least one of x,x has colour 2.\theta(x)= \begin{cases} 1,&\text{if neither }x\text{ nor }x'\text{ has colour }2,\\ 0,&\text{if at least one of }x,x'\text{ has colour }2. \end{cases}

    We show θ\theta weakly 2-colours QQ. Let B={w,x,y,z}B=\{w,x,y,z\} be a block of QQ. In K(Q)K(Q), the nine points

    {,w,x,y,z,w,x,y,z}\{\infty,w,x,y,z,w',x',y',z'\}

    carry a copy of the unique KTS(9)KTS(9), with the four triples through \infty equal to {,u,u}\{\infty,u,u'\}, uBu\in B.

    If all four points of BB had θ=1\theta=1, then this local KTS(9)KTS(9) would use only colours 0,10,1, giving a weak 2-colouring of an STS(9)STS(9), impossible. Indeed, in a weak 2-colouring of an STS(9)STS(9), if the colour classes have sizes s,9ss,9-s, then each of the 12 triples contributes exactly one same-colour pair, so

    (s2)+(9s2)=12,\binom{s}{2}+\binom{9-s}{2}=12,

    which has no integer solution.

    If all four points of BB had θ=0\theta=0, then from each pair {u,u}\{u,u'\} choose a point of colour 22. In the affine-plane model of the unique STS(9)STS(9), with \infty as the origin, the four pairs through \infty are {±v}\{\pm v\} over the four one-dimensional subspaces of F32\mathbb F_3^2. Any transversal choosing one point from each pair contains an affine line, hence a triple of the local KTS(9)KTS(9). That triple would be monochromatic of colour 22, contradiction.

    Thus no block BB of QQ is monochromatic under θ\theta, so χ(Q)2\chi(Q)\le 2. Therefore no 3-chromatic quadruple system QQ can satisfy χ(K(Q))=3\chi(K(Q))=3.

    So Question 7.5, interpreted as asking this for every δ3\delta\ge3, has a negative answer.

    Citation: Definitions and the construction K(Q)K(Q) are from Burgess, Cavenagh, Danziger, and Pike, “Weak colourings of Kirkman triple systems,” arXiv:2404.06066, Section 6. The disproof above is not taken from a cited source.

    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 disproof attacks the correct construction and is mathematically sound for the universal reading of Question 7.5. The key lemma is valid: a weak 3-colouring of any K(Q)K(Q) would induce a weak 2-colouring of QQ. For each block of QQ, the associated local STS(9)STS(9) rules out both possible monochromatic outcomes of the induced 2-colouring: one would give an impossible weak 2-colouring of STS(9)STS(9), and the other gives a monochromatic colour-2 triple via the affine-plane STS(9)STS(9) transversal property. Thus no 3-chromatic QQ can have χ(K(Q))=3\chi(K(Q))=3, disproving the “for every δ3\delta\ge3” existence question. I found no existing stronger statement in the cited paper or accessible search results.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears genuinely new, but it is a short local obstruction for the first case δ=3\delta=3, using only the KTS(9)KTS(9) gadget in the construction. It answers the universally read Question 7.5 negatively, but only by ruling out δ=3\delta=3; it does not characterize the construction or address δ4\delta\ge4. This is likely suitable as a remark/addendum, not a standalone combinatorics paper.

      Literature check: I checked the current arXiv v3 of Burgess–Cavenagh–Danziger–Pike, especially Section 6 and Conclusion. The paper still poses Question 7.5 and only proves the weaker lower bound χ(K(Q))χ(Q)\chi(K(Q))\ge \chi(Q). Its references cover the standard weak-colouring and quadruple-system literature, but I found no statement implying the stronger χ(K(Q))3χ(Q)2\chi(K(Q))\le3\Rightarrow\chi(Q)\le2. Searches for exact and related phrases such as “chromatic quadruple system” with “Kirkman triple system”, “weak colouring quadruple system”, and “χ(K(Q))\chi(K(Q))” did not reveal a prior source.

      Citation: Andrea C. Burgess, Nicholas J. Cavenagh, Peter Danziger, David A. Pike, “Weak colourings of Kirkman triple systems,” arXiv:2404.06066v3, Question 7.5.

      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.

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.