Erdős Problem #667
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Suppose a large graph is locally dense: every group of \(p\) vertices spans at least \(q\) edges. How large a complete subgraph, or clique, must the whole graph contain? Erdős Problem #667, attributed to Erdős, Faudree, Rousseau and Schelp, asks whether stronger local density forces a strictly larger polynomial clique exponent.
For fixed \(p,q\), write \(H(n;p,q)\) for the largest integer \(m\) such that every qualifying graph on \(n\) vertices contains a clique with \(m\) vertices, and set
$$
c(p,q)=\liminf_{n\to\infty}\frac{\log H(n;p,q)}{\log n}.
$$
The question is whether \(c(p,q)\) increases strictly as the allowed integer \(q\) grows from \(1\) to \(\binom{p-1}{2}+1\). The maintained catalogue records OPEN.
A small example
Take \(p=3\) and \(q=2\). Every triple must contain two edges or more. In the complementary graph, every triple therefore contains at most one edge. Two missing edges sharing a vertex would themselves form two edges inside some triple, so the complement is a matching.
Deleting a maximum matching from the complete graph leaves a graph satisfying the condition, with maximum clique of size about \(n/2\). Conversely, a complement consisting of a matching allows us to select one vertex from each missing edge and every unmatched vertex, giving a clique with at least \(\lceil n/2\rceil\) vertices. Consequently
$$
H(n;3,2)=\lceil n/2\rceil,\qquad c(3,2)=1.
$$
For \(p=3,q=1\), the complement only needs to be triangle-free. The classical triangle-free Ramsey estimates give \(c(3,1)=1/2\). Thus strictness holds in this small endpoint comparison, without settling the question for all \(p\).
What is known
Nondecreasing is easy. A graph satisfying every \(p\) subset edge lower bound \(q+1\) also satisfies the weaker bound \(q\). Hence the family of admissible graphs shrinks, and
$$
H(n;p,q+1)\geq H(n;p,q).
$$
Taking logarithms and lower limits gives \(c(p,q+1)\geq c(p,q)\). This says nondecreasing, which is weaker than the conjectured strictly increasing. One cannot infer a strict inequality without a new estimate.
The maintained #667 statement reports the Ramsey-type benchmark \(1/(p-1)\leq c(p,1)\leq2/(p+1)\), the top-endpoint value \(c(p,\binom{p-1}{2}+1)=1\), and a bound \(c(p,\binom{p-1}{2})\leq1/2\). These are catalogued prior results, not proofs recovered from the original Erdős–Faudree–Rousseau–Schelp publication in this audit.
A useful dual view is the complement: at least \(q\) edges on every \(p\) vertices in \(G\) is exactly at most \(\binom p2-q\) edges on every \(p\) vertices in its complement. This translates forced-clique questions into independence-number questions under forbidden local edge counts.
GCL's current state
The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.
Source interpretation and unresolved mathematical qualification: Nonstrict monotonicity in q follows by inclusion; strictly increasing Ramsey exponents remain conjectural.
The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.
What remains
A bounded follow-up should choose \(p=4\) and one adjacent pair of \(q\) values, then derive upper and lower polynomial exponents for \(H(n;4,q)\) under the exact induced-subgraph conditions. A finite graph search may disprove a proposed local lemma, but it cannot establish asymptotic strictness.
The original historical source and cited benchmarks still need direct review. Later editorial admission requires critical mathematics/source checks, a protected production merge and a browser rendering receipt, followed by a separate V2 exact-hash record.
Sources and claim boundaries
-
Maintained Erdős #667, statement, previous exponent estimates and OPEN status.
-
GCL authenticated #667 source return, elementary monotonicity and endpoint check.
-
Classical triangle-free Ramsey exponent: established input, not re-proved here.
-
Original [Er97f] and EFRS primary source pages: not independently inspected.
Boundary: no new result for general \(p\), no claim of complete primary source review, formal verification, protected publication, deployed MathJax readback or editorial admission.
Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1938 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.