ERDŐS/DAILY ▸

← back to the ledger

ERDőS #600 · PARTIAL

Erdős problem #600 — wave w001

Date: 2026-07-28 (UTC)

Claim labels

Step 0: authoritative live-page check

(d) I fetched the live page through the Bright Data browser path, not datacenter curl: Erdős problem #600, accessed 2026-07-28. It displayed:

Thus none of the mandatory stop conditions applied.

Verbatim current statement

The following is copied verbatim from the page's “View the LaTeX source” view:

Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that\[e(n,r+1)-e(n,r)\to \infty\]as $n\to \infty$? Is it true that\[\frac{e(n,r+1)}{e(n,r)}\to 1\]as $n\to \infty$?

Listed known result and comment

(b) The page states: “Ruzsa and Szemerédi [RuSz78] proved that \(e(n,r)=o(n^2)\) for any fixed \(r\).” Its bibliography identifies:

I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II (1978), 939–945, MR 519318.

(d) I read the entire sole discussion comment. It:

  1. introduces the counterexample extremal function \(F_r(n)=e(n,r)-1\);
  2. observes that a nonedge of codegree 1 or 2 can be added to a locally linear \(F_2\)-admissible graph to produce an \(F_3\)-admissible graph;
  3. describes the \(t\)-blow-up of a locally linear graph and deletion of two diagonal matchings from each \(K_{t,t,t}\) block for \(t\geq3\);
  4. notes the exceptional \(K_{2,2,2}\) behavior;
  5. explicitly says these observations do not settle either question and includes an AI-assistance disclosure.

The insertion and blow-up observations are re-proved and independently checked below; I do not treat the comment itself as an authoritative result.

Normalization

For an edge \(uv\), write

\[ b_G(uv)=|N_G(u)\cap N_G(v)|, \]

the number of triangles containing \(uv\), and define

\[ F_r(n)=\max\{|E(G)|:\ |V(G)|=n,\quad 1\leq b_G(e)\leq r-1\text{ for every }e\in E(G)\}. \]

(a) Then

\[ \boxed{e(n,r)=F_r(n)+1.} \]

Indeed, \(F_r(n)\) is exactly the largest size of a graph that satisfies the “every edge is triangular” hypothesis but avoids an edge in \(r\) triangles. This also handles the vacuous range: if \(r\geq n-1\), then \(F_r(n)=\binom n2\) and \(e(n,r)=\binom n2+1\).

Literature verification and search result

(d) The original source exists and contains this problem: P. Erdős, Some problems on finite and infinite graphs, Contemporary Mathematics 65 (1987), 223–228, MR 891250, author-archive PDF. On pp. 226–227 Erdős defines the density version first, then \(e(n,r)\), records the Ruzsa–Szemerédi bounds, and proposes the same two successive-\(r\) asymptotics.

(b) A modern primary source that explicitly discusses the related density problem and the Ruzsa–Szemerédi theorem is J. Fox and P.-S. Loh, On a problem of Erdős and Rothschild on edges in triangles, Combinatorica 32 (2012), 619–628, arXiv:1106.0290, DOI 10.1007/s00493-012-2844-3. It proves, for the density function \(h(n,c)\) and fixed \(c<1/4\), the upper bound \(h(n,c)=n^{O(1/\log\log n)}\). That is relevant to linked problem #80, but it does not compare \(e(n,r+1)\) with \(e(n,r)\) for fixed \(r\).

(c) I searched the exact displayed expressions, variants of the definition, “locally linear graph”, “unique triangle per edge”, “booksize”, the original-paper citation graph, and the cited Ruzsa–Szemerédi title. I found the tracker, the original paper, work on the density problem, and work on Ruzsa–Szemerédi graphs, but no primary source directly resolving either successive-\(r\) limit. This is a reported search miss, not evidence that no such paper exists.

Independent recovery of the listed \(o(n^2)\) result

(b) The fixed-\(r\) upper bound follows quickly from the triangle removal lemma. If \(G\) is \(F_r\)-admissible, with \(m\) edges and \(T\) triangles, then

\[ \frac m3\leq T\leq \frac{(r-1)m}{3}=O_r(n^2)=o(n^3). \]

The triangle removal lemma therefore supplies a set \(S\) of \(o(n^2)\) edges meeting every triangle. Each edge of \(S\) meets at most \(r-1\) triangles, while \(T\geq m/3\), so

\[ (r-1)|S|\geq T\geq m/3. \]

Consequently \(m=o(n^2)\), hence \(F_r(n)=o(n^2)\) and \(e(n,r)=o(n^2)\). The only non-elementary input here is the triangle removal lemma.

Result 1: exact small values through \(n=10\)

(d) The exhaustive computation gives the following exact threshold values. Columns are \(e(n,r)\), not \(F_r(n)\).

| \(n\) | \(r=2\) | \(r=3\) | \(r=4\) | \(r=5\) | \(r=6\) | \(r=7\) | \(r=8\) | \(r=9\) | |---:|---:|---:|---:|---:|---:|---:|---:|---:| | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | | 4 | 4 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | | 5 | 7 | 9 | 11 | 11 | 11 | 11 | 11 | 11 | | 6 | 7 | 13 | 13 | 16 | 16 | 16 | 16 | 16 | | 7 | 10 | 16 | 17 | 19 | 22 | 22 | 22 | 22 | | 8 | 13 | 19 | 22 | 25 | 25 | 29 | 29 | 29 | | 9 | 19 | 22 | 28 | 29 | 31 | 33 | 37 | 37 | | 10 | 19 | 27 | 32 | 34 | 37 | 41 | 41 | 46 |

Equivalently, the computed \(F_r(10)\) row for \(r=2,\ldots,9\) is

\[ (18,26,31,33,36,40,40,45). \]

(d) For the first two successive levels, the computed gaps for \(n=3,\ldots,10\) are

\[ \begin{aligned} e(n,3)-e(n,2)&=(0,3,2,6,6,6,3,8),\\ e(n,4)-e(n,3)&=(0,0,2,0,1,3,6,5). \end{aligned} \]

These finite sequences are nonmonotone and are not evidence for a limit by themselves.

Exhaustive method and exactness boundary

(a) An admissible graph has no vertex of degree 1: its incident edge could not lie in a triangle. Thus every vertex is either isolated or has degree at least 2.

(d) For each \(3\leq n\leq10\), nauty-geng -d2 n generated one representative of every isomorphism class with minimum degree at least 2. Every record was decoded into bitset neighborhoods; for every present edge \(uv\), the checker recomputed \(\operatorname{popcount}(N(u)\cap N(v))\). Graphs with isolated vertices were covered exactly by inheriting the maxima at smaller orders.

(d) The largest pass, \(n=10\), generated 9,808,968 isomorphism classes; 2,954,334 had every edge in at least one triangle. The full vectorized pass through \(n=10\) took 6.92 seconds on this VM.

(d) A second implementation independently enumerated all \(2^{\binom n2}\) labeled graphs through \(n=7\), using scalar integer masks and no graph6, nauty, NetworkX, or vectorized predicate. Its tables agree entry-for-entry. It checked all \(2^{21}=2{,}097{,}152\) labeled graphs at \(n=7\).

(d) Lower-bound witnesses are retained as graph6 certificates and decoded by a separate scalar parser. For the \(n=10\) row, witnesses found by the run include:

| \(r\) | graph6 certificate | |---:|:---| | 2 | HEhbtjK on 9 vertices, plus one isolated vertex | | 3 | IEhbtj{ro | | 4 | ICxvF~}~_ | | 5 | I?~vf~}~_ | | 6 | IFzvvZ~~o | | 7 | I]~v~z~~o | | 8 | I]~v~z}~w | | 9 | I~~~~~~~w |

The checker verifies each certificate's edge count and every edge booksize from scratch.

Result 2: exact closed forms in two near-complete regimes

(a) Theorem. For every \(n\geq5\),

\[ \boxed{e(n,n-2)=\binom n2-\left\lfloor\frac n2\right\rfloor+1} \]

and

\[ \boxed{ e(n,n-3)= \begin{cases} \binom n2-\dfrac n2+1,&n\text{ even},\\[2mm] \binom n2-\dfrac{n+3}{2}+1,&n\text{ odd}. \end{cases}} \]

These formulas agree with every overlapping entry of the exhaustive table.

Complement reduction

Let \(H=\overline G\). If \(uv\in E(G)\), equivalently \(uv\notin E(H)\), then

\[ \boxed{b_G(uv)=n-2-|N_H(u)\cup N_H(v)|.}\tag{1} \]

(a) More generally, for \(r=n-s\), the conditions

\[ 1\leq b_G(uv)\leq r-1=n-s-1 \]

are exactly

\[ s-1\leq |N_H(u)\cup N_H(v)|\leq n-3 \quad\text{for every nonedge }uv\text{ of }H. \tag{2} \]

Thus the near-complete problem becomes a sparse-complement neighborhood-union problem.

Proof for \(r=n-2\)

(a) Here (2) requires \(|N_H(u)\cup N_H(v)|\geq1\) for every nonedge \(uv\) of \(H\). Therefore \(H\) has at most one isolated vertex. At least \(n-1\) vertices must be incident with an \(H\)-edge, and each edge covers at most two of them, so

\[ |E(H)|\geq \left\lceil\frac{n-1}{2}\right\rceil =\left\lfloor\frac n2\right\rfloor. \]

Equation (1) gives the corresponding upper bound on \(|E(G)|\).

(a) Equality is attained when \(H\) is a maximum matching, covering all vertices if \(n\) is even and all but one if \(n\) is odd. Every \(G\)-edge then has booksize \(n-4\), or \(n-3\) when one endpoint is the unmatched vertex. For \(n\geq5\), these values lie in \([1,n-3]\). Hence

\[ F_{n-2}(n)=\binom n2-\left\lfloor\frac n2\right\rfloor, \]

which proves the first formula after adding 1.

Proof for \(r=n-3\)

(a) Now every nonedge \(uv\) of \(H\) must satisfy

\[ |N_H(u)\cup N_H(v)|\geq2. \tag{3} \]

If \(n\) is even, (3) in particular prohibits two isolated vertices, so the same edge-cover count gives \(|E(H)|\geq n/2\). A perfect matching attains equality. Its complement has every edge in exactly \(n-4\) triangles, which is positive for even \(n\geq6\).

Suppose \(n\) is odd. If \(H\) has an isolated vertex \(z\), applying (3) to \(zv\) forces \(d_H(v)\geq2\) for every \(v\neq z\). Hence \(|E(H)|\geq n-1\geq(n+3)/2\).

If \(H\) has no isolated vertex, then \(\delta(H)\geq1\). Were \(|E(H)|=(n+1)/2\), the degree excess would be

\[ \sum_v(d_H(v)-1)=2|E(H)|-n=1. \]

Thus exactly one vertex would have degree 2 and every other vertex degree 1. Its two neighbors would be nonadjacent degree-1 vertices with the same singleton neighborhood, contradicting (3). Therefore

\[ |E(H)|\geq\frac{n+3}{2}. \]

(a) For odd \(n\geq7\), equality is attained by taking \(H\) to be a disjoint \(K_3\) and \((n-3)/2\) copies of \(K_2\). A nonedge joins different components, so its neighborhood union has size 2 or 3; by (1), every \(G\)-edge has booksize \(n-4\) or \(n-5\), both in \([1,n-4]\). For \(n=5\), take \(H\) to be an isolated vertex plus a \(C_4\); its complement is two triangles sharing one vertex and every edge has booksize 1. This proves the odd case and the theorem.

Re-verification of the discussion comment's finite mechanisms

Single-edge insertion

(a) Let \(G\) have every edge in exactly one triangle, and let \(uv\) be a nonedge with \(1\leq|N(u)\cap N(v)|\leq2\). In \(G+uv\), the new edge has booksize 1 or 2. For each common neighbor \(w\), only the two old edges \(uw\) and \(vw\) gain the new triangle \(uvw\), so they rise from booksize 1 to 2. Every other old edge is unchanged. Therefore \(G+uv\) is \(F_3\)-admissible.

(d) The independent labeled enumerator universally checked this implication for every locally linear labeled graph through \(n=7\) and every eligible nonedge.

Blow-up gadget

(a) Let \(L\) be locally linear and replace every vertex by \(t\) independent clones and every edge by a \(K_{t,t}\). Every triangle in the blow-up projects to a triangle of \(L\), and every base edge belongs to a unique base triangle, so each blow-up edge has booksize exactly \(t\).

Inside a base \(K_{t,t,t}\), label the three parts \(A=(a_i)\), \(B=(b_i)\), \(C=(c_i)\). Delete the two diagonal matchings

\[ \{a_ib_i:1\leq i\leq t\} \quad\text{and}\quad \{a_ic_i:1\leq i\leq t\}. \]

Every retained \(A\)-\(B\) or \(A\)-\(C\) edge then has booksize \(t-1\); a retained \(b_jc_k\) has booksize \(t-1\) if \(j=k\) and \(t-2\) otherwise. For \(t\geq3\), every retained edge remains triangular and the block retains

\[ 3t^2-2t \]

of its \(3t^2\) edges.

(d) The checker constructs and validates these gadgets for \(3\leq t\leq12\). It also exhausts all \(2^{12}\) subgraphs of \(K_{2,2,2}\) and finds that the exact maximum locally linear subgraph has 6 edges.

What remains, precisely

(c) Neither closed form above addresses the original quantifiers, because there \(r\) is fixed while \(n\to\infty\); the formulas instead have \(r=n-O(1)\). The exact table stops at \(n=10\). Thus no uniformity or finiteness step closes either asymptotic question.

A concrete missing packing lemma for the first limit

For \(r=2\), let \(G_n\) be an \(F_2(n)\)-extremal locally linear graph. Call a set \(S\) of nonedges compatible if every edge of \(G_n+S\) has booksize 1 or 2.

(a) If one could prove that some \(F_2(n)\)-extremal \(G_n\) has a compatible set \(S_n\) with \(|S_n|\to\infty\), then

\[ F_3(n)\geq F_2(n)+|S_n| \]

and hence \(e(n,3)-e(n,2)\to\infty\).

(c) The exact missing ingredient is therefore not merely the existence of one nonedge of codegree 1 or 2. It is a growing packing of such insertions subject to the local capacity constraints: an old book of size 1 may gain at most one page, and every new edge must finish with at most two pages. The page comment proves only the one-insertion implication.

For general fixed \(r\), the analogous missing lemma asks for \(\omega(1)\) compatible local modifications of an \(F_r(n)\)-extremizer without creating an \((r+1)\)-page book.

A concrete missing extraction theorem for the ratio

(a) It would suffice to prove that every \(F_{r+1}(n)\)-extremizer contains, on the same vertex set, an \(F_r\)-admissible subgraph with

\[ F_{r+1}(n)-o(F_{r+1}(n)) \]

edges. This would give \(F_r(n)\geq(1-o(1))F_{r+1}(n)\), and monotonicity would force \(e(n,r+1)/e(n,r)\to1\).

(c) No such near-lossless extraction theorem was located or proved. Triangle removal only yields \(F_r(n)=o(n^2)\) separately for each \(r\); it gives no comparison sharp enough to control a successive ratio.

Computation wall

(c) Straight isomorphism-class enumeration ceases to be a sensible attack very quickly. The \(n=10\) min-degree-two pass already processed 9.81 million classes. There are about 1.019 billion unlabeled graphs at \(n=11\) before the min-degree filter and about \(1.65\times10^{11}\) at \(n=12\). Extrapolating the measured checker rate puts a comparable \(n=11\) pass at roughly \(0.2\)–\(0.5\) core-hours and \(n=12\) at tens of core-hours, before any structural packing optimization. I did not run either.

Reproduction

The standalone checker is:

runs/erdos600_wavew001_reverify.py

Run:

python runs/erdos600_wavew001_reverify.py

It uses Python 3.12.3, NumPy 2.4.4, and nauty 2.8.8 (/bin/nauty-geng). Its successful full run took 17.95 seconds and ended with:

ALL CHECKS PASSED

SHA-256 at the time of this report:

a77e8dc4787c7beabadbd2d713484fed88cc0f2d775fdf1c5a49338565ac12d6

PARTIAL: exact e(n,r) is verified through n=10 and closed forms are proved for r=n-2 and r=n-3, but both fixed-r asymptotic questions remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger