Is the local-density Ramsey exponent $c(p,q)$ strictly increasing in $q$? (Erdős #667)
Statement
Fix integers $p,q\geq 1$. Let $H(n;p,q)$ be the largest $m$ such that every graph on $n$ vertices in which every set of $p$ vertices spans at least $q$ edges must contain a complete graph $K_m$. Define $$c(p,q)=\liminf_{n\to\infty}\frac{\log H(n;p,q)}{\log n}.$$ Is $c(p,q)$ a strictly increasing function of $q$ on the range $1\leq q\leq \binom{p-1}{2}+1$? That is, does $c(p,q)<c(p,q+1)$ hold throughout this range for every fixed $p$?
Acceptance. FULLY RESOLVES: a complete proof that $c(p,q)$ is strictly increasing in $q$ on $1\leq q\leq \binom{p-1}{2}+1$ for every fixed $p$ (equivalently $c(p,q)<c(p,q+1)$ throughout), machine-checkable (Lean) preferred or a full written proof; OR a disproof exhibiting specific $p$ and $q$ in range with $c(p,q)=c(p,q+1)$, together with a proof of that equality (matching upper and lower exponent bounds). ADVANCES: prove strict monotonicity for a specific fixed $p$ (e.g. $p=4$ or $p=5$) across all admissible $q$, with proof; OR determine $c(p,q)$ exactly, or improve its best known upper or lower bound, for a specific pair $(p,q)$ beyond the values recorded here ($c(p,1)\in[\tfrac{1}{p-1},\tfrac{2}{p+1}]$, $c(p,\binom{p-1}{2})\leq 1/2$, $c(p,\binom{p-1}{2}+1)=1$), with proof; OR compute $H(n;p,q)$ exactly for a new range of small $n,p,q$ via exhaustive/SAT search, giving certified numerical bounds on $c(p,q)$ with reproducible code. Deliver a proof, a counterexample with proof, or improved bounds / certified small-case values.
Background
A problem of Erdős, Faudree, Rousseau and Schelp [Er97f]; listed as open on erdosproblems.com/667 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). The quantity $H(n;p,q)$ measures the largest clique forced by a *local density* condition (every $p$-set spans $\geq q$ edges), interpolating between Ramsey-type and Turán-type extremal problems, and $c(p,q)$ is its polynomial growth exponent. Anchor values: when $q=1$ the condition 'every $p$ vertices span at least one edge' just says the graph has no independent set of size $p$, so $H(n;p,1)$ is the largest guaranteed clique under bounded independence number — the classical Ramsey regime — giving $$\tfrac{1}{p-1}\leq c(p,1)\leq \tfrac{2}{p+1};$$ at the top of the range, $q=\binom{p-1}{2}+1$ forces $c(p,q)=1$ (a linear-size clique). Erdős, Faudree, Rousseau and Schelp further showed $c(p,\binom{p-1}{2})\leq 1/2$. The monotonicity question — whether each extra required edge strictly raises the exponent across the whole admissible range — is open. Erdős offered no cash prize. The attacker's tool: for fixed small $p$, exhaustive/SAT computation of $H(n;p,q)$ over accessible $n$ to bound $c(p,q)$ and separate consecutive $q$, combined with Ramsey–Turán constructions and pseudorandom lower-bound graphs to pin the exponents.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #667 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.