On a Problem of Erdős, Herzog and Schönheim

Abstract

Let $p_1,p_2,...,p_n$ be distinct primes. In 1970, Erd\H os, Herzog and Schönheim proved that if $\mathcal{D}$ is a set of divisors of $N=p_1^{{\alpha }_1}...p_n^{{\alpha }_n}$, ${\alpha }_1\ge {\alpha }_2\ge ...\ge {\alpha }_n$, no two members of the set being coprime and if no additional member may be included in $\mathcal{D}$ without contradicting this requirement then $|\mathcal{D}|\ge {\alpha }_n{\prod }_{i=1}^{n-1}({\alpha }_i+1)$. They asked to determine all sets $\mathcal{D}$ such that the equality holds. In this paper we solve this problem. We also pose several open problems for further research.

12 pages