tailieunhanh - Báo cáo toán học: "Lower bounds for the football pool problem for 7 and 8 matches"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Lower bounds for the football pool problem for 7 and 8 matches. | Lower bounds for the football pool problem for 7 and 8 matches Wolfgang Haas Albert-Ludwigs-Universitat Mathematisches Institut Eckerstr. 1 79104 Freiburg Germany wolfgang_haas@ Submitted Oct 26 2006 Accepted Mar 15 2007 Published Mar 28 2007 Mathematics Subject Classifications 94B65 Abstract Let k3 n denote the minimal cardinality of a ternary code of length n and covering radius one. In this paper we show k3 7 156 and k3 8 402 improving on the best previously known bounds k3 7 153 and k3 8 398. The proofs are founded on a recent technique of the author for dealing with systems of linear inequalities satisfied by the number of elements of a covering code that lie in k-dimensional subspaces of F n. 1 Introduction Let F3 0 1 2 denote the finite field with three elements. The Hamming distance d A ụ between A x1 . xn 2 F and ụ y1 . yn 2 F is defined by d A ụ i 2 1 . n xi yi . The subset C c Fn is called a ternary code with covering radius at most one if 8A 2 Fn 9ụ 2 C with d A ụ 1 1 holds. For a monograph on covering codes see 1 . The problem to determine k3 n the minimal cardinality of a ternary code with covering radius one is known as the football pool problem and was widely studied during the last decades. Updated bounds for k3 n are contained in an internet table by Kéri 7 . The easy bound qn THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R27 1 is known as the sphere covering bound. In the recent papers 2 3 the author developed a new technique based on a method of Habsieger 4 to improve on the sphere covering bound by dealing with systems of linear inequalities satisfied by the number of elements of C that lie in k-dimensional subspaces of Fn. The method presented in 3 is limited by k n. The reason is that for larger values of k the irregular solutions of the linear inequalities no longer yield a negligible amount in the necessary estimations. The aim of this paper is to present a first method to deal with these irregularities. We consider the cases n 7 .