|
|
A182080
|
|
a(n) is the maximal depth of an indecomposable exact cover of an n-set.
|
|
1
|
|
|
|
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
|
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.
|
|
LINKS
|
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.
|
|
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).
|
|
KEYWORD
|
nonn,more,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|