Erdoes #78 - working report - Erdős Problem a Day

Erdős problem #78 — wave 5h

Access date: 2026-07-26 (UTC).

Result in one paragraph

(a, elementary-rigorous) The mandatory live-page collision check passed: the page says OPEN - $100, 0 claimed proofs, Currently working ... None, and Interested in collaborating ... None. (a, elementary-rigorous) The discussion does contain a conditional-expectation construction for a weaker whole-graph-output formulation, but Thomas Bloom explicitly says that the intended meaning of “explicit” is a uniform edge predicate running in time polynomial in the vertex-label length. (a, elementary-rigorous) I give a from-scratch reduction showing that the exact missing object is a strongly explicit one-bit two-source zero-error disperser on two $m$-bit inputs at entropy $\log_2 m+O(1)$; Li's current construction has entropy $c\log m$, $c>1$, and therefore gives homogeneous-set threshold $(\log N)^c$, not $O(\log N)$. (d, computational-only) I also computed exact clique and independence numbers for the next six prime-order Paley graphs after the classical published $p\leq1601$ range; in particular,

\[ \omega(P_{1669})=\alpha(P_{1669})=13, \]

so $P_{1669}$ is a concrete certificate for $R(14)>1669$. (b, rigorous modulo named theorems) This does not extend asymptotically: square-order Paley graphs have subfield cliques of order $\sqrt q$, and the Graham–Ringrose theorem gives infinitely many prime Paley graphs with clique number $\Omega(\log p\log\log\log p)$, ruling out the full Paley family as an $O(\log p)$-Ramsey family. No solution of #78 is claimed.

Claim labels

Every substantive mathematical assertion below is marked as requested:

(a) elementary-rigorous (including exact source transcription or a complete proof given here);
(b) rigorous modulo the named theorem or primary source;
(c) plausible/structural-unverified;
(d) computational-only (finite exhaustive computation, never extrapolated).

0. Mandatory live-page check

Fetch and official status

(a, direct observation) I fetched the rendered problem page through the Bright Data browser path, not datacenter curl:

<https://www.erdosproblems.com/78>
<https://www.erdosproblems.com/forum/thread/78>

(a, direct observation) The rendered page reported:

OPEN - $100
5 comments on this problem
0 claimed proofs for this problem
Interested in collaborating    None
Currently working on this problem    None

(a, direct observation) It also said that the problem page was last edited on 23 January 2026. The problem has one “like” marker (Fedir), but no collaboration or current-worker marker.

Verbatim current statement

The following is copied verbatim from the page's “View the LaTeX source” rendering:

> Let $R(k)$ be the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$.

> Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.

Known results stated on the page

(a, direct transcription) The page states that Erdős's probabilistic argument gives

\[ R(k)\gg k2^{k/2}. \]

(a, direct transcription) It states the equivalent target as an explicit $n$-vertex graph with no clique or independent set of size at least $c\log n$, for an absolute $c>0$.

(a, direct transcription) It says that [Er69b] asked even for a construction with largest clique or independent set $o(n^{1/2})$, which is now known.

(b, Cohen's theorem) It credits Cohen [Co15] with a construction having no clique or independent set of size

\[ \geq 2^{(\log\log n)^C} \]

for some constant $C>0$.

(b, Li's theorem) It credits Li [Li23b] with improving this to

\[ \geq(\log n)^C \]

for some constant $C>0$.

(a, direct transcription) The page lists the original-source keys [Er69b], [Er71], [Er88], [Er93, p.337], [Er95], [Er97c], and [Va99, §3.49]. Its rendered bibliography identifies them as:

P. Erdős, “Problems and results in chromatic graph theory,” Proof Techniques in Graph Theory (1969), 27–35.
P. Erdős, “Some unsolved problems in graph theory and combinatorial analysis,” Combinatorial Mathematics and its Applications (1971), 97–109.
P. Erdős, “Problems and results in combinatorial analysis and graph theory,” Discrete Math. (1988), 81–92.
P. Erdős, “Some of my favorite solved and unsolved problems in graph theory,” Quaestiones Math. (1993), 333–350.
P. Erdős, “Some of my favourite problems in number theory, combinatorics, and geometry,” Resenhas (1995), 165–186.
P. Erdős, “Some of my favorite problems and results,” The Mathematics of Paul Erdős I (1997), 47–67.
“Some of Paul's favorite problems,” conference booklet, Budapest (1999).

All five comments and why they do not trigger `SKIP`

(a, direct observation) The comments, in chronological order, are:

1. Neel Somani asks whether conditional expectation, giving a deterministic full colouring in roughly the probabilistic range, counts as “constructive.”

2. StijnC answers: “Explicit.” He says this derandomization still only gives an existence proof for the intended purpose and is not efficient for large $n$; algebraic constructions would be welcome but are not the only allowed kind.

3. Terence Tao proposes a concrete weaker formulation: given $k$, output an exponential-size Ramsey graph in time less than double exponential in $k$.

4. aditya gives the standard conditional-expectation algorithm with $N=\lfloor2^{k/3}\rfloor$ and running time $2^{O(k^2)}$, calling it a solution to Tao's formulation.

5. Thomas Bloom confirms that this is the standard conditional-expectation argument and says that “explicit” here means a uniform algorithm which, given two vertices, decides adjacency in time polynomial in $\log n$.

(a, collision decision) Although comment 4 says that an LLM “seems to have found a solution to this formulation,” “this formulation” is Tao's weaker whole-output formulation, not the live problem under Bloom's explicitness criterion. The official proof-claim counter is zero, Bloom's reply rejects it as a solution of the intended target, and there is no current worker. Therefore the mandatory stop condition does not apply.

1. What “constructive” means here

(a, live-comment criterion) In this report, a family $G_N$ is strongly explicit if one uniform algorithm, on input $N$ and two $O(\log N)$-bit vertex labels, decides their adjacency in $(\log N)^{O(1)}$ time.

(b, Cohen's definition) This agrees with Cohen's formal definition in the introduction of arXiv:1506.04428: the edge between two labels in an $N$-vertex graph must be decidable in $\operatorname{polylog}N$ time.

(a, parameter equivalence) A strongly explicit family with

\[ \max\{\omega(G_N),\alpha(G_N)\}\leq D\log_2 N \]

for an absolute $D$ solves the stated problem. Indeed, for large $k$, choose

\[ N=\left\lfloor 2^{k/(2D)}\right\rfloor. \]

Then $D\log_2NN$, and after reducing the base slightly to absorb the floor and finitely many small $k$, $N>C^k$ for some $C>1$.

Audit of the conditional-expectation comment

Let $r=\binom{k}{2}$ and colour the edges of $K_N$ independently and uniformly.

(a, elementary-rigorous) The expected number of monochromatic $K_k$'s is

\[ \Phi(\varnothing)=\binom Nk\,2^{1-r}. \]

For $N=\lfloor2^{k/3}\rfloor$,

\[ \Phi(\varnothing) \leq \frac{N^k}{k!}\,2^{1-r} \leq \frac{2^{\,1-k^2/6+k/2}}{k!}<1 \qquad(k\geq10). \]

At $k=10$ the last power of $2$ already has exponent $-32/3$; both it and $1/k!$ decrease thereafter. Also $N\geq k$ from $k=10$ onward.

(a, elementary-rigorous) If an uncoloured edge $e$ is next, then

\[ \Phi(P)=\tfrac12\Phi(P\cup\{e=\mathrm{red}\}) +\tfrac12\Phi(P\cup\{e=\mathrm{blue}\}). \]

Choosing the smaller child potential never increases $\Phi$. When all edges are coloured, $\Phi$ is an integer counting monochromatic $K_k$'s, hence is zero. Thus the comment's weaker deterministic construction is correct.

(a, elementary-rigorous) Recomputing the potential by enumerating all $k$-sets takes $2^{O(k^2)}$ time. It does not give a succinct uniform edge predicate: retaining the completed adjacency table is nonuniform advice of $\Theta(N^2)$ bits, while recomputing an edge through the global process is vastly more than $\operatorname{poly}(k)$.

(a, exact arithmetic) At $k=50$, the comment's choice is $N=104031$ and

\[ \log_2\binom{104031}{50}=619.107570\ldots. \]

Even granting $10^6$ complete $50$-set inspections per second per core, one naive potential evaluation costs about $10^{176.814}$ core-hours. The edge-by-edge algorithm needs many such evaluations. This is a cost estimate for the naive algorithm in the comment, not a lower bound against every possible implementation.

2. Primary-literature check

Sources verified

(a, direct primary-source check) I verified that each identifier below exists and inspected the cited theorem, corollary, or introduction rather than relying on search-result summaries.

| Primary source | Verified statement | Relevance |

|---|---|---|

| Gil Cohen, arXiv:1506.04428, Theorem 1.2 | A strongly explicit bipartite $2^{(\log\log N)^{O(1)}}$-Ramsey graph | Confirms the page's Cohen summary and the local-edge definition |

| Xin Li, arXiv:2303.06802v2, Corollaries 1.9 and 7.7 | For some $c>1$, strongly explicit $N$-vertex graphs with no clique or independent set of size $(\log N)^c$ | Current cited bound; exponent $c>1$ is the remaining gap |

| Xin Li and Yan Zhong, ECCC TR25-049 rev. 1, Appendix F, Theorem F.1 | Construction of a $(\log m+2\log(1/\epsilon)+3,\epsilon)$ two-source extractor reduces in polynomial time to $NC^0_4$-Avoid | Gives a precise complexity-theoretic route to the missing target |

| Brandon Hanson and Giorgis Petridis, arXiv:1905.09134, Corollary 1.5 | For prime $p\equiv1\pmod4$, the Paley clique number is at most $(\sqrt{2p-1}+1)/2$ | Best uniform prime-Paley upper bound used below |

| Dmitriy Kunisky, arXiv:2303.16475, Theorem 1.2 and §1 | Records Hanson–Petridis as state of the art and explains that even $o(\sqrt p)$ would require new high-order spectral control | Independent current check of the Paley barrier |

| Mark Magsino, Dustin G. Mixon, and Hans Parshall, arXiv:1907.05971, introduction | For standard difference Paley graphs $G_p$, $p\equiv1\pmod4$, cites the Graham–Ringrose theorem giving $\Omega(\log p\log\log\log p)$ cliques for infinitely many primes | Rules out an all-prime $O(\log p)$ Paley family |

| I. Broere, D. Döman, J. N. Ridley, DOI 10.1080/16073606.1988.9631945 | Its abstract says prime Paley clique numbers were known for $5\leq p\leq1601$, and proves the square-order value | Gives the published finite cutoff immediately before my table |

Search misses and false positives

(a, honest search record) Searches of arXiv and ECCC for “explicit Ramsey graph,” “$O(\log N)$-Ramsey,” “optimal Ramsey graph,” and two-source extractors through the access date found no primary source claiming the target. The newest primary source I found that explicitly identifies the state of the art, Li–Zhong (2025), still names Li's $(\log N)^{O(1)}$ construction and treats $O(\log N)$ as missing.

(a, checked false positive) Matija Kocbek's 2025 preprint arXiv:2507.09235, despite the title “Explicit geometric construction of Ramsey graphs,” concerns off-diagonal $R(3,t)$-type constructions, including triangle-free graphs with independence number $O(n^{2/3})$. It does not establish the diagonal $O(\log n)$ target here.

(c, literature-completeness caveat) Failure to find a paper is not a theorem that none exists; the live page itself carries the same caveat. The direct page status, current-worker markers, and checked primary sources are the evidence used here.

3. Clean reduction: the exact missing lemma

Let $M=2^m$. A Boolean matrix

\[ B_m:\{0,1\}^m\times\{0,1\}^m\longrightarrow\{0,1\} \]

is a bipartite $K$-Ramsey matrix if it has no monochromatic $K\times K$ submatrix.

Bipartite to ordinary, with the constant exposed

(a, elementary-rigorous lemma) Given a bipartite $K$-Ramsey matrix $B$ whose rows and columns are both ordered as $[M]$, define an ordinary graph $G_B$ on $[M]$ by

\[ \{i,j\}\in E(G_B)\quad\Longleftrightarrow\quad B(i,j)=1 \qquad(iThen $G_B$ has no clique or independent set of size $2K$.

Proof. Suppose \(S=\{s_1<\cdots \[ A=\{s_1,\ldots,s_K\},\qquad C=\{s_{K+1},\ldots,s_{2K}\}. \]

Every $a\in A$ is smaller than every $c\in C$, so all cross-edge colours in $G_B$ are the entries $B(a,c)$. Homogeneity of $S$ makes $B[A,C]$ a monochromatic $K\times K$ submatrix, a contradiction. $\square$

(a, explicitness preservation) One evaluation of the ordinary edge predicate uses one evaluation of $B$, one comparison, and no preprocessing. Thus strong explicitness is preserved.

Disperser parameter ledger

A one-bit two-source zero-error disperser for entropy $t$ is a Boolean function $B_m$ which is nonconstant on $A\times C$ whenever $|A|,|C|\geq2^t$.

(a, elementary-rigorous) This is exactly the absence of a monochromatic $2^t\times2^t$ rectangle. The preceding lemma therefore gives:

| quantity | value |

|---|---:|

| input length | $m$ bits |

| graph vertices | $M=2^m$ |

| source entropy | $t$ |

| forbidden bipartite rectangle side | $K=2^t$ |

| forbidden ordinary homogeneous-set size | $2K=2^{t+1}$ |

(a, exact reduction) Erdős #78 follows from a strongly explicit family with

\[ t\leq\log_2m+O(1), \]

because then $2^{t+1}=O(m)=O(\log M)$.

(b, Li's parameter) Li proves a constant-error two-source extractor for $t=c\log m$, for some $c>1$. Error $<1/2$ rules out a constant $K\times K$ rectangle, but

\[ K=2^t=m^c=(\log_2 M)^c. \]

This reproduces Li's $(\log M)^c$ threshold and isolates the exact exponent-one gap.

(a, precise missing lemma) It would suffice to construct a uniform, $\operatorname{poly}(m)$-time-evaluable, one-bit zero-error two-source disperser for entropy $\log_2m+O(1)$. A full extractor is stronger than necessary.

(b, named complexity route) Li–Zhong Theorem F.1 shows that a still-stronger extractor with entropy

\[ \log m+2\log(1/\epsilon)+3 \]

reduces in polynomial time to their $NC^0_4$-Avoid problem. For constant $\epsilon<1/2$, solving that avoidance task with the required uniformity would reach the Ramsey target.

4. The Paley attack and its exact failure modes

For a prime $p\equiv1\pmod4$, let $P_p$ have vertex set $\mathbb F_p$, with $x\sim y$ iff $x-y$ is a nonzero quadratic residue.

Why it is the natural algebraic candidate

(a, elementary-rigorous) Adjacency is computable by modular exponentiation:

\[ (x-y)^{(p-1)/2}\pmod p. \]

Its bit complexity is polynomial in $\log p$, so $P_p$ is strongly explicit.

(a, elementary-rigorous) If $\nu$ is a quadratic nonresidue, multiplication by $\nu$ maps residues to nonresidues. Hence $x\mapsto\nu x$ is an isomorphism $P_p\cong\overline{P_p}$, and

\[ \omega(P_p)=\alpha(P_p). \]

Square prime powers are structurally impossible

(a, elementary-rigorous) Let $q=r^2$ be an odd square prime power. For every $a\in\mathbb F_r^\times$,

\[ a^{(q-1)/2} =a^{(r-1)(r+1)/2} =1. \]

Thus every nonzero subfield element is a square in $\mathbb F_q$, and the additive subfield $\mathbb F_r$ is a clique of size $r=\sqrt q$ in $P_q$. Therefore square-order Paley graphs cannot have $O(\log q)$ homogeneous sets.

(b, Broere–Döman–Ridley/Hoffman) In fact the clique number for square order is exactly $\sqrt q$, but the elementary lower bound already rules out this branch.

The full prime family is also impossible

(b, Graham–Ringrose theorem) There are infinitely many primes $p$ for which

\[ \omega(P_p)=\Omega(\log p\,\log\log\log p). \]

Consequently there is no absolute $D$ with $\omega(P_p)\leq D\log p$ for every admissible prime $p$.

(a, logical consequence) A Paley solution could only use a provably good selected sequence of primes (or a modified construction), not the complete prime family. To cover all relevant sizes by induced subgraphs, the selected good primes would also need controlled multiplicative gaps and an efficient uniform selection rule. No such theorem was found.

Where elementary character sums stall

Let $\chi$ be the quadratic character and $S\subset\mathbb F_p$, $|S|=t$. Let $N(S)$ count common Paley neighbours of all vertices in $S$.

(a, exact identity) Excluding the points of $S$,

\[ 2^tN(S) =\sum_{x\notin S}\prod_{s\in S}\bigl(1+\chi(x-s)\bigr). \]

(b, rigorous modulo Weil's character-sum bound) Expand the product. For each $T\subseteq S$, $|T|\geq2$, the polynomial $\prod_{s\in T}(x-s)$ is squarefree, so Weil gives an error at most $(|T|-1)\sqrt p$. Triangle inequality and

\[ \sum_{j=2}^{t}\binom tj(j-1)=(t-2)2^{t-1}+1 \]

give

\[ N(S)=\frac{p}{2^t} +O\!\left(\left(\frac{t-2}{2}+2^{-t}\right)\sqrt p+t\right). \]

(a, exact diagnosis) At the desired scale $t\asymp\log_2p$, the main term is $O(1)$, while this error is $O(\sqrt p\log p)$. Thus separate Weil bounds plus triangle inequality cannot even decide whether the common neighbourhood is empty. (c, method-specific) Continuing this route would require high-order cancellation correlated across the $2^t$ character sums (and, because of Graham–Ringrose exceptions, it could only hold on a suitably selected family).

(b, current best uniform bound) Hanson–Petridis prove

\[ \omega(P_p)\leq\frac{\sqrt{2p-1}+1}{2}, \]

still polynomially larger than $\log p$.

5. Exact finite computation

Scope

(a, elementary-rigorous) The primes

\[ 1609,1613,1621,1637,1657,1669 \]

are the next six primes congruent to $1\bmod4$ after $1601$.

(d, computational-only) The standalone checker computed:

|---:|---:|---:|---:|---:|---|

| 1609 | 13 | 28 | 40 | 510,128 | 8d14c3448d958e8c |

| 1613 | 14 | 28 | 40 | 284,401 | e762595d4559fe3a |

| 1621 | 13 | 28 | 40 | 906,969 | 521f9ead5e307df1 |

| 1637 | 13 | 29 | 40 | 816,875 | 30361a9c4be53a99 |

| 1657 | 13 | 29 | 40 | 655,907 | bc127268dde18203 |

| 1669 | 13 | 29 | 40 | 722,694 | 08391c7c4e77d276 |

Lower-bound certificates

(d, computational-only) The following are explicit maximum-clique witnesses; every pairwise difference in each row is a nonzero square modulo $p$:

p=1609:
0 1 3 13 16 219 536 1007 1031 1250 1300 1550 1560

p=1613:
0 1 77 132 266 401 456 597 614 637 830 1038 1093 1417

p=1621:
0 1 5 106 122 415 536 776 1155 1214 1289 1437 1610

p=1637:
0 1 15 67 225 403 441 780 924 1225 1291 1552 1601

p=1657:
0 1 4 59 68 71 441 804 862 932 1040 1232 1334

p=1669:
0 1 82 358 439 631 676 803 949 1031 1225 1307 1364

Why the upper certificates are exhaustive

(a, elementary-rigorous) Every clique of size at least two can be mapped to one containing $\{0,1\}$. Given an edge $a,b$, its difference $d=b-a$ is a square; the affine map

\[ x\longmapsto (x-a)d^{-1} \]

preserves square differences and maps $a,b$ to $0,1$. Therefore it is enough to search the common neighbourhood of $0$ and $1$.

(a, elementary-rigorous) The exact solver recursively extends a partial clique. At each node it greedily partitions the remaining candidates into independent colour classes. If $c$ classes are used, no clique extension has more than $c$ vertices; a branch whose current size plus $c$ is at most the best known size is safely pruned. Exhausting the remaining branches proves the upper bound.

(a, elementary-rigorous) Multiplication by the least quadratic nonresidue was checked on every pair and maps each computed graph to its complement, so the exact clique number also equals the exact independence number.

(d, computational cross-checks) The checker independently:

compared the colouring-bound solver with raw subset enumeration on all $32,768$ labelled graphs on six vertices;
compared the fixed-edge Paley reduction with raw subset enumeration for $p=5,13,17$;
checked every listed witness pair by pair;
audited all $65,536$ Boolean $4\times4$ matrices for the bipartite-to-ordinary reduction;
audited the lexicographic-product identities below on every ordered pair of three-vertex graphs;
checked the Paley character identity directly for every subset of size at most four in $p=5,13,17,29$.

(d, finite Ramsey consequence) Since $P_{1669}$ has neither a clique nor an independent set of size $14$,

\[ R(14)>1669. \]

This is a concrete certificate, not a claim of a record diagonal Ramsey bound.

(c, novelty caveat) The 1988 Broere–Döman–Ridley abstract identifies $p\leq1601$ as the then-computed prime range, so these six values extend that particular published cutoff. Later informal/computational tables may exist; I make no claim that the values are new to every database.

6. Why finite witnesses do not supply the missing uniformity

One natural attempt is to amplify a finite graph by lexicographic products.

(a, elementary-rigorous) For graphs $G,H$,

\[ \omega(G[H])=\omega(G)\omega(H), \qquad \alpha(G[H])=\alpha(G)\alpha(H). \]

For the upper bound, project a clique (or independent set) to its occupied $G$-fibres and bound its intersection with each fibre by the corresponding parameter of $H$; products of extremal sets attain equality.

(a, elementary-rigorous) Consequently the $t$-fold lexicographic power of $P_{1669}$ has

\[ |V|=1669^t,\qquad \omega=\alpha=13^t =|V|^{\log_{1669}13}. \]

This is a fixed positive power of the number of vertices, not $O(\log |V|)$. Thus the exact finite table cannot be bootstrapped by standard graph substitution into a solution.

(a, uniformity warning) No finite list, however long, proves the required asymptotic family. The closing step must be a uniform theorem—such as the entropy-$\log m+O(1)$ disperser above—not an extrapolation from computed clique numbers.

7. Exact wall and what would move it

The problem remains open in this run. The three most precise next targets are:

1. (a, sufficient lemma) Construct a strongly explicit one-bit two-source zero-error disperser on $m$-bit inputs for entropy $\log_2m+O(1)$. This directly closes #78 via §3.

2. (b, stronger named route) Give the uniform avoidance algorithm needed by Li–Zhong Theorem F.1 for the corresponding $NC^0_4$-Avoid instances, thereby constructing a constant-error extractor at entropy $\log m+O(1)$.

3. (a, Paley-specific sufficient route) Prove and efficiently select a multiplicatively dense sequence of primes $p_i$ for which $\omega(P_{p_i})=O(\log p_i)$. Bounds for every prime are impossible by Graham–Ringrose, and current Hanson–Petridis machinery is only $O(\sqrt p)$.

(a, computational cost diagnosis) Brute-force conditional expectation is already fantastically infeasible at $k=50$, as quantified above. Exact maximum-clique searches at $p\approx1600$ are cheap enough (the full verifier used about 78 seconds on one core), but extending any finite range cannot prove the uniform assertion. Therefore no heavier finite computation on this VM has a credible path to closing #78; the missing resource is a theorem, not additional core-hours.

8. Reproduction

The complete standard-library-only checker is:

runs/erdos78_wave5h_verify.py

Run from the repository root:

python3 runs/erdos78_wave5h_verify.py

(d, reproduced execution) The final full run ended with ALL CHECKS PASSED. It used one core and approximately 78 seconds. The checker SHA-256 at report time is:

1c217d5565738f7185cee0f8645899ec9f25672bb17a369dd8e09d49e43b051e

PARTIAL: Exact post-1601 Paley values (including $\omega(P_{1669})=\alpha(P_{1669})=13$) and the entropy-$\log m+O(1)$ reduction are verified, but the required uniform strongly explicit family remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger