Erdős problem #667 — wave 6i report

Date of live-page audit: 2026-07-27 (UTC)

Claim labels

• (a) elementary-rigorous: proved below from definitions and elementary graph arguments.
• (b) rigorous-modulo-named-theorem: the dependency is named and linked.
• (c) plausible/structural-unverified: heuristic or literature-search conclusion, not used as a theorem.
• (d) computational-only: exact for the stated finite range under the stated exhaustive computation; not promoted to an asymptotic theorem.

0. Mandatory live-page audit

I fetched https://www.erdosproblems.com/667 and its discussion thread through the Bright Data browser on 2026-07-27. Direct datacenter access to the LaTeX endpoint returned HTTP 403, as anticipated. The browser-rendered page said:

• status: OPEN;
• comments: 1;
• claimed proofs: 0;
• “Interested in collaborating”: None;
• “Currently working on this problem”: None;
• every other participation/formalisation marker shown on the page: None.

Thus the required stop condition did not fire.

Verbatim live statement

The following is the exact text returned by the live page's “View the LaTeX source” endpoint, including its apparent n/N typo:

> Let \(p,q\geq 1\) be fixed integers. We define \(H(n)=H(N;p,q)\) to be the largest \(m\) such that any graph on \(n\) vertices where every set of \(p\) vertices spans at least \(q\) edges must contain a complete graph on \(m\) vertices.

> Is

> \[ > c(p,q)=\liminf \frac{\log H(n)}{\log n} > \]

> a strictly increasing function of \(q\) for \(1\leq q\leq \binom{p-1}{2}+1\)?

The live page attributes the problem to Erdős, Faudree, Rousseau, and Schelp and lists these known assertions:

1. When \(q=1\), this is the classical off-diagonal Ramsey problem, with

\[ \frac1{p-1}\leq c(p,1)\leq\frac2{p+1}. \]

2. If \(q=\binom{p-1}{2}+1\), then \(c(p,q)=1\).

3. The page says that Erdős, Faudree, Rousseau, and Schelp showed

\[ c\!\left(p,\binom{p-1}{2}\right)\leq\frac12. \]

The sole comment, by ho boon suan at 08:26 on 18 April 2026, contains the following mathematical leads. The site explicitly warns that comments are unverified.

• \(c(p,q)\) is nondecreasing in \(q\).
• The displayed penultimate bound \(\leq1/2\) appears wrong. For \(p=2k\), \(k\geq3\), the comment derives

\[ c\!\left(2k,\binom{2k-1}{2}\right)\geq1-\frac1k>\frac12 \]

from the Bondy–Simonovits even-cycle theorem.

• It substitutes the upper bound \(2p/(2p+1)\), using Erdős's 1959 high-girth construction.
• It states

\[ c\!\left(p,\binom{p-2}{2}+1\right)\geq\frac12 \]

and gives the finite lower bound

\[ \alpha(F)\geq\sqrt{\frac n{p-2}}-\frac1{p-2} \]

when every \(p\)-set of \(F\) spans at most \(2p-4\) edges.

• It states \(c(4,2)=1/2\) and reduces the only remaining \(p=4\) jump to the independence exponent of \(\{C_3,C_4\}\)-free graphs.

No claimed solution or current worker appeared anywhere on the live page or discussion thread.

There is a minor literal edge case: for \(p=1,q=1\), no graph satisfies “every one-vertex set spans at least one edge”, so “largest \(m\)” is not finite without an added convention. (a) Everything below concerns \(p\geq3\); \(p=2\) has only \(q=1\) and no strictness comparison to make.

1. Primary-source audit

I searched the exact notation and several verbatim fragments of the statement, as well as the equivalent local-sparsity formulation developed below. I found the original problem and the standard Ramsey ingredients, but no paper claiming to settle the full strict-monotonicity question.

1. Original source. Problem 13 of Paul Erdős, “Some Unsolved Problems,” in Combinatorics, Geometry and Probability (1997), pp. 1–10, states this problem. The chapter DOI is 10.1017/CBO9780511662034.004. The scanned source on pp. 4–5 defines \(H(n;p,q)\), gives the Ramsey bounds, and asks for strict increase.

2. 1959 high-girth result. Erdős, “Graph Theory and Probability,” Canadian Journal of Mathematics 11 (1959), 34–38, defines \(h(k,\ell)\) and proves

\[ h(k,\ell)>\ell^{\,1+1/(2k)} \]

for fixed \(k\) and sufficiently large \(\ell\); see the scan at renyi.hu/~p_erdos/1959-06.pdf. The April 2026 comment quotes this correctly. (b)

3. A stronger result already visible in the older cycle-Ramsey literature. Erdős, Faudree, Rousseau, and Schelp, “On Cycle–Complete Graph Ramsey Numbers,” J. Graph Theory 2 (1978), 53–64, DOI 10.1002/jgt.3190020107, records as equation (1.4) Spencer's bound

\[ r(\leq C_m,K_t)\geq c_m(t/\log t)^{(m-1)/(m-2)} \]

for fixed \(m\). The paper is available at renyi.hu/~p_erdos/1978-18.pdf. Its cited primary source is Joel Spencer, “Asymptotic Lower Bounds for Ramsey Functions,” Discrete Mathematics 20 (1977), 69–76, DOI 10.1016/0012-365X(77)90044-990044-9). This gives the stronger penultimate estimate

\[ c\!\left(p,\binom{p-1}{2}\right)\leq\frac{p-2}{p-1}, \]

not merely the comment's \(2p/(2p+1)\). (b)

4. Correction to the live-page \(\leq1/2\) assertion. Bondy and Simonovits, “Cycles of Even Length in Graphs,” J. Combin. Theory Ser. B 16 (1974), 97–105, DOI 10.1016/0095-8956(74)90052-590052-5), proves

\[ \operatorname{ex}(n,C_{2k})\leq100k\,n^{1+1/k}. \]

This verifies the comment's contradiction to the page for every even \(p=2k\geq6\). (b)

5. Triangle Ramsey number. Jeong Han Kim, “The Ramsey Number \(R(3,t)\) Has Order of Magnitude \(t^2/\log t\),” Random Structures & Algorithms 7 (1995), 173–207, DOI 10.1002/rsa.3240070302. (b)

6. Current \(R(4,t)\) exponent. Sam Mattheus and Jacques Verstraete, “The Asymptotics of \(r(4,t)\),” Annals of Mathematics 199 (2024), 919–941, arXiv:2306.04007, proves

\[ r(4,t)=\Omega(t^3/\log^4t). \]

Together with the classical \(O(t^3/\log^2t)\) upper bound quoted and used there, this fixes the polynomial exponent at \(3\). (b)

The searches did not find a later primary source using the exact \(H(n;p,q)\) notation to resolve strict monotonicity. That is an honest search miss, not evidence that no such paper exists. (c)

2. Exact complement formulation

Put

and let \(\mathcal P_{p,q}\) be the class of graphs \(F\) such that

Taking \(F=\overline G\), a \(p\)-set has at least \(q\) edges in \(G\) exactly when it has at most \(\binom p2-q=r\) edges in \(F\), and a clique in \(G\) is an independent set in \(F\). Therefore

This is an exact equality. (a)

It follows immediately that \(H(n;p,q)\), and hence \(c(p,q)\), is nondecreasing in \(q\): increasing \(q\) decreases \(r\) and shrinks the class over which the minimum in (2.1) is taken. (a)

The live range \(q\leq\binom{p-1}{2}+1\) is exactly

3. A uniform local-lemma upper bound

Theorem

For \(p\geq3\) and

one has

This is rigorous modulo the asymmetric Lovász Local Lemma. (b)

At \(q=1\), (3.1) is exactly the live page's standard upper bound \(2/(p+1)\). At \(q=\binom{p-1}{2}\), it becomes Spencer's stronger \((p-2)/(p-1)\). Thus (3.1) interpolates those two known cases.

Proof

Write \(r=\binom p2-q\). If \(r=p-2\), the right-hand side of (3.1) is \(1\), which is trivial. Assume \(r>p-2\), and put

Let \(t\to\infty\), choose a fixed constant \(\lambda=12\mu\), and set

Take \(F\sim G(N,\rho)\).

There are two kinds of bad events:

• \(A_S\), for \(S\in\binom{[N]}p\): \(F[S]\) has at least \(r+1\) edges;
• \(B_T\), for \(T\in\binom{[N]}t\): \(T\) is independent.

Join two events in the dependency graph when their sets of underlying edge variables overlap, equivalently when their vertex sets overlap in at least two vertices. Events outside a neighborhood are mutually independent of the event in question.

Let \(C_0=\binom{\binom p2}{r+1}\). A union bound over choices of \(r+1\) present edges gives

Also, for all large \(t\),

Assign Local-Lemma weights

The total \(x_B\)-weight of all \(B\)-events satisfies

because \(\lambda=12\mu\).

A fixed \(A\)-event has \(O(N^{p-2})\) neighboring \(A\)-events. Hence their total \(x_A\)-weight is

Together with (3.4), the total neighboring weight of an \(A\)-event is \(o(1)\).

A fixed \(B\)-event has \(O(t^2N^{p-2})\) neighboring \(A\)-events, so their total weight is

Its neighboring \(B\)-weight is again \(o(1)\) by (3.4).

For all weights at most \(1/2\),

Equations (3.2) and (3.5) show, for large \(t\), that

Equations (3.3) and (3.6) show the same for \(B_T\), since the spare exponent between \(\Pr(B_T)\) and \(x_B\) is \(\Theta(t\log t)\), whereas the neighbor-weight loss is only \(O(t)\). The asymmetric Lovász Local Lemma now supplies an \(F\) with no bad event.

Thus \(F\in\mathcal P_{p,q}\) and \(\alpha(F) \[ H(N;p,q)Finally,

so along these \(N\),

This proves (3.1).

Independent arithmetic check

The verifier checks with exact rational arithmetic, for every \(3\leq p\leq40\) and every live-range \(q\), the two cancellations used above:

It also checks that multiplying by \(t^2\) changes the first exponent from \(-1\) to \(+1\). (d)

4. An elementary neighborhood recurrence

Theorem

For \(p\geq3\) and

one has

This is elementary-rigorous. (a)

Proof

Let \(F\in\mathcal P_{p,q}\), let \(v\) have maximum degree \(\Delta\), and put \(X=N_F(v)\). Every \((p-1)\)-set \(S\subseteq X\) satisfies

and therefore

Consequently \(F[X]\in\mathcal P_{p-1,q}\), and (2.1) gives

The greedy bound also gives

Set \(a=c(p-1,q)\). By the definition of a liminf, for every \(\varepsilon>0\) and all sufficiently large \(d\),

If \(\Delta\geq n^{1/(1+a-\varepsilon)}\), use (4.2); otherwise use (4.3). In either case,

Take the minimum over \(F\), then let \(n\to\infty\) and \(\varepsilon\downarrow0\). This proves (4.1).

Triangular lower thresholds

At

the complement threshold for parameter \(s\) is \(s-2\). If \(F\in\mathcal P_{s,q_s}\), no component of \(F\) can contain \(s\) vertices: a spanning tree on \(s\) vertices would already contribute \(s-1\) edges to an \(s\)-set. Thus every component has at most \(s-1\) vertices, so \(\alpha(F)\geq n/(s-1)\), and \(c(s,q_s)=1\). (a)

Iterating (4.1), and using

gives, for \(2\leq s\leq p\),

This recovers the classical \(1/(p-1)\) lower bound at \(q=1\) by taking \(s=2\), and the comment's \(1/2\) lower bound by taking \(s=p-1\). (a)

For completeness, the comment's explicit finite \(1/2\)-bound follows from the same idea without asymptotic notation. If every \(p\)-set of \(F\) has at most \(2p-4\) edges, then every component of \(F[N(v)]\) has at most \(p-2\) vertices; otherwise \(v\), together with a connected \((p-1)\)-vertex subgraph of its neighborhood, would span at least \(2p-3\) edges. Hence

Splitting at \(\Delta=\sqrt{n(p-2)}-1\) yields

So that part of the page comment checks out from first principles. (a)

5. Two proved families of strict adjacent jumps

Combining the upper bound (3.1) with the lower thresholds (4.4) proves strictness at two adjacent pairs for every \(p\geq4\).

First family

At the left endpoint,

so (3.1) gives

At

equation (4.4), with \(s=p-1\), gives \(c(p,q_+)\geq1/2\). Therefore

This is rigorous modulo the asymmetric Lovász Local Lemma. (b)

Final family

Similarly,

so

This is rigorous modulo the asymmetric Lovász Local Lemma; it also follows from Spencer's cited short-cycle Ramsey bound. (b)

These are genuine adjacent comparisons required by the original problem. They do not prove all the intervening comparisons.

The verifier checks both strict rational inequalities for \(3\leq p\leq40\), but the displayed algebra itself is uniform in \(p\). (d)

6. Audit of the disputed live-page bound

Let \(p=2k\), \(k\geq3\), and

If \(G\) is admissible and \(F=\overline G\), then every \(2k\)-set of \(F\) has at most \(2k-1\) edges, so \(F\) is \(C_{2k}\)-free. Bondy–Simonovits gives

The elementary random-order/greedy bound

then yields

Consequently

Thus the live page's displayed \(\leq1/2\) assertion cannot be correct as written for even \(p\geq6\). This verification is rigorous modulo Bondy–Simonovits. (b)

Together with (3.1), the corrected interval is

The lower endpoint uses Bondy–Simonovits; the upper endpoint uses the Local Lemma or Spencer. (b)

7. Complete reduction for \(p=4\)

The four values of \(q\) are \(1,2,3,4\).

\(q=1\)

This is the inverse \(R(4,t)\) problem. Mattheus–Verstraete and the matching polynomial exponent in the classical upper bound give

This is rigorous modulo those Ramsey theorems. (b)

\(q=2\)

Here every four vertices of \(F=\overline G\) span at most four edges.

For a vertex \(v\), the graph on \(N(v)\) has maximum degree at most one: a two-edge path \(a-b-c\) inside \(N(v)\), together with the three edges from \(v\), would give five edges on \(\{v,a,b,c\}\). Hence

and therefore \(\alpha(F)\geq n^{1/2-o(1)}\). (a)

Conversely, every triangle-free graph is feasible, since a triangle-free graph on four vertices has at most four edges. Kim's triangle-free Ramsey construction has \(\alpha(F)=O(\sqrt{n\log n})\). Therefore

The upper half is rigorous modulo Kim's theorem. (b)

\(q=3\): exact structural reduction

Now every four vertices of \(F\) span at most three edges. A triangle in \(F\) cannot have an edge to any outside vertex, since the triangle plus that edge would make four edges on four vertices. Thus every triangle is an isolated \(K_3\) component. After deleting these components, the remaining graph has neither a triangle nor a \(C_4\). Conversely, any disjoint union of isolated \(K_3\)'s and a \(\{C_3,C_4\}\)-free graph satisfies the four-vertex/three-edge condition. (a)

Define

The component classification gives the exact finite identity

This is elementary-rigorous. (a)

Spencer's bound, or the \(p=4,q=3\) instance of (3.1), gives \(f(n)\leq n^{2/3+o(1)}\) after the usual monotone interpolation, so \(f(n)=o(n)\). Since \(f\) is nondecreasing, (7.1) implies

Indeed, \(H(n;4,3)\leq f(n)\); while splitting (7.1) into \(j\geq n/6\) and \(j \[ H(n;4,3)\geq f(\lfloor n/2\rfloor). \]

This reduction is rigorous modulo the short-cycle Ramsey upper construction used only to know \(f=o(n)\). (b)

Consequently the only unresolved \(p=4\) comparison is precisely:

> Does every \(\{C_3,C_4\}\)-free \(n\)-vertex graph have

> \(\alpha(F)\geq n^{1/2+\varepsilon}\) for one absolute

> \(\varepsilon>0\), or are there such graphs with

> \(\alpha(F)=n^{1/2+o(1)}\) along a sequence?

The elementary maximum-degree argument gives the lower exponent \(1/2\), and (3.1) gives the construction-side upper exponent \(2/3\):

The strict jump \(c(4,2)(a)/(b)

\(q=4\)

This is the live top endpoint, so \(c(4,4)=1\). (a)

Thus

and only the middle strict inequality remains. (a)/(b)

For \(p=3\), Kim's theorem gives \(c(3,1)=1/2\), while the top endpoint gives \(c(3,2)=1\); hence the conjecture is true for \(p=3\). (b)

8. Exact finite computation

I exhaustively enumerated every isomorphism class of \(\{C_3,C_4\}\)-free graph through 15 vertices using nauty 2.8.8:

nauty-geng -q -tf n | nauty-countg -q --h

Here \(f(n)\) is as above. “Extremal classes” counts isomorphism classes with independence number exactly \(f(n)\).

| \(n\) | all \(\{C_3,C_4\}\)-free classes | \(f(n)\) | extremal classes | \(H(n;4,3)\) from (7.1) |

|---:|---:|---:|---:|---:|

| 1 | 1 | 1 | 1 | 1 |

| 2 | 2 | 1 | 1 | 1 |

| 3 | 3 | 2 | 2 | 1 |

| 4 | 6 | 2 | 2 | 2 |

| 5 | 11 | 2 | 1 | 2 |

| 6 | 23 | 3 | 7 | 2 |

| 7 | 48 | 3 | 4 | 3 |

| 8 | 114 | 4 | 35 | 3 |

| 9 | 293 | 4 | 30 | 3 |

| 10 | 869 | 4 | 11 | 4 |

| 11 | 2963 | 5 | 446 | 4 |

| 12 | 12066 | 5 | 345 | 4 |

| 13 | 58933 | 5 | 60 | 5 |

| 14 | 347498 | 5 | 3 | 5 |

| 15 | 2455693 | 6 | 18712 | 5 |

Therefore

This is computational-only and says nothing by itself about the limiting exponent. (d)

The standalone verifier does more than replay the printed table:

1. it checks all Local-Lemma exponent cancellations and strict-jump arithmetic with exact Fraction values;

2. without nauty or any third-party Python package, it enumerates every labelled graph through six vertices, verifies the structural classification in §7 in both directions, and recomputes \(H(n;4,3)\);

3. it runs the nauty census through 15 vertices;

4. for every \(n\), it extracts an extremal graph6 record, decodes it in Python, checks from scratch that it has no \(C_3\) or \(C_4\), and exhaustively recomputes its independence number.

Reproduction:

cd /home/exedev/MathDyad
python runs/erdos667_wave6i_verify.py

Observed result:

PASS symbolic LLL exponents, recurrence, and strict-jump arithmetic
PASS pure labelled enumeration: H(n;4,3)={1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2} for 1<=n<=6
...
PASS nauty census and fresh witness checks through n=15
PASS convolution gives H(n;4,3)=[1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]
ALL CHECKS PASSED

Environment: Python 3.12.3, Debian nauty 2.8.8+ds-5. SHA-256 of the verifier at the time of this report:

3882bfe693dbde3d330ec52c3d14cb6c6dddb7b90e64d4e300ab4c777a4550dd

9. Exact wall

The output does not settle full strict monotonicity.

The neighborhood recurrence and Local-Lemma upper bound explain exactly where this machinery stops. At

the lower bound is \(1/(p-s+1)\). At the immediately preceding \(q_s-1\), (3.1) is strictly smaller only when \(p-s+1<3\), precisely the two jumps proved in §5. When \(p-s+1=3\), the two exponents are equal; earlier than that, the upper bound is weaker. No rearrangement of these same two inequalities can produce the missing power gap. (a)

The first concrete missing lemma already occurs for \(p=4\):

or construct a sequence of such graphs with

\(\alpha(F)=n^{1/2+o(1)}\). Either result decides the remaining \(p=4\) jump. Current arguments audited here only give the exponent interval \([1/2,2/3]\). (a)/(b)

Finite computation cannot supply the required uniform power saving. The full nauty check already passes through 2,455,693 isomorphism classes at \(n=15\) in about 16 seconds on this VM; extending a few orders is feasible with increasing cost, but no finite order can prove either asymptotic alternative without an additional stability/extension theorem. I therefore did not spend the CPU budget on larger, mathematically non-closing censuses. (d)

PARTIAL: Proved the uniform bound c(p,q) <= (p-2)/(C(p,2)-q), the neighborhood recurrence, and two infinite families of strict adjacent jumps; reduced the remaining p=4 jump exactly to the independence exponent of {C3,C4}-free graphs and verified the finite table through n=15.