A066010 -id:A066010 - cp's OEIS frontend

A066701 Triangle giving number of nonisomorphic minimal covering designs with parameters (n, k, k-1) (designs achieving the covering number C(n,k,k-1) given in A066010), for n >= 2, 2 <= k <= n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 5, 1, 6, 1, 1, 1, 1, 1, 77, 3, 2, 1, 1, 1, 1, 58, 1, 40, 1, 20, 1, 1, 1, 1, 2

Offset: 2

N. J. A. Sloane, Jan 11 2002

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets. This sequence says how many different solutions there are for C(n,k,k-1).

CRC Handbook of Combinatorial Designs, 1996, p. 263.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers
Index entries for sequences related to Steiner systems

Cf. A066010. A030129 gives entries in second column in the cases when a Steiner triple system exists.

A051390 gives entries in 3rd column in the cases when a Steiner quadruple system exists.

A011975 Covering numbers C(n,3,2).

Original entry on oeis.org

1, 3, 4, 6, 7, 11, 12, 17, 19, 24, 26, 33, 35, 43, 46, 54, 57, 67, 70, 81, 85, 96, 100, 113, 117, 131, 136, 150, 155, 171, 176, 193, 199, 216, 222, 241, 247, 267, 274, 294, 301, 323, 330, 353, 361, 384, 392, 417, 425, 451, 460, 486

Offset: 3

N. J. A. Sloane

Also, minimal number of triangles needed to cover every edge (and node) of a complete graph on n nodes. This problem is also known as the edge clique covering problem. - Dmitry Kamenetsky, Jan 24 2016

P. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.
CRC Handbook of Combinatorial Designs, 1996, p. 262.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

T. D. Noe, Table of n, a(n) for n = 3..1000
Marek Cygan, Marcin Pilipczuk and Michał Pilipczuk, Known algorithms for EDGE CLIQUE COVER are probably optimal, arXiv:1203.1754 [cs.DS], 2012.
Oliver Goldschmidt, Dorit S. Hochbaum, Cor Hurkens and Gang Yu, Approximation Algorithms for the k-Clique Covering Problem, Journal of Discrete Mathematics, volume 9, issue 3, pages 492-509, 1995, doi: 10.1137/S089548019325232X.
D. Gordon, La Jolla Repository of Coverings
Jenö Lehel, The minimum number of triangles covering the edges of a graph, Journal of Graph Theory, volume 13, issue 3, pages 369-384, 1989.
Uenal Mutlu (uenalm(AT)metronet.de), Tables of coverings
Wikipedia, Clique Cover Problem.
Index entries for covering numbers

Cf. A011976, A011977, A001839. A column of A066010. Also a column of A036838.

L := proc(v,k,t,l) local i,t1; t1 := l; for i from v-t+1 to v do t1 := ceil(t1*i/(i-(v-k))); od: t1; end; # gives Schoenheim bound L_l(v,k,t). Present sequence is L_1(n,3,2,1).

L[v_, k_, t_, m_] := Module[{t1 = m}, Do[t1 = Ceiling[t1*i/(i - (v - k))], {i, v - t + 1, v}]; t1]; Table[L[n, 3, 2, 1], {n, 3, 100}] (* T. D. Noe, Sep 28 2011 *)

Conjecture: G.f. ( -1-2*x-2*x^5+x^7+x^6-x^8 ) / ( (1+x+x^2)*(x^2-x+1)*(1+x)^2*(x-1)^3 ) with a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9). - R. J. Mathar, Aug 12 2012

a(n) = ceiling((n/3)*ceiling((n-1)/2)). - Nathaniel Johnston, Jan 10 2024

A011983 Covering numbers C(n,5,4).

Original entry on oeis.org

1, 5, 9, 20, 30, 51, 66, 113

Offset: 5

N. J. A. Sloane

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

CRC Handbook of Combinatorial Designs, 1996, p. 263.
D. De Caen, D. L. Kreher, S. P. Radziszowski, and W. H. Mills, On the covering of t-sets with (t+1)-sets: C(9,5,4) and C(10,6,5). Discrete Math. 92 (1991), no. 1-3, 65-77.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, arXiv:math/0205303 [math.CO], 2002; J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

Cf. A066009. A column of A066010.

Next term is <= 157.

A066009 Covering numbers C(n,7,6).

Original entry on oeis.org

1, 7, 16, 45, 84

Offset: 7

N. J. A. Sloane

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

CRC Handbook of Combinatorial Designs, 1996, p. 263.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

Cf. A011983. A column of A066010.

A066225 Covering numbers C(n,n-4,n-5).

Original entry on oeis.org

3, 7, 14, 30, 50, 84, 126, 185, 259, 357, 476

Offset: 6

N. J. A. Sloane

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

CRC Handbook of Combinatorial Designs, 1996, p. 263.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, arXiv:math/0205303 [math.CO], 2002; J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. Markström, Covering designs.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
A. Sidorenko, On Turan numbers of the complete 4-graphs, Discr. Math., 344 (2021), #112544.
Index entries for covering numbers

A column of A066010.

A036830 is a lower bound.

More terms from Sidorenko (2021) added by N. J. A. Sloane, Oct 31 2021

A011979 Covering numbers C(n,4,3) (next term is <= 261).

Original entry on oeis.org

1, 4, 6, 12, 14, 25, 30, 47, 57, 78, 91, 124, 140, 183, 207

Offset: 4

N. J. A. Sloane

CRC Handbook of Combinatorial Designs, 1996, p. 262.

D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

A column of A066010.

A011987 Covering numbers C(n,6,5) (next term is <= 100).

Original entry on oeis.org

1, 6, 12, 30, 50

Offset: 6

N. J. A. Sloane

CRC Handbook of Combinatorial Designs, 1996, p. 263.

D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

A column of A066010.

A066011 Covering numbers C(n,8,7).

Original entry on oeis.org

1, 8, 20, 63, 126

Offset: 8

N. J. A. Sloane

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

CRC Handbook of Combinatorial Designs, 1996, p. 263.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

A column of A066010.

A066137 Covering numbers C(n,9,8).

Original entry on oeis.org

1, 9, 25, 84, 185

Offset: 9

N. J. A. Sloane

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

CRC Handbook of Combinatorial Designs, 1996, p. 263.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Applegate, E. M. Rains and N. J. A. Sloane, On asymmetric coverings and covering numbers, J. Comb. Des. 11 (2003), 218-228.
D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

A column of A066010.

A066140 Covering numbers C(n,n-3,n-4).

Original entry on oeis.org

3, 6, 12, 20, 30, 45, 63, 84

Offset: 5

N. J. A. Sloane

nonn

C(v,k,t) is the smallest number of k-subsets of an n-set such that every t-subset is contained in at least one of the k-subsets.

CRC Handbook of Combinatorial Designs, 1996, p. 263.
W. H. Mills and R. C. Mullin, Coverings and packings, pp. 371-399 of Jeffrey H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory, Wiley, 1992.

D. Gordon, La Jolla Repository of Coverings
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets, J. Combinat. Designs, 7 (1999), 217-226.
K. J. Nurmela and Patric R. J. Östergård, New coverings of t-sets with (t+1)-sets (appendix), J. Combinat. Designs, 7 (1999), 217-226.
Index entries for covering numbers

A column of A066010.

cp's OEIS Frontend

A066701 Triangle giving number of nonisomorphic minimal covering designs with parameters (n, k, k-1) (designs achieving the covering number C(n,k,k-1) given in A066010), for n >= 2, 2 <= k <= n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A011975 Covering numbers C(n,3,2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A011983 Covering numbers C(n,5,4).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A066009 Covering numbers C(n,7,6).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A066225 Covering numbers C(n,n-4,n-5).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A011979 Covering numbers C(n,4,3) (next term is <= 261).

Views

Author

Keywords

References

Links

Crossrefs

A011987 Covering numbers C(n,6,5) (next term is <= 100).

Views

Author

Keywords

References

Links

Crossrefs

A066011 Covering numbers C(n,8,7).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A066137 Covering numbers C(n,9,8).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A066140 Covering numbers C(n,n-3,n-4).

Views

Author