ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let KrK_r be the complete graph on rr vertices, let sat⁡(n,R(Kr))\operatorname{sat}(n,\mathcal{R}(K_r)) denote the minimum number of edges in an nn-vertex edge-colored graph containing no rainbow copy of KrK_r such that adding any non-edge in any color creates a rainbow copy of KrK_r, and fix r≥3r\geq 3. Girã o–Lewis–Popielarz conjecture. There exists a constant CrC_r depending only on rr such that, for every n≥2(r−2)n\geq 2(r-2),

sat⁡(n,R(Kr))=2(r−2)n+Cr.\operatorname{sat}(n,\mathcal{R}(K_r))=2(r-2)n+C_r.

The conjecture predicts an exact linear formula for rainbow saturation with infinitely many available colors. It is refuted: for every r≥3r\geq 3, the paper establishes constants αr\alpha_r satisfying r+Ω(r1/3)≤αr≤r+r1/2r+\Omega(r^{1/3})\leq\alpha_r\leq r+r^{1/2} and sat⁡(n,R(Kr))=αrn+O(1)\operatorname{sat}(n,\mathcal{R}(K_r))=\alpha_r n+O(1), contradicting the proposed slope 2(r−2)2(r-2).

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

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.