GPT 6 Astra Ultra attempt on Math-5467

Erdős Problem 162: a logarithmic quasi-Ramsey threshold

Statement and necessary corrections

The page asks for $F(n,\alpha)\sim c_\alpha\log n$, but defines $F$ using the largest threshold $k$ for which some colouring has more than $\alpha\binom{|X|}{2}$ edges of each colour in every $|X|\ge k$. For fixed $\alpha<1/2$ and sufficiently large $n$, a balanced global colouring satisfies the condition at $k=n$, because $\lfloor\binom n2/2\rfloor>\alpha\binom n2$. Thus the literal largest threshold in $[1,n]$ is $n$; if larger thresholds are allowed there is no largest one. At $\alpha=1/2$ the strict requirement is impossible on any set of at least two vertices.

We explicitly study the intended smallest threshold $Q(n,\alpha)$ for $0\le\alpha<1/2$, allowing $n+1$ as a vacuous value. The wording correction does not resolve the asymptotic question.

A correct clique lower bound

Splitting a vertex's neighbours by incident colour gives $R(a,b)\le R(a-1,b)+R(a,b-1)$, with $R(1,b)=R(a,1)=1$. Induction consequently gives \[ R(r,r)\le\binom{2r-2}{r-1}\le4^{r-1}. \] Every colouring on $n$ vertices therefore has a monochromatic clique of size $r=\lfloor\log_4 n\rfloor+1$. For large $n$, this is at least two and violates the strict requirement for every $\alpha\ge0$. Hence \[ Q(n,\alpha)\ge\lfloor\log_4 n\rfloor+2. \tag{1} \] The old local greedy proof allowed its majority colour to change at successive vertices and then incorrectly declared the chosen vertices monochromatic.

An explicit upper constant

Put $I_\alpha=\log2+\alpha\log\alpha+(1-\alpha)\log(1-\alpha)$, with $0\log0=0$. A fixed $s$-set in an independent fair colouring is bad with probability at most $2e^{-I_\alpha\binom s2}$. For $0<\alpha<1/2$, exponential Markov for the binomial red count, optimized at $e^{-z}=\alpha/(1-\alpha)$, proves this. For $\alpha=0$, the exact probability of a monochromatic clique is $2^{1-\binom s2}$.

For fixed $\eta>0$ take $s=\lceil(2/I_\alpha+\eta)\log n\rceil$. A union bound gives \[ \mathbb P(\text{some bad $s$-set}) \le2\binom ns e^{-I_\alpha s(s-1)/2}<1 \] for large $n$, since the coefficient of $(\log n)^2$ in its logarithm is negative. Summing the strict inequalities over all $s$-subsets of a larger set, and dividing by each edge's multiplicity, proves the condition at all larger sizes. Thus \[ \frac1{\log4}\le\liminf\frac{Q(n,\alpha)}{\log n} \le\limsup\frac{Q(n,\alpha)}{\log n}\le\frac2{I_\alpha}. \tag{2} \]

The zero-density question contains a Ramsey limit problem

For $n\ge2$ put $r(n)=\max\{r:R(r,r)\le n\}$. Every colouring has a monochromatic $r(n)$-clique, while some colouring has no $(r(n)+1)$-clique. Therefore \[ Q(n,0)=r(n)+1. \tag{3} \] A finite positive limit $Q(n,0)/\log n\to c$ is consequently equivalent to $\log R(r,r)/r\to1/c$. If the latter limit exists, bracket $n$ between consecutive Ramsey thresholds in $3$. Conversely, apply $3$ at $n=R(r,r)$ and at $R(r,r)-1$, where the values of $r(n)$ are $r$ and $r-1$. The thresholds are strictly increasing: add one vertex, with arbitrary incident colours, to a colouring on $R(r,r)-1$ vertices avoiding monochromatic $r$-cliques. A monochromatic $(r+1)$-clique in the enlarged colouring would leave an old monochromatic $r$-clique, so $R(r+1,r+1)>R(r,r)$. The two evaluations prove the inverse limit assertion.

Assessment and attribution

The random-colouring strategy of gpt_pro_5.2/162.tex is retained, with its false clique bound, endpoint treatment, and unchecked numerical claims replaced. Equations $1$--$3$ are proved here. Existence of $c_\alpha$ for the intended threshold remains unresolved in this attempt. Source: https://www.erdosproblems.com/162. No novelty claim is made.

COMPLETION ESTIMATE

COMPLETION: 35%