Skip to main content
replaced "first known bound" to "first good bound"
Source Link
Anurag
  • 1.2k
  • 1
  • 20
  • 29

Bannai, Bannai and Stanton proved that $f_d(k) \leq {d + k \choose k}$ in 1983. See: http://link.springer.com/article/10.1007%2FBF02579288

I don't think this bound has been improved in general. It is certainly not tight for every value of the parameters.

The first knowngood bound for this function was for $k = 2$, as given by Larman Rogers and Seidel in 1977, "On Two-Distance Sets in Euclidean Space". They proved that $f_d(2) \leq (d+1)(d+4)/2$ using a nice dimension argument. This bound was later improved by Blokhuis in 1981 to $(d+1)(d+2)/2 = {d+2 \choose 2}$, which was later generalised to $f_d(k) = {d+k \choose k}$.

This problem is also discussed in the manuscript "Linear Algebra Methods in Combinatorics" by Babai and Frankl, where you can find some of these proofs.

Bannai, Bannai and Stanton proved that $f_d(k) \leq {d + k \choose k}$ in 1983. See: http://link.springer.com/article/10.1007%2FBF02579288

I don't think this bound has been improved in general. It is certainly not tight for every value of the parameters.

The first known bound for this function was for $k = 2$, as given by Larman Rogers and Seidel in 1977, "On Two-Distance Sets in Euclidean Space". They proved that $f_d(2) \leq (d+1)(d+4)/2$ using a nice dimension argument. This bound was later improved by Blokhuis in 1981 to $(d+1)(d+2)/2 = {d+2 \choose 2}$, which was later generalised to $f_d(k) = {d+k \choose k}$.

This problem is also discussed in the manuscript "Linear Algebra Methods in Combinatorics" by Babai and Frankl, where you can find some of these proofs.

Bannai, Bannai and Stanton proved that $f_d(k) \leq {d + k \choose k}$ in 1983. See: http://link.springer.com/article/10.1007%2FBF02579288

I don't think this bound has been improved in general. It is certainly not tight for every value of the parameters.

The first good bound for this function was for $k = 2$, as given by Larman Rogers and Seidel in 1977, "On Two-Distance Sets in Euclidean Space". They proved that $f_d(2) \leq (d+1)(d+4)/2$ using a nice dimension argument. This bound was later improved by Blokhuis in 1981 to $(d+1)(d+2)/2 = {d+2 \choose 2}$, which was later generalised to $f_d(k) = {d+k \choose k}$.

This problem is also discussed in the manuscript "Linear Algebra Methods in Combinatorics" by Babai and Frankl, where you can find some of these proofs.

Source Link
Anurag
  • 1.2k
  • 1
  • 20
  • 29

Bannai, Bannai and Stanton proved that $f_d(k) \leq {d + k \choose k}$ in 1983. See: http://link.springer.com/article/10.1007%2FBF02579288

I don't think this bound has been improved in general. It is certainly not tight for every value of the parameters.

The first known bound for this function was for $k = 2$, as given by Larman Rogers and Seidel in 1977, "On Two-Distance Sets in Euclidean Space". They proved that $f_d(2) \leq (d+1)(d+4)/2$ using a nice dimension argument. This bound was later improved by Blokhuis in 1981 to $(d+1)(d+2)/2 = {d+2 \choose 2}$, which was later generalised to $f_d(k) = {d+k \choose k}$.

This problem is also discussed in the manuscript "Linear Algebra Methods in Combinatorics" by Babai and Frankl, where you can find some of these proofs.