login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A182080 a(n) = maximal depth of an indecomposable exact cover of an n-set. 1
1, 2, 3, 5, 9, 18, 38 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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.

The sum of two block systems f,g is defined in the obvious way, and z denotes the zero block system.

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

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

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

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

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.

Graver gives many references, most of which seem never to have been published (see scanned pages below).

REFERENCES

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.

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.

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.

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.

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); http://alexandria.tue.nl/repository/freearticles/593483.pdf

LINKS

Table of n, a(n) for n=1..7.

J. E. Graver, Pages 731-734 and 742-743

FORMULA

Alon and Vu give asymptotics.

EXAMPLE

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

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

------------------

..- | 0 0 0 | 0

..1 | 1 0 0 | 0

..2 | 0 1 0 | 0

..3 | 0 0 1 | 0

.12 | 1 1 0 | 1

.13 | 1 0 1 | 1

.23 | 0 1 1 | 1

123 | 1 1 1 | 0

CROSSREFS

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

Sequence in context: A000602 A034790 A047121 * A259117 A096753 A022862

Adjacent sequences:  A182077 A182078 A182079 * A182081 A182082 A182083

KEYWORD

nonn,more,nice

AUTHOR

N. J. A. Sloane, Apr 10 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 29 14:18 EDT 2017. Contains 287247 sequences.