# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a182080
Showing 1-1 of 1
%I A182080 #45 Apr 19 2023 09:55:29
%S A182080 1,2,3,5,9,18,38
%N A182080 a(n) is the maximal depth of an indecomposable exact cover of an n-set.
%C A182080 Let U = {1,2,...,n} and let P = collection of all subsets of U.
%C A182080 A block system on U is a function f: P -> {0,1,2,...}; f(S) is the number of times a subset S occurs as a block in the system.
%C A182080 The sum of two block systems f,g is defined in the obvious way, and z denotes the zero block system.
%C A182080 f is an exact cover of depth d if for each u in U,
%C A182080 Sum_{ S in P: u in S} f(S) = d.
%C A182080 An exact cover is decomposable if f = g+h where g, h are nonzero exact covers.
%C A182080 Then a(n) is the maximal depth of an indecomposable exact cover of U.
%C A182080 The values of a(6), a(7), a(8) shown here were only conjectural, but that may have changed since Graver's paper is now nearly 40 years old.
%C A182080 Graver gives many references, most of which seem never to have been published (see scanned pages below).
%D A182080 J. E. Graver, A survey of the maximum depth problem for indecomposable exact covers. In "Infinite and finite sets" (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vol. II, pp. 731-743. Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975. MR0401516 (53 #5343). See scans of selected pages below.
%H A182080 Noga Alon and Van H. Vu, Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs, Journal of Combinatorial Theory, Series A, Volume 79, Issue 1, July 1997, Pages 133-160.
%H A182080 Zoltán Füredi, Indecomposable regular graphs and hypergraphs, Discrete Mathematics, Volume 101, Issues 1-3, 29 May 1992 (DOI: 10.1016/0012-365X(92)90590-C), pp. 59-64.
%H A182080 J. E. Graver, Pages 731-734 and 742-743
%H A182080 J. H. van Lint and H. O. Pollak, An "offense-last-move" game against perfect local defense at targets of arbitrary values, Unpublished AT&T Bell Labs Memorandum, 1968.
%H A182080 J. H. van Lint and H. O. Pollak, An Asymmetric Contest for Properties of Arbitrary Value, Philips Res. Repts. 30 (1975), 40-55, (Special issue in honour of C. J. Bouwkamp).
%F A182080 Alon and Vu give asymptotics.
%e A182080 Example showing an indecomposable f of depth d = 2 for n = 3, illustrating a(3) = 2:
%e A182080 .S. | 1 2 3 | f(S)
%e A182080 ------------------
%e A182080 ..- | 0 0 0 | 0
%e A182080 ..1 | 1 0 0 | 0
%e A182080 ..2 | 0 1 0 | 0
%e A182080 ..3 | 0 0 1 | 0
%e A182080 .12 | 1 1 0 | 1
%e A182080 .13 | 1 0 1 | 1
%e A182080 .23 | 0 1 1 | 1
%e A182080 123 | 1 1 1 | 0
%Y A182080 Cf. A096753 (has the same beginning, but is unlikely to be the same sequence).
%K A182080 nonn,more,nice
%O A182080 1,2
%A A182080 _N. J. A. Sloane_, Apr 10 2012
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE