On Disjoint Golomb Rulers

Abstract

A set $\{a_i|1\le i\le k\}$ of non-negative integers is a Golomb ruler if differences $a_i-a_j$, for any $i\ne j$, are all distinct. A set of $I$ disjoint Golomb rulers (DGR) each being a $J$-subset of $\{1,2,\cdots ,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\le I\le 13$ and $10\le J\le 13$. Moveover for $I>13$ and $10\le J\le 13$, $H(I,J)=IJ$ are determined without difficulty.