A001839 -id:A001839 - cp's OEIS frontend

A060406 Duplicate of A001839.

0, 0, 1, 1, 2, 4, 7, 8, 12, 13, 17, 20, 26, 28, 35, 37, 44, 48, 57, 60, 70, 73, 83, 88, 100, 104

Offset: 1

dead

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

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

A005864 The coding-theoretic function A(n,4).

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 8, 16, 20, 40, 72, 144, 256, 512, 1024, 2048

Offset: 1

N. J. A. Sloane

Since A(n,3) = A(n+1,4), A(n,3) gives essentially the same sequence.
The next term a(17) is in the range 2816-3276.
Let T_n be the set of SDS-maps of sequential dynamical systems defined over the complete graph K_n in which all vertices have the same vertex function (defined using a set of two possible vertex states). Then a(n) is the maximum number of period-2 orbits that a function in T_n can have. - Colin Defant, Sep 15 2015
Since the n-halved cube graph is isomorphic to (or, if you prefer, defined as) the graph with binary sequences of length n-1 as nodes and edges between pairs of sequences that differ in at most two positions, the independence number of the n-halved cube graph is A(n-1,3) = a(n). - Pontus von Brömssen, Dec 12 2018
a(2^k) = A(2^k-1, 3) = 2^(2^k-k-1) because the hypercube Q(2^k-1) can be perfectly packed with radius-1 spheres, corresponding to a Hamming(2^k-1, 2^k-k-1) code. - Yifan Xie, May 06 2025

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 248.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 674.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A. E. Brouwer, Tables of general binary codes
A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, New table of constant weight codes, IEEE Trans. Info. Theory 36 (1990), 1334-1380.
Colin Defant, Binary Codes and Period-2 Orbits of Sequential Dynamical Systems, arXiv:1509.03907 [math.CO], 2015.
Moshe Milshtein, A new binary code of length 16 and minimum distance 3, Information Processing Letters 115.12 (2015): 975-976.
Patric R. J. Östergård (patric.ostergard(AT)hut.fi), T. Baicheva and E. Kolev, Optimal binary one-error-correcting codes of length 10 have 72 codewords, IEEE Trans. Inform. Theory, 45 (1999), 1229-1231.
A. M. Romanov, New binary codes with minimal distance 3, Problemy Peredachi Informatsii, 19 (1983) 101-102.
Eric Weisstein's World of Mathematics, Error-Correcting Code
Eric Weisstein's World of Mathematics, Halved Cube Graph
Eric Weisstein's World of Mathematics, Independence Number
Wikipedia, Halved cube graph
Index entries for sequences related to A(n,d)

Cf. A005865: A(n,6) ~ A(n,5), A005866: A(n,8) ~ A(n,7).

Cf. A001839: A(n,4,3), A001843: A(n,4,4), A169763: A(n,4,5).

A060407 Maximal number of pairwise edge-disjoint monochromatic K_3's in a K_n for any 2-coloring of the edges of K_n.

Original entry on oeis.org

0, 0, 0, 1, 2, 2, 3, 4, 6

Offset: 3

N. J. A. Sloane, Apr 06 2001

P. Erdős et al., Edge disjoint monochromatic triangles in 2-colored graphs, Discrete Math., 231 (2001), 135-141.

Cf. A001839.

A351100 Maximum number of 4-subsets of an n-set such that every 3-subset is covered at most twice.

Original entry on oeis.org

2, 5, 9, 15, 28, 40, 60, 80, 108, 143, 182, 225, 280, 340, 405

Offset: 4

Jeremy Tan, Jan 31 2022

Maximum number of K_4^3's that can be packed in a doubled K_n^3, where K_n^m is the complete m-uniform hypergraph on n vertices.

			a(6) = 9 because of the following optimal collection of 4-subsets:
  1 2 3 4
  2 3 4 5
  3 4 5 6
  4 5 6 1
  5 6 1 2
  6 1 2 3
  1 2 4 5
  2 3 5 6
  3 4 6 1

Richard K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Department of Mathematics, University of Calgary, January 1967. [Annotated and scanned copy, with permission]
Haim Hanani, On quadruple systems, Canadian Journal of Mathematics, 12 (1960), 145-157.
Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Cf. A001839-A001843 for other packing sequences discussed in Richard K. Guy's paper.

a(n) >= 2*A001843(n). Equality holds if n = 6k+2 or 6k+4 (Hanani).

cp's OEIS Frontend

A060406 Duplicate of A001839.

Views

Author

Keywords

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005864 The coding-theoretic function A(n,4).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A060407 Maximal number of pairwise edge-disjoint monochromatic K_3's in a K_n for any 2-coloring of the edges of K_n.

Views

Author

Keywords

Links

Crossrefs

A351100 Maximum number of 4-subsets of an n-set such that every 3-subset is covered at most twice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula