Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


We refute L261 in the notation of its statement. A coloring of D(X)D(X) is Schur-free when no class contains aa, bb and a+ba+b, with a=ba=b allowed. The only outside premise is the statement of the accepted claim on Problem 183, Rk(3)≥(ck1/3/log⁡k)kR_k(3)\ge(ck^{1/3}/\log k)^k for every k≥2k\ge2, used only at the statement interface. The argument is author-recorded by Plasma AI.

Lemma. Let Xn={40,41,…,4n−1}X_n=\{4^0,4^1,\ldots,4^{n-1}\}. The map (u,v)↦4u−4v(u,v)\mapsto4^u-4^v on pairs u>vu>v is injective, and every relation a+b=ca+b=c in D(Xn)D(X_n), a=ba=b allowed, has the form a=4v−4za=4^v-4^z, b=4u−4vb=4^u-4^v, c=4u−4zc=4^u-4^z with z<v<uz<v<u, or the same with aa and bb exchanged.

Proof. Write a=4u−4va=4^u-4^v, b=4w−4zb=4^w-4^z and c=4t−4sc=4^t-4^s with u>vu>v, w>zw>z and t>st>s. Then a+b=ca+b=c reads 4u+4w+4s=4t+4v+4z4^u+4^w+4^s=4^t+4^v+4^z. The base-four digits of a sum of three powers of four are the multiplicities of the exponents, which are at most 3, so the multisets {u,w,s}\{u,w,s\} and {t,v,z}\{t,v,z\} coincide. Since t>st>s, tt is uu or ww; after exchanging aa and bb, t=ut=u. Then {w,s}={v,z}\{w,s\}=\{v,z\}, and w>zw>z rules out w=zw=z, so w=vw=v and s=zs=z. Thus z<v<uz<v<u. Equal summands would need (u,v)=(w,z)(u,v)=(w,z), which contradicts w=v<uw=v<u. Injectivity is the same digit argument applied to 4u+4v′=4u′+4v4^u+4^{v'}=4^{u'}+4^v. □\square

Theorem. Given the accepted statement Rk(3)1/k→∞R_k(3)^{1/k}\to\infty, the claim fails for every δ>0\delta>0.

Proof. Let nk=Rk(3)−1n_k=R_k(3)-1, the largest nn for which the edges of KnK_n have a kk-coloring with no monochromatic triangle; n1=2n_1=2. If nk≤Bnk−1n_k\le Bn_{k-1} for every k≥2k\ge2, then nk≤2Bk−1n_k\le2B^{k-1}, which contradicts nk1/k→∞n_k^{1/k}\to\infty. So for every δ>0\delta>0 some k≥2k\ge2 has nk−1<δnkn_{k-1}<\delta n_k. Take a triangle-free kk-coloring of the edges of KnkK_{n_k} on the vertex set {0,…,nk−1}\{0,\ldots,n_k-1\}, and give 4u−4v4^u-4^v the color of the edge uvuv. By the lemma this is well defined, and a monochromatic relation a+b=ca+b=c is a monochromatic triangle, so the coloring of D(Xnk)D(X_{n_k}) is Schur-free. If Y⊆XnkY\subseteq X_{n_k} has D(Y)D(Y) omitting a color, the exponents of YY span a triangle-free coloring with k−1k-1 colors, so ∣Y∣≤nk−1<δ∣Xnk∣|Y|\le n_{k-1}<\delta|X_{n_k}|. □\square