we-solve (beta)

Math-6040 · mathematics · Mathematics

Erdős Problem #986

Status Solved · erdosproblems.comLLM status Solved from source status

Statement

Let R(k,n) denote the (off-diagonal) graph Ramsey number: the least integer N such that every simple graph G on N vertices contains either - a clique K_k, or - an independent set of size n.

Conjecture: For each fixed integer k>=3 there exist constants c=c(k)>0 and C=C(k)>0 such that for all sufficiently large integers n,

R(k,n) >= C * n^{k-1} / (log n)^c.

Restatement from Math-6040-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-6040-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-6040

Erdős Problem 986: off-diagonal Ramsey numbers

Statement and attribution

For each fixed $s\ge3$, prove $R(s,k)\gg_s k^{s-1}/(\log k)^{c(s)}$. We reconstruct Bradač's proof of the stronger bound \[ R(s,k)\gg_s \frac{k^{s-1}}{(\log k)^{2s-4}} \] from Section 2.5 of Off-diagonal Ramsey numbers, arXiv:2605.28793v3. That version credits an internal OpenAI model for the final improvement of the exponent to $s-1$. The reconstruction below includes the geometric graph, its spectrum, the counting argument, and the sampling step. No novelty is claimed.

The projective polarity graph

Fix $t=s-1\ge2$ and a power $q$ of $2$. The vertices of $G$ are the one-dimensional subspaces of $\mathbb F_q^{t+1}$; join $a,b$ when $a\perp b$ for the usual nondegenerate dot product. Loops are allowed at this intermediate stage. The graph is regular with \[ n=\frac{q^{t+1}-1}{q-1}\asymp q^t,\qquad d=\frac{q^t-1}{q-1}\asymp q^{t-1}. \] Two different vertices have exactly $c=(q^{t-1}-1)/(q-1)$ common neighbors: their two independent linear equations cut out a $(t-1)$-dimensional vector subspace. If $A$ is the adjacency matrix, then $A^2=(d-c)I+cJ$, with $d-c=q^{t-1}$. Consequently, on the orthogonal complement of the constant vector, its eigenvalues have modulus $\lambda=q^{(t-1)/2}$. The usual decomposition of two indicator vectors into constant and orthogonal parts proves \[ \left|e_G(U,V)-\frac dn|U||V|\right| \le\lambda\sqrt{|U||V|}. \tag{1} \] Here edges between two sets are counted as ordered incidences, so $1$ also applies to overlapping sets.

A digraph with no transitive $s$-tournament

Let $D$ have as vertices the ordered pairs $(a,b)$ with $a\perp b$. Draw an arc $(a,b)\to(a',b')$ exactly when $a\perp b'$ and $a'\not\perp b$. It has $nd\asymp q^{2t-1}$ vertices and has neither loops nor opposite arcs. Suppose $(a_i,b_i)$, $1\le i\le t+1$, form a transitive tournament in that order. Choose nonzero vector representatives $x_i,y_i$. We have $x_i\cdot y_j=0$ for $i\le j$, and $x_{i+1}\cdot y_i\ne0$. Choose also $x_{t+2}$ with $x_{t+2}\cdot y_{t+1}\ne0$. In a nontrivial relation $\sum_jc_jy_j=0$, let $i$ be its smallest nonzero coefficient. Taking the dot product with $x_{i+1}$ kills all later terms and leaves a contradiction. Thus the $t+1$ vectors $y_j$ form a basis. But $x_1$ is orthogonal to all of them, another contradiction.

Counting ordered tuples with no forward arcs

Call a sequence $(a_1,b_1),\ldots,(a_m,b_m)$ consistent if $a_i\perp b_i$, and if $a_i\perp b_j$ for $i<j$, then $a_j\perp b_i$. This is exactly a tuple with no forward arc in $D$. Repetitions are allowed for this upper bound. For a consistent prefix $\sigma$, define \[ W_\sigma(y)=\operatorname{span}\{b_i:a_i\perp y\},\quad r_\sigma(y)=\dim W_\sigma(y),\quad U_r=\{y:r_\sigma(y)\le r\},\quad Z_r=\{y:r_\sigma(y)=r\}. \] An extension $(a,b)$ must have $a\perp W_\sigma(b)$ and $a\perp b$. If $r=r_\sigma(b)\le t$, there are at most $2q^{t-r}$ possibilities for $a$, even after dropping the latter condition; if $r=t+1$ there are none.

For each nonempty $U_r$, $0\le r\le t$, choose $\ell\le r$ with $|Z_\ell|$ maximal. Then $|Z_\ell|\ge |U_r|/(t+1)$ and $|Z_r|\le|Z_\ell|$. Call $b\in Z_r$ popular if it lies in at least $|Z_\ell|/(16q)$ of the spaces $W_\sigma(y)$, $y\in Z_\ell$. Each such space contains at most $2q^{\ell-1}$ projective points (zero when $\ell=0$), so there are at most $32q^\ell$ popular $b$. Mark extensions using them. For this $r$ there are at most $32q^\ell\cdot2q^{t-r}\le64q^t$ marked extensions.

Call $a$ poor if $|N_G(a)\cap Z_\ell|\le |Z_\ell|/(8q)$, and write $P_r$ for these $a$. For sufficiently large $q$, $d/n\ge1/(4q)$. Combining the definition of poverty with $1$ gives \[ |P_r||Z_\ell|\ll q^{t+1}. \] Since $|Z_r|\le|Z_\ell|$, another application of $1$ gives \[ e_G(P_r,Z_r)\le\frac dn|P_r||Z_r|+ \lambda\sqrt{|P_r||Z_r|}\ll q^t. \] Mark all extensions with poor $a$, too. Summing over $r$ shows that each prefix has at most $h=C_tq^t$ marked children.

For an unmarked extension $(a,b)$ with $b\in Z_r$, $a$ is not poor and $b$ is not popular. At least $|Z_\ell|/(16q)$ points $y\in Z_\ell$ satisfy both $a\perp y$ and $b\notin W_\sigma(y)$. Their span dimension rises from $\ell$ to $\ell+1$. No dimension decreases. Thus this extension reduces $|U_\ell|$ by a factor at most \[ 1-\frac1{16(t+1)q}. \] Initially every $|U_\ell|$ is at most $n\ll q^t$. For each fixed $\ell$, only $O_t(q\log q)$ such reductions can occur while the integer $|U_\ell|$ remains positive; once it is zero it cannot be chosen again. There are only $t+1$ possibilities for $\ell$. Therefore every path of extensions has at most $w=C'_tq\log q$ unmarked steps.

The full number of children is at most $\Delta=nd\ll q^{2t-1}$. The number $F_k$ of consistent $k$-tuples is bounded by \[ F_k\le\sum_{i\le\min(w,k)}\binom{k}{i}\Delta^ih^{k-i} \le2^kh^k\max(1,\Delta/h)^w \le(C''_tq^t)^k \tag{2} \] provided $k\ge C'''_tq(\log q)^2$. The last inequality follows since the logarithm of the extra factor is $O_t(w\log q)=O_t(q(\log q)^2)$, which is absorbed by a fixed exponential in $k$.

From the digraph to a Ramsey graph

Order $V(D)$ uniformly at random. Join $u<v$ in an undirected graph $\Gamma$ if $D$ has the forward arc $u\to v$. Every clique in $\Gamma$ would be a transitive tournament in $D$, so $\Gamma$ is $K_s$-free. For a fixed $k$-set, its relative ordering is uniform among $k!$ possibilities. Summing over sets, the expected number $i_k(\Gamma)$ of independent $k$-sets is at most $F_k/k!$. Some order consequently gives \[ i_k(\Gamma)\le\left(\frac{eC''_tq^t}{k}\right)^k. \] Select each vertex independently with probability $p=k/(eC''_tq^t)$, which is at most $1$ for the parameters below. The expected value of the number of selected vertices minus the number of independent $k$-sets among them is at least $pnd-1$. Choose a realization attaining at least this value and delete one vertex from each surviving independent $k$-set. This leaves a $K_s$-free graph with independence number less than $k$ and at least \[ pnd-1\gg_t kq^{t-1} \] vertices. Deleting vertices cannot create a new independent $k$-set that was not already present.

Choice of the field size and conclusion

For each sufficiently large $k$, choose the largest power of $2$ for which $C'''_tq(\log q)^2\le k$. Consecutive powers differ by $2$, so $q\asymp_t k/(\log k)^2$. In particular $p\le1$ for large $k$, since $t\ge2$. The preceding construction yields \[ R(s,k)\gg_s k\left(\frac{k}{(\log k)^2}\right)^{s-2}. \] Adjusting the positive constant covers the finitely many remaining $k\ge2$. All substantive counting steps have been reconstructed; the standard existence of finite fields and elementary spectral linear algebra are the background inputs. Sources: https://www.erdosproblems.com/986 and https://arxiv.org/abs/2605.28793v3.

COMPLETION ESTIMATE

COMPLETION: 100%

Go to contribution →

Math-6040-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-6040

1) FORMAL RESTATEMENT

Let R(k,n) denote the (off-diagonal) graph Ramsey number: the least integer N such that every simple graph G on N vertices contains either - a clique K_k, or - an independent set of size n.

Conjecture: For each fixed integer k>=3 there exist constants c=c(k)>0 and C=C(k)>0 such that for all sufficiently large integers n,

R(k,n) >= C * n^{k-1} / (log n)^c.

2) QUICK LITERATURE/CONTEXT CHECK

The problem file states that this conjecture is known for k=3 (Spencer) and for k=4 (Mattheus--Verstraete). It also quotes general upper/lower bounds (not needed for the arguments below).

3) ATTACK PLAN

- Prove easy structural facts: recursion and the standard polynomial upper bound. - Prove a baseline probabilistic lower bound (weaker than the conjecture but completely self-contained). - Do a small-case computation to sanity-check the definition $R(3,3)$.

4) WORK

FAST REALITY CHECK (exact small computation): R$3,3$=6.

I verified this by brute force over all graphs on N vertices for N<=6. A graph "witnesses R$3,3$>N" if it has no triangle and no independent set of size 3. The computation found witnesses for N=3,4,5 and none for N=6. One witness on 5 vertices is the 5-cycle.

Exact output from a minimal script: 

n 3 exists True
n 4 exists True
n 5 exists True
n 6 exists False
example mask for n=5 220
edges [(0, 3), (0, 4), (1, 2), (1, 4), (2, 3)]

(Here "exists False" at N=6 means there is no graph on 6 vertices avoiding both a triangle and an independent triple.)

---

Lemma 986.1 (Ramsey recursion). For integers k,n>=2,

R(k,n) <= R$k-1,n$ + R$k,n-1$.

Proof. Let N = R$k-1,n$ + R$k,n-1$. Consider any graph G on N vertices and fix a vertex v. Partition the remaining N-1 vertices into A = neighbors of v, B = non-neighbors of v. Then |A|+|B|=N-1.

If |A| >= R$k-1,n$, then the induced subgraph G[A] contains either - a K_{k-1}, in which case adding v gives a K_k in G, or - an independent set of size n, which is also independent in G.

If |A| < R$k-1,n$, then |B| >= N-1-$R(k-1,n)-1$ = R$k,n-1$. In that case G[B] contains either - a K_k (done), or - an independent set of size n-1; together with v (which is non-adjacent to all of B) this forms an independent set of size n in G.

Thus every graph on N vertices contains K_k or an independent n-set, so R(k,n) <= N. $\square$

Corollary 986.2 (Erdos--Szekeres binomial upper bound). For k,n>=1,

R(k,n) <= $\binom{k+n-2}{k-1}$.

Proof. Define U(k,n)=$\binom{k+n-2}{k-1}$. One checks the same recursion U(k,n)=U$k-1,n$+U$k,n-1$, with base cases U$1,n$=U$k,1$=1. Using Lemma 986.1 and induction on k+n gives R(k,n) <= U(k,n). $\square$

---

Lemma 986.3 (A self-contained probabilistic lower bound). Fix an integer k>=3. For all sufficiently large n, there exists a graph on at least

$1/(2(10k)^{k/2})$ * (n/log n)^{k/2}

vertices with no K_k and with independence number < n. Consequently,

R(k,n) >= c_k * (n/log n)^{k/2}

for a positive constant c_k depending only on k.

Proof. Let n be large (so that log n>0 and the estimates below hold). Define

\[ N := \left\lfloor (n/(10k\,\log n))^{k/2} \right\rfloor, p := (5k\,\log n)/n. \]

Consider the random graph G   G(N,p).

Step 1: bound the expected number X of independent sets of size n. For a fixed n-subset S of vertices, the probability it is independent is $1-p$^{$\binom{n}{2}$}. Hence

E[X] = $\binom{N}{n}$ $1-p$^{$\binom{n}{2}$}.

Use the crude bounds $\binom{N}{n}$ <= (eN/n)^n and $1-p$^{$\binom{n}{2}$} <= exp$-p\,n(n-1)/2$ <= exp$-p\,n^2/3$ for n>=2. Thus

E[X] <= exp( n$\log(eN/n)$ - $p n^2$/3 ).

Now compute a simple upper bound on $\log(eN/n)$: since N <= $n/(10k\log n)$^{k/2},

eN/n <= e * n^{k/2-1} / $10k\log n$^{k/2}.

For fixed k and large n this is <= n^{k/2} (say), hence $\log(eN/n)$ <= $k/2$$\log$ n. Therefore

n$\log(eN/n)$ <= $k/2$ n$\log$ n, $p n^2$/3 = $5k\log n$/n * n^2/3 = $5k/3$ n$\log$ n.

So the exponent is <= $(k/2) - (5k/3)$ n$\log$ n = -$7k/6$ n$\log$ n, which is < -10 for large n. In particular E[X] < 1/4. Thus P$X>=1$ <= E[X] < 1/4 (Markov), so with probability > 3/4 the random graph has no independent set of size n.

Step 2: bound the expected number Y of K_k subgraphs. For each k-subset T, the probability it forms a clique is $p^{\binom{k}{2}}$. Hence

E[Y] = $\binom{N}{k}$ $p^{\binom{k}{2}}$ <= N^k $p^{\binom{k}{2}}$.

Let t=$\binom{k}{2}$=k$k-1$/2. Using N <= $n/(10k\log n)$^{k/2} and p=$5k\log n$/n,

N^k p^t <= $n/(10k\log n)$^{k^2/2} * $5k\log n/n$^{k$k-1$/2} = $ (5k)/(10k) $^{t} * $n^{k/2}/(\log n)^{k/2}$ * $1/(10k)$^{k/2} = $1/2$^{t} * $n/(10k\log n)$^{k/2}.

Since N is the floor of $n/(10k\log n)$^{k/2}, for large n we have E[Y] <= $1/2$^{t} $N+1$ <= $1/2$^{t}*2N <= N/4, because t>=3 for k>=3. Then P$Y > N/2$ <= E[Y]/$N/2$ <= $N/4$/$N/2$=1/2 by Markov; in fact the above gives <=1/2. So with probability at least 1/2, both events occur: - X=0 (no independent n-set), and - Y <= N/2 (at most N/2 copies of K_k).

Fix a realization of G with these two properties. Delete one vertex from each K_k present in G (choose arbitrarily one vertex per clique). Since there are at most N/2 cliques, we delete at most N/2 vertices, leaving an induced subgraph G' on at least N/2 vertices.

- G' has no K_k by construction. - G' has no independent set of size n: any independent n-set in G' would also be an independent n-set in the original G because deleting vertices does not create new edges.

Thus R(k,n) > |V(G')| >= N/2. Substituting the definition of N yields the claimed lower bound with c_k = 1/$2(10k)^{k/2}$. $\square$

5) VERIFICATION

- The brute-force computation checks the definition: it finds a 5-vertex witness and verifies none exists on 6 vertices, consistent with the classical statement R$3,3$=6. - Lemma 986.1 recursion proof checked by neighborhood partition. - Lemma 986.3: all probabilistic inequalities are explicit (Markov + union bound). Deleting vertices cannot create a new independent set of a fixed size.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here: - An elementary upper bound: R(k,n) <= binom{k+n-2}{k-1}. - A self-contained probabilistic lower bound: R(k,n) >= c_k (n/log n)^{k/2}. - Exact small-case computation: R$3,3$=6.

(ii) First gap (crisp statement): Improve the exponent in the lower bound from k/2 to k-1 (up to polylog factors), i.e. prove that for fixed k>=5 the largest K_k-free graphs with independence number < n can have N on the order n^{k-1}/(log n)^{O$1$}.

(iii) Top 3 next moves (concrete): 1. Try to adapt sparse random / semi-random constructions to push the exponent from k/2 to $k+1$/2 (already nontrivial) without importing heavy external theorems. 2. For a fixed k (say k=5), attempt a dedicated construction and compute numerically the best N achievable by heuristic search to guess the right polylog. 3. Re-express the conjecture as a statement about maximal size of K_k-free graphs with bounded independence number and look for a container-style counting argument.

(iv) Minimal counterexample structure: A fixed k>=3 for which there exists an infinite sequence n_i->infty with R$k,n_i$ << n_i^{k-1}/(log n_i)^{c} for every c>0; equivalently, for infinitely many n there is a K_k-free graph on about n^{k-1}/(log n)^{c} vertices with independence number < n failing for all c.

Go to contribution →