Polynomial-time explicit logarithmic Ramsey graphs

Polynomial-time explicit logarithmic Ramsey graphs

Definitions and mathematical statement

For a finite graph $G$, let $\omega(G)$ be the largest clique size and $\alpha(G)$ the largest independent-set size. Seek a single deterministic algorithm $A$ and constants $C,c>0$ such that, on unary input $1^N$ for every $N\ge2$, it prints a simple $N$-vertex adjacency matrix in time $O(N^c)$ with \[ \max\{\omega(G),\alpha(G)\}\le C\log_2N. \] The constants are uniform in $N$. The requested explicitness is polynomial in the output scale, not the stronger requirement of answering an adjacency query in time polynomial in $\log N$. Nonconstructive existence or a randomized algorithm without a deterministic guarantee does not meet the selected target.

Formulation and concept references: [S1].

Short English statement

Can a deterministic polynomial-time algorithm explicitly build graphs whose largest clique and independent set are both only logarithmic in the number of vertices?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, turns the probabilistic existence proof into an explicit deterministic quasipolynomial-time construction, then measures exactly why its implementation misses the requested polynomial bound. The input is unary and the entire adjacency matrix may be printed in polynomial time; no stronger local-access convention is imposed.

The source [S1] concerns Ramsey properties of specified algebraic graph classes and explains their relation to explicit construction questions. Its structural restrictions are not imposed on the graph sought here. The first gap is a polynomial-time way to choose edges while retaining the logarithmic clique and independent-set bound.

An elementary probabilistic existence bound.

Let $G$ be the random graph with each edge independently present with probability $1/2$, and put \[ t=\lceil4\log_2N\rceil. \] If $t>N$, every $N$-vertex graph already has maximum clique and independent-set size at most $N<t$, so take any graph. Assume henceforth $t\le N$.

Let $Z$ count $t$-vertex sets that induce a clique or an independent set. Each fixed set has $\binom t2$ edge choices, and its two monochromatic outcomes have total probability $2^{1-\binom t2}$. Thus \[ \mathbb EZ=2\binom Nt2^{-\binom t2} \le 2^{\,1+t\log_2N-t(t-1)/2}<1. \tag{280.1} \] For the last inequality, $t\ge4\log_2N$ gives $\log_2N-(t-1)/2\le-\log_2N+1/2$, which makes the displayed exponent negative for $N\ge2$ in the nonvacuous case.

Some graph therefore has $Z=0$. It has no clique or independent set of size $t$, and hence \[ \max(\omega,\alpha)\le t-1<4\log_2N. \] The existence proof is uniform in its numerical constant but has not yet provided a deterministic polynomial-time construction.

Conditional expectation gives an actual deterministic algorithm.

Order the $\binom N2$ possible edges. After assigning some edge bits, maintain the conditional expected value of $Z$ with the remaining bits still independent and unbiased. For each next edge, the current expectation is the average of the two expectations obtained by fixing it to zero and to one. At least one choice does not increase the expectation; choose the smaller, breaking ties deterministically.

Every term of that conditional expectation can be computed exactly. For a $t$-set, if its assigned edges include both colors, its contribution is zero. If it has some assigned edges, all of one color, and $r$ unassigned edges, its contribution is $2^{-r}$. If none are assigned, its contribution is $2^{1-\binom t2}$. Sum over all $t$-sets.

At the end every edge is fixed, and the conditional expectation is the integer $Z$ itself. It has never exceeded its initial value, which was below one, so $Z=0$. This is a full correctness proof for a deterministic construction, not a random experiment with a successful output.

All arithmetic can be exact. The denominators are powers of two with exponent at most $\binom N2$, and adding at most $N^t$ terms increases numerator length by only $O(t\log N)$. Thus ordinary integer arithmetic has polynomially many bits per expectation value. The obstacle is the number of terms evaluated, not roundoff or exponentially long individual numbers.

The resulting time bound is quasipolynomial.

There are $O(N^2)$ edge decisions, and a direct evaluation visits $\binom Nt\le N^t$ candidate sets with $O(t^2)$ inspection work each. Ignoring polynomial bit-arithmetic factors, the total is \[ N^{t+O(1)}=2^{O((\log N)^2)}. \tag{280.2} \] This is quasipolynomial, and it is not bounded by $N^c$ for one fixed $c$. The growing exponent $t=\Theta(\log N)$ must not be hidden inside an unspecified polynomial.

The algorithm uses a fixed tie rule and works for every input size, so it satisfies the uniformity requirement and the desired graph property. It falls short only in time. Improving the count to a compact conditional-expectation estimator, or finding a different efficiently computable certificate, would be meaningful progress. No such compression of the sum is proved here.

Even verifying that an arbitrary candidate has no $t$-clique and no $t$-independent set by enumerating all $t$-sets costs the same quasipolynomial scale. The observation does not prove verification needs that much time; it identifies the cost of the particular method.

Limited independence preserves the proof but not the target time.

Only $\binom t2$ edge bits are examined by each bad event. Thus a $K$-wise independent distribution on the edge bits, with $K=\binom t2=O((\log N)^2)$, gives exactly the same expectation in $280.1$.

For completeness, such a distribution can be built from a random degree-$(K-1)$ polynomial over a binary extension field $\mathbb F_{2^r}$ containing at least $\binom N2$ distinct evaluation points, where $r=O(\log N)$. Evaluations at any $K$ distinct points are independent uniform field elements because the corresponding Vandermonde matrix is invertible. Apply a fixed nonzero $\mathbb F_2$-linear functional to each evaluation to obtain independent unbiased bits on those coordinates.

The seed has $Kr=O((\log N)^3)$ bits. Enumerating all seeds and testing all $t$-sets is a valid deterministic construction, since $280.1$ guarantees that some seed succeeds. But the seed enumeration alone has \[ 2^{O((\log N)^3)} \] possibilities. This is not polynomial time and is worse than $280.2$ at this level of analysis. A short-looking polylogarithmic seed is not the logarithmic seed length that polynomial enumeration would require.

This reasoning only asserts existence and the usual finite-field evaluation construction; it does not replace the explicit field arithmetic by a hidden exponential preprocessing step. Standard representations of binary finite fields can be found deterministically here by testing degree-$r$ candidate polynomials in time polynomial in $2^r$, hence polynomial in $N$.

A natural explicit graph product loses the logarithmic scale.

The five-cycle has clique number and independence number two. For the lexicographic product $G[H]$, each vertex of $G$ is replaced by a copy of $H$, and pairs of blocks are fully joined exactly when their outer vertices are adjacent.

A clique uses blocks whose outer vertices form a clique of $G$, and within each block it uses a clique of $H$. This proves $\omega(G[H])\le\omega(G)\omega(H)$; choosing maximum cliques realizes equality. The same block argument for nonadjacency gives $\alpha(G[H])=\alpha(G)\alpha(H)$.

The $r$-fold lexicographic power of the five-cycle therefore has \[ N=5^r,\qquad \omega=\alpha=2^r=N^{\log_5 2}. \] Its adjacency matrix is easy to generate, but the homogeneous sets grow as a positive power of $N$, far faster than $\log N$. Repeating a small good example has multiplied the obstruction together with the vertex count. This is a countertest of this product construction, not a lower bound against all explicit graphs.

Existence advice does not become a uniform construction.

For each $N$, one could select a graph guaranteed by $280.1$ and place its adjacency matrix in a separate advice string. Reading that advice prints a good graph quickly. The catalogue instead asks for one deterministic algorithm whose finite description handles every $N$. An arbitrary sequence of successful matrices is not such an algorithm.

Likewise the expected value below one does not identify which edge decisions can be made using only a small portion of the input or a fixed algebraic formula. Conditional expectation succeeds precisely because it evaluates the remaining global risk. Replacing that risk by an unchecked local score removes the proof of the final property.

Verification and outcome.

Small exact tests check the conditional-expectation update and its final integer certificate, using a smaller clique threshold when the displayed constant makes the tiny instances vacuous. Separate checks verify the lexicographic-product formulas and the union-bound exponents. These tests are for the derivations, not a numerical search presented as a general explicit construction.

UNRESOLVED. A deterministic quasipolynomial-time logarithmic-Ramsey construction is justified in full, and the time losses of two tempting alternatives are quantified. The remaining gap is reducing the construction time to one fixed polynomial in $N$ while retaining the logarithmic bound for every size.

Sources

• S1 Benny Sudakov and István Tomon, Ramsey properties of algebraic graphs and hypergraphs; arXiv2103.05618v2 March17,2021. https://arxiv.org/pdf/2103.05618v2. Formulation source.