← All problems

Erdős Problem #272 — Families with arithmetic progression intersections

45 years old · traced to

For an integer N≥1N\geq 1, write [N]={1,2,…,N}[N]=\{1,2,\ldots,N\}. An arithmetic progression in [N][N] means a set of the form

{a+kd:0≤k≤r},\{a+kd:0\leq k\leq r\},

where a,d,ra,d,r are integers, d≥1d\geq1, r≥0r\geq0, and every term belongs to [N][N]; in particular, a singleton is an arithmetic progression. Let tmax⁡(N)t_{\max}(N) be the largest integer tt for which there is a family of distinct subsets A1,…,At⊆[N]A_1,\ldots,A_t\subseteq[N] such that

Ai∩Aj is a non-empty arithmetic progression whenever 1≤i<j≤t.A_i\cap A_j\text{ is a non-empty arithmetic progression whenever }1\leq i<j\leq t.

The question is to determine tmax⁡(N)t_{\max}(N). Distinctness is required by the family formulation of the problem; without it, repeating one admissible set would make the maximum unbounded. Erdős Problems #272 Szabó, Intersection properties of subsets of integers

Background

This problem belongs to extremal set theory, but unlike classical intersection questions that constrain only the size of pairwise intersections, it imposes structure on the intersection itself: it must be an arithmetic progression. Graham, Simonovits and Sós studied the related version in which empty intersections are allowed. They determined its exact maximum, (N3)+(N2)+(N1)+1\binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1. Requiring intersections to be non-empty changes the extremal behavior and leads to the present problem. Erdős Problems #272 Szabó, Intersection properties of subsets of integers Graham, Simonovits and Sós (1980)

A natural construction takes all arithmetic progressions containing one fixed integer, while another takes all subsets of size at most three containing a fixed integer. The latter construction already gives (N2)+1\binom{N}{2}+1 sets, and Szabó’s later improvement shows that this simple common-point construction is not always extremal. Thus the problem is not merely to count progressions through a point; it also asks how non-progression sets can be incorporated while preserving the required pairwise intersections. Erdős Problems #272 Szabó, Intersection properties of subsets of integers

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.