← All problems

Erdős Problem #534 — Largest pairwise non-coprime family containing its endpoint

46 years old · traced to

For a positive integer NN, let [N]={1,…,N}[N]=\{1,\ldots,N\}. Determine the maximum cardinality of a set A⊆[N]A\subseteq[N] satisfying

N∈A,gcd⁡(a,b)>1for every pair of distinct a,b∈A.N\in A, \qquad \gcd(a,b)>1\quad\text{for every pair of distinct }a,b\in A.

For N=1N=1 the maximum is 11, attained by A={1}A=\{1\}; for N≥2N\ge 2 this is the endpoint-containing pairwise non-coprime family problem. Erdős Problem #534

Background

Erdős and Graham posed the endpoint problem in their work on combinatorial number theory; Erdős revisited it in his 1980 survey. An initial conjecture proposed that the maximum was one of two natural quantities, but Ahlswede and Khachatrian found a counterexample and informed Erdős in 1992. Erdős then proposed a more refined formula, indexed by the initial segments of the prime factors of NN. Ahlswede–Khachatrian (1996) Erdős (1980)

References

P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

Source: P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

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.