Improved Lower Bounds


Lower Bounds

While there has been far less work on lower bounds than upper bounds, there has been some progress, starting with Sidorenko's work in the 1990s.

More recently, in 2002 David Applegate, Eric Rains, and Neil Sloane showed that C(10,5,4)=51;  C(11,6,5)>=96;  C(11,7,6)=84;  C(12,7,6)>=165;  C(12,8,7)=126;  C(13,9,8)=185.

Also in 2002, John Bate, Ben Li, and John van Rees showed that C(19,6,2)=15, and Li and van Rees showed C(17,10,3)=11.

In 2004, Malcolm Greig, Li, and van Rees showed that C(28,9,2)=C(41,13,2)=14.

In 2007, Klas Marström gave many new lower bounds, and found all non-isomorphic coverings for many parameters.

Most recently, Daniel Horsley wrote a paper Generalizing Fisher's Inequality to coverings and packings, which improves lower bounds for a wide range of coverings with t=2. Adding his lower bounds improved over 400 entries in this database.

These bounds, with other improvements that result from them, are given here.

Below are the improvements that we know of on lower bounds for the covering designs in the tables of our JCD paper New Constructions for Covering Designs, since that paper appeared in 1995.  These improvements appear roughly in the order we learned of them.  For each, we give the date (either when we learned of the result, or a publication date) and attribution, along with the old lower bound. We also give the improvements that follow directly from the Schonheim inequality:

      C(v,k,t)  >=  ceiling( (v/k) * C(v-1,k-1,t-1) )

And we state a lower bound as an equality if we know of an actual covering whose size matches the bound.


July 1996;   Alex Sidorenko:
  C(13,10,7) = 30     (was 29)
    so C(14,11,8) >= 39     (was 37)
  C(13,9,5) = 19     (was 18)
    so C(14,10,6) >= 27     (was 26)
    so C(15,11,7) >= 37     (was 36)
    so C(16,12,8) >= 50     (was 48)
  C(16,12,5) = 12     (was 11)
    so C(17,13,6) >= 16     (superseded; see below)
  C(17,13,6) = 17     (was 15)
    so C(18,14,7) >= 22     (was 20)
    so C(19,15,8) >= 28     (was 26)
  C(13,8,3) = 10     (was 9)
    so C(14,9,4) = 16     (was 14)
    so C(15,10,5) >= 24     (was 21)
    so C(16,11,6) >= 35     (was 31)
    so C(17,12,7) >= 50     (was 44)
    so C(18,13,8) >= 70     (was 61)
  C(16,11,4) = 12     (was 11)
    so C(17,12,5) = 17     (was 16)
    so C(18,13,6) >= 24     (was 23)
    so C(19,14,7) >= 33     (was 32)
    so C(20,15,8) >= 44     (was 43)
  C(11,7,5) >= 33     (was 32)
    so C(12,8,6) >= 50     (was 48)
    so C(13,9,7) >= 73     (was 70)
    so C(14,10,8) >= 103     (was 98)
  C(11,7,6) >= 81     (was 79)
    so C(12,8,7) >= 122     (was 120)
    so C(13,9,8) >= 177     (was 174)

September 1996;   Alex Sidorenko:
  C(18,13,5) = 15     (was 14)
    so C(19,14,6) >= 21     (was 19)
    so C(20,15,7) >= 28     (was 26)
    so C(21,16,8) >= 37     (was 35)
  C(19,14,5) = 14     (was 13)
    so C(20,15,6) = 19     (was 18)
    so C(21,16,7) >= 25     (was 24)
  C(15, 9,3) = 10     (was 9)
    so C(16,10,4) >= 16     (was 15)
    so C(17,11,5) >= 25     (was 24)
    so C(18,12,6) >= 38     (was 36)
    so C(19,13,7) >= 56     (was 53)
    so C(20,14,8) >= 80     (was 76)
  C(18,12,4) = 12     (was 11)
    so C(19,13,5) >= 18     (was 17)
    so C(20,14,6) >= 26     (was 25)
    so C(21,15,7) >= 37     (was 35)
    so C(22,16,8) >= 51     (was 49)
  C(15,11,6) = 21     (was 20)
    so C(16,12,7) = 28     (was 27)
    so C(17,13,8) >= 37     (was 36)
  C(16,12,6) = 19     (was 18)
    so C(17,13,7) >= 25     (was 24)
    so C(18,14,8) >= 33     (was 31)
  C(18,14,7) = 24     (was 22)
    so C(19,15,8) = 31     (was 28)
  C(20,16,8) = 26     (was 24)
  C(19,13,4) = 11     (was 10)
    so C(20,14,5) >= 16     (was 15)
    so C(21,15,6) >= 23     (was 21)
    so C(22,16,7) >= 32     (was 29)

October 1996;   Alex Sidorenko:
  C(14,11,8) = 40     (was 39)
  C(21,16,5) = 12     (was 11)
  C(21,16,6) = 17     (was 16)

October 1996;   Staszek Radziszowski:
  C(14,7,3) = 15     (was 14)
    so C(15,8,4) >= 29     (was 27)
    so C(16,9,5) >= 52     (was 48)
    so C(17,10,6) >= 89     (was 82)
    so C(18,11,7) >= 146     (was 135)
    so C(19,12,8) >= 232     (was 214)

February 2002;   David Applegate, Eric Rains, and Neil Sloane; Journal of Combinatorial Designs 11(3):218--228, 2003:
  C(10,5,4) = 51     (was 50)
    so C(11,6,5) >= 94     (superseded; see below)
  C(11,6,5) >= 96     (was 92)
    so C(12,7,6) >= 165     (was 158)
    so C(13,8,7) >= 269     (was 257)
    so C(14,9,8) >= 419     (was 400)
  C(11,7,6) = 84     (was 79)
    so C(12,8,7) = 126     (was 122)
    so C(13,9,8) >= 182     (superseded; see below)
  C(13,9,8) = 185     (was 174)

February 2002;   John Bate, Ben Li, and John van Rees; Congressus Numerantium 157:95--102, 2002:
  C(19,6,2) = 15     (was 14)
    so C(20,7,3) >= 43     (was 40)
    so C(21,8,4) >= 113     (was 105)
    so C(22,9,5) >= 277     (was 257)
    so C(23,10,6) >= 638     (was 592)
    so C(24,11,7) >= 1392     (was 1292)
    so C(25,12,8) >= 2900     (was 2692)

August 2002;   Ben Li and John van Rees:
  C(17,10,3) = 11     (was 9)
    so C(18,11,4) >= 18     (was 15)
    so C(19,12,5) >= 29     (was 24)
    so C(20,13,6) >= 45     (was 37)
    so C(21,14,7) >= 68     (was 56)
    so C(22,15,8) >= 100     (was 83)

August 2004;   Malcolm Greig, Ben Li, and John van Rees; Ars Combinatoria, to appear:
  C(28,9,2) = 14     (was 13)
    so C(29,10,3) >= 41     (was 38)
    so C(30,11,4) >= 112     (was 104)
    so C(31,12,5) >= 290     (was 269)
    so C(32,13,6) >= 714     (was 663)

This page last updated 10 March 2005