2014/05/18 by Xiu Baoxin, Baoxin, Xiu, Changjun Fan +3
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1405.4535
arxiv created 2014/05/18 · arxiv updated 2014/05/20
A set \ai | 1≤ i ≤ k\ of non-negative integers is a Golomb ruler if differences ai-aj, for any i ≠ j, are all distinct. A set of I disjoint Golomb rulers (DGR) each being a J-subset of \1,2,⋯, n\ is called an (I,J,n)-DGR. Let H(I, J) be the least positive n such that there is an (I,J,n)-DGR. In this paper, we propose a series of conjectures on the constructions and structures of DGR. The main conjecture states that if A is any set of positive integers such that |A| = H(I, J), then there are I disjoint Golomb rulers, each being a J-subset of A, which generalizes the conjecture proposed by Komlós, Sulyok and Szemerédi in 1975 on the special case I = 1. These conjectures are computationally verified for some values of I and J through modest computation. Eighteen exact values of H(I,J) and ten upper bounds on H(I,J) are obtained by computer search for 7 ≤ I ≤ 13 and 10 ≤ J ≤ 13. Moveover for I > 13 and 10 ≤ J ≤ 13, H(I,J)=IJ are determined without difficulty.