Erdős problem 1033 — live-page audit and exact small cases

Access date: 2026-07-28 UTC.

Claim labels used below:

• (a) elementary-rigorous
• (b) rigorous modulo a named theorem
• (c) plausible/structural-unverified
• (d) computational-only

0. Mandatory live-page gate

I fetched both the live problem page and its discussion thread with a Bright Data browser, not datacenter curl. I also inspected the rendered status/marker table, followed the bibliography controls, and saved full-page screenshots during the run.

Verbatim live statement

Let \(h(n)\) be such that every graph on \(n\) vertices with \(>n^2/4\) many edges contains a triangle whose vertices have degrees summing to at least \(h(n)\). Estimate \(h(n)\). In particular, is it true that \[ > h(n)\geq (2(\sqrt{3}-1)-o(1))n? > \]

The citation header is #1033: [Er82e,p.71][Er93,p.344].

Current status and all activity markers

The rendered page says:

• Status: OPEN.
• Last main-page edit: 03 April 2026.
• Comments: 5.
• Claimed proofs: 0.
• Likes this problem: None.
• Interested in collaborating: None.
• Currently working on this problem: None.
• Looks difficult: JohanLand.
• Looks tractable: None.
• Results could be formalisable: None.
• Working on formalising the results: None.

Thus neither the claimed-proof nor current-worker stop condition fires. The comments do say that the highlighted proposed asymptotic lower bound has been disproved, but they explicitly distinguish that subquestion from the still-open request to estimate \(h(n)\).

All five comments

In oldest-first order:

1. rickyc, 16:51 on 27 Jun 2026: links a public ChatGPT conversation and

says GPT-5.5 Pro claims an explicit construction disproving the proposed lower bound.

1. JohanLand, 19:52 on 26 Jul 2026: says the construction appears to hold

up, so the displayed lower-bound conjecture is false; records \[ \frac{21}{16}n\leq h(n)\leq 1.46393n+O(1), \] and stresses that this does not resolve the estimation problem.

1. rickyc, 21:52 on 26 Jul 2026: expects other constructions may improve

the bound and notes that there is no candidate for the true constant.

1. Wouter CvB, 14:38 on 27 Jul 2026: links

a three-page construction note optimizing the same five-part butterfly blow-up to \(1.463877226\ldots\), a root of a degree-seven polynomial. The comment says connected support graphs on at most seven vertices were tried; the PDF says, less precisely, that its experiments included all graphs on at most eight vertices. Neither exhaustive-search assertion comes with code or a certificate, so I do not use it as a theorem.

1. rickyc, 15:11 on 27 Jul 2026: says GPT confirms the refinement and

suggests that further small constant improvements may be meaningful.

The page itself warns that comments are unverified. The linked PDF downloaded in this run had SHA-256 f42a5ecece0979af67806fc1f5d8d7e9d47dfc441b0a95e78398c6e90af487fb.

1. Ground truth and literature check

The main page records

It attributes the upper construction to Erdős--Laskar and the lower bound to Fan. It also explains the classical upper construction: start with a complete bipartite graph with parts \(k+l=n\), add \(\lfloor n^2/4\rfloor+1-kl\) triangle-free, nearly regular edges inside the \(k\)-part, and optimize at \(k/n=1/\sqrt3\).

I checked the following primary records rather than relying on paper titles from secondary search results:

• The Rényi Institute scan of Erdős,

Some of my favourite problems which recently have been solved, exists. Page 71 discusses the triangle degree-sum problem. (a: bibliographic/content check)

• The publisher record for Erdős,

Some of my favorite solved and unsolved problems in graph theory, verifies Quaestiones Mathematicae 16 (1993), 333–350, DOI 10.1080/16073606.1993.9631741. Page 344 is paywalled, so I verified the record but did not pretend to inspect that page.

• The Erdős archive scan of Erdős--Laskar,

A note on the size of a chordal subgraph, exists as Congressus Numerantium 48 (1985), 81–86.

• Fan's publisher record,

Degree sum for a triangle in a graph, exists as Journal of Graph Theory 12 (1988), 249–263. Its abstract defines the two-parameter extremal function \(f(n,e)\), states \(f(n,e)\geq 21e/(4n)\), and records the relevant upper construction.

• Bollobás--Nikiforov,

The sum of degrees in cliques, is genuinely arXiv:math/0410218 and later appeared in Electronic Journal of Combinatorics 12 (2005), N21. Its near-\(t_r(n)\) theorem is the higher-density general result quoted on the page; it does not settle the near-Mantel regime here.

Exact-title, formula, DOI, Erdős-archive, and arXiv searches found no later primary paper specifically improving Fan's near-\(n^2/4\) lower bound. This is an honest search miss, not a claim that no such paper exists.

The linked July 2026 butterfly note sets

and uses the root

The companion checker independently brackets a sign-changing root, evaluates all displayed density formulas at 80-decimal precision, verifies that the five part weights sum to one, that both partial densities lie in \((0,1)\), that the limiting edge density is exactly \(1/4\) to the computed precision, and that the two possible triangle types both have normalized degree sum \(y_0\). That is an arithmetic/support check (d), not certification of the PDF's claim that this is the global butterfly optimum.

2. A finite reduction

For a graph \(G\), define

Equivalently,

Let

Fixed-edge lemma. (b, modulo Mantel's theorem)

Proof. A graph with at least \(m_0(n)\) edges has a spanning subgraph \(H\) with exactly \(m_0(n)\) edges (take \(H=G\) in the equality case). Every triangle of \(H\) is a triangle of \(G\), and \(d_H(v)\leq d_G(v)\) for every vertex, so \(s(H)\leq s(G)\). Mantel's theorem ensures that \(H\) has a triangle. The reverse inequality is immediate because every graph with \(m_0(n)\) edges is allowed. \(\square\)

This reduction makes each fixed \(n\) a finite, exact computation.

3. Exact computation for \(3\leq n\leq10\)

Method

For each \(n\), I generated every nonisomorphic simple graph with exactly \(m_0(n)\) edges using nauty-geng 2.8.8. A separately written graph6 decoder then:

1. reconstructed the adjacency bitsets;
2. recomputed the edge count and every vertex degree;
3. enumerated every triangle;
4. evaluated \(s(G)\); and
5. retained the minimum and the number of isomorphism classes attaining it.

The official nauty/Traces page documents geng as a generator of nonisomorphic graphs. Reliance on that software is why the equality table is labelled (d).

As an independent cross-check, the verifier also enumerates all labeled edge subsets from scratch for \(3\leq n\leq7\), without nauty. The largest such second search checks all \(\binom{21}{13}=203{,}490\) labeled graphs. Both implementations agree.

Result

Exact finite table (d):

Here “add \(H\) in the \(a\)-side” means start with \(K_{a,b}\) and insert the edges of \(H\) among those \(a\) vertices. The edge counts and maximum triangle degree sums of all eight displayed certificates are direct finite checks (a). The matching lower bounds are the exhaustive computation (d).

The independent labeled enumeration produced:

No asymptotic conclusion is drawn from this finite list.

4. Reproduction and independent checker

The complete checker is runs/erdos1033_wave8a_reverify.py, SHA-256 593fd9d88aae05c3ebad60638c3d72e6c11df8b8872d7fbe9aa2f3cdb1fbc577.

Run:

python runs/erdos1033_wave8a_reverify.py

On this VM (Python 3.12.3, nauty 2.8.8+ds-5), the full run took about 26 seconds and ended:

nauty n=10: m=26, h=16, graphs=828728, minimizers=259
nauty enumeration: PASS
independent enumeration agreement: PASS (n=3..7)
ALL CHECKS PASSED

The nauty-independent portion can be run with:

python runs/erdos1033_wave8a_reverify.py --skip-nauty

It verifies all explicit certificates, the posted butterfly arithmetic, and the complete labeled searches through \(n=7\).

The core scoring rule is deliberately simple:

degrees = tuple(mask.bit_count() for mask in adj)
maximum = -1
for a in range(n - 2):
    for b in range(a + 1, n - 1):
        if not ((adj[a] >> b) & 1):
            continue
        common = adj[a] & adj[b] & ~((1 << (b + 1)) - 1)
        while common:
            bit = common & -common
            c = bit.bit_length() - 1
            maximum = max(maximum, degrees[a] + degrees[b] + degrees[c])
            common ^= bit

The standalone file contains the graph generator invocation, graph6 decoder, direct labeled enumerator, certificate construction, assertions, and high-precision butterfly check. Expected values appear only as post-computation assertions; the searches recompute each result before making that comparison.

5. What remains and the precise asymptotic wall

The best live construction claim is currently approximately

whereas Fan gives

The exact finite table does not bridge this uniform gap.

A natural graphon formulation has degree function

and asks to control the essential supremum of

over triangle-support triples. The missing lemma is a uniform structural or lower-bound theorem showing that every graph (or limiting graphon) of edge density just above \(1/4\) must contain such a triple with degree sum at least a proposed constant. Ordinary Mantel stability does not supply this: the objective depends on where triangle-support edges are positive and is not continuous under the usual coarse convergence when small edge densities are turned on or off.

Numerical optimization of a fixed finite support graph cannot repair that uniformity gap. It is a nonconvex search, support changes are discontinuous, and checking support graphs on at most seven or eight vertices does not reduce arbitrary graphs or graphons to that finite list. A proof would need either:

1. a stability/classification theorem reducing all near-extremizers to a

certified finite family of weighted templates; or

1. a new global inequality improving Fan's \(21/16\) lower constant.

I found neither lemma. Therefore this report claims the exact small cases, not a solution of the asymptotic problem and not global optimality of the butterfly construction.

PARTIAL: Exhaustive computation gives h(3..10) = 6,8,9,10,12,13,14,16 with explicit certificates and an independent labeled cross-check through n=7; the asymptotic constant remains open.