Many interesting infinite graphs are given by taking a ground set $X$ and placing edges between pairs of vertices in $X$ at certain prescribed distances. The Hadwiger-Nelson problem is to determine the chromatic number of the unit-distance graph over the plane. As a modified version of this problem, Eggleton, Erdős, and Skilton defined a distance graph to be a graph $G(S)$ with the integers as a vertex set and edges between pairs of vertices at distance within some set $S$. A significant research effort has gone into determining the chromatic number of these graphs. One tool to study the chromatic number is the fractional chromatic number.
Instead of directly studying the fractional chromatic number, one can study the independence ratio of a distance graph. That is, let $A$ be an independent set in a distance graph $G(S)$ generated by a distance set $S$. Then, the density of $A$ is $\delta(A) = \limsup_{N\to\infty} \frac{|A\cap [-N,N]|}{2N+1}$. The independence ratio of $G(S)$ is
The independence ratio is bounded from below by periodic independent sets and is bounded above by discharging arguments. It is determined that for every finite set $S$ there is a periodic independent set of density $\overline{\alpha}(S)$, and the minimum period of such a set is bounded by a function of the maximum element in $S$. Several exact values of $\overline{\alpha}(S)$ are determined, especially for sets of size three, and several conjectures are stated.
Web Version ArXiv Version
Web Version ArXiv Version Official Version Research Project
distance_cliquer computes the independence ratio of a distance graph, given the set $S$. Simply download, unzip, type make, then run the program with the following command structure:
It will output multiple statistics, but the important pair are the variables DALPHA_INT_* and DALPHA_CYC_*, which are upper and lower bounds, respectively, on $\overline{\alpha}(S)$. To limit the run time, use the parameters -k [MAXRUNTIME] -N [MAXSIZE] to limit it to running no more than MAXRUNTIME seconds and to compute the independence number for circulant graphs $G(n,S)$ for $n$ at most MAXSIZE.
cliquer (by Niskanen and Östergârd) computes the clique number of a given graph. The algorithm for distance_cliquer is based on the algorithm in cliquer.
We computed the values of $\overline{\alpha}(S)$ for many sets $S$. These values can be found in the Table of Independence Ratios.
For the extremal sets and exact performance data, see the following data files. The values DALPHA_CYC_S_* provide the best-computed lower bound on $\overline{\alpha}(S)$ while the values DALPHA_INT_S_* provide the best-computed upper bound on $\overline{\alpha}(S)$.
- alldalphas.txt contains all values of computed upper and lower bounds on $\overline{\alpha}(S)$.
- g3.txt contains all data for generator sets of size 3.
- g4.txt contains all data for generator sets of size 4. (WARNING: Large!)
- g5.txt contains all data for generator sets of size 5. (WARNING: Large!)
- allstats.txt contains all data for computed generator sets. (WARNING: Very Large!)
R.B. Eggleton, P. Erdős, D.K. Skilton, Colouring the real line, J. Combin. Theory B 39 (1985) 86-100.
G. Gao and X. Zhu, Star extremal graphs and the lexicographic product, Discrete Math. 165/166 (1996) 147-156.
X. Zhu, Circular Chromatic Number of Distance Graphs with Distance Sets of Cardinality 3, Journal of Graph Theory 41 (2002) 195-207.
Finding cliques and independent sets in circulant graphs, Computational Combinatorics (Blog).
Slides