# American Institute of Mathematical Sciences

May  2007, 1(2): 173-195. doi: 10.3934/amc.2007.1.173

## New upper bounds on codes via association schemes and linear programming

 1 Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ, P.O. Box 94079, 1090 GB Amsterdam, Netherlands 2 Department of Computer Science, Technion, Haifa 32000, Israel 3 School of Electrical Engineering, Tel Aviv University, Tel Aviv 69978

Received  August 2006 Revised  February 2007 Published  May 2007

Let $A(n, d)$ denote the maximum number of codewords in a binary code of length n and minimum Hamming distance $d$. Upper and lower bounds on $A(n, d)$ have been a subject for extensive research. In this paper we examine upper bounds on $A(n, d)$ as a special case of bounds on the size of subsets in metric association scheme. We will first obtain general bounds on the size of such subsets, apply these bounds to the binary Hamming scheme, and use linear programming to further improve the bounds. We show that the sphere packing bound and the Johnson bound as well as other bounds are special cases of one of the bounds obtained from association schemes. Specific bounds on $A(n, d)$ as well as on the sizes of constant weight codes are also discussed.
Citation: Beniamin Mounits, Tuvi Etzion, Simon Litsyn. New upper bounds on codes via association schemes and linear programming. Advances in Mathematics of Communications, 2007, 1 (2) : 173-195. doi: 10.3934/amc.2007.1.173

2020 Impact Factor: 0.935