login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A182080 a(n) is the maximal depth of an indecomposable exact cover of an n-set. 1

%I

%S 1,2,3,5,9,18,38

%N a(n) is the maximal depth of an indecomposable exact cover of an n-set.

%C Let U = {1,2,...,n} and let P = collection of all subsets of U.

%C 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 The sum of two block systems f,g is defined in the obvious way, and z denotes the zero block system.

%C f is an exact cover of depth d if for each u in U,

%C Sum_{ S in P: u in S} f(S) = d.

%C An exact cover is decomposable if f = g+h where g, h are nonzero exact covers.

%C Then a(n) is the maximal depth of an indecomposable exact cover of U.

%C 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 Graver gives many references, most of which seem never to have been published (see scanned pages below).

%D 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 (DOI: 10.1006/jcta.1997.2780), pp. 133-160.

%D 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.

%D Graver, J. E., 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.

%D 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 Memonrandum, 1968; http://repository.tue.nl/595956.

%H J. E. Graver, <a href="/A182080/a182080_1.pdf">Pages 731-734 and 742-743</a>

%H J. H. van Lint and H. O. Pollak, <a href="http://alexandria.tue.nl/repository/freearticles/593483.pdf">An Asymmetric Contest for Properties of Arbitrary Value</a>, Philips Res. Repts. 30 (1975), 40-55, (Special issue in honour of C. J. Bouwkamp).

%F Alon and Vu give asymptotics.

%e Example showing an indecomposable f of depth d = 2 for n = 3, illustrating a(3) = 2:

%e .S. | 1 2 3 | f(S)

%e ------------------

%e ..- | 0 0 0 | 0

%e ..1 | 1 0 0 | 0

%e ..2 | 0 1 0 | 0

%e ..3 | 0 0 1 | 0

%e .12 | 1 1 0 | 1

%e .13 | 1 0 1 | 1

%e .23 | 0 1 1 | 1

%e 123 | 1 1 1 | 0

%Y Cf. A096753 (has the same beginning, but is unlikely to be the same sequence).

%K nonn,more,nice

%O 1,2

%A _N. J. A. Sloane_, Apr 10 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 15 08:29 EDT 2021. Contains 342977 sequences. (Running on oeis4.)