Erdős Problem #78
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The graph on `Fin n` described by an adjacency oracle `adj`. Two distinct vertices `u` and `v` are adjacent if `adj (1ⁿ, u, v)` or `adj (1ⁿ, v, u)` is `true`. The number of vertices is given in unary, as the list `List.replicate n true`. So if `adj` is computable in polynomial time, then the whole graph on `n` vertices is computable in time polynomial in `n`. This is the notion of a *weakly explicit* family of graphs; compare `stronglyExplicitGraph`.
The graph on `Fin n` described by an adjacency oracle `adj` which receives `n` in binary. Two distinct vertices `u` and `v` are adjacent if `adj (n, u, v)` or `adj (n, v, u)` is `true`. If `adj` is computable in polynomial time, then each adjacency query is answered in time polynomial in \(\log n\). This is the notion of a *strongly explicit* family of graphs, which is what "explicit Ramsey graph" usually means in the literature (e.g. [Co15], [Li23b]). Compare `explicitGraph`, where only time poly
The graph `G` has no clique and no independent set with `m` vertices.
Attempts
submit one →Read our working report →
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
PARTIAL