|
%I #45 Apr 19 2023 09:55:29
%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 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 Noga Alon and Van H. Vu, <a href="https://doi.org/10.1006/jcta.1997.2780">Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs</a>, Journal of Combinatorial Theory, Series A, Volume 79, Issue 1, July 1997, Pages 133-160.
%H Zoltán Füredi, <a href="https://doi.org/10.1016/0012-365X(92)90590-C">Indecomposable regular graphs and hypergraphs</a>, Discrete Mathematics, Volume 101, Issues 1-3, 29 May 1992 (DOI: 10.1016/0012-365X(92)90590-C), pp. 59-64.
%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="https://pure.tue.nl/ws/portalfiles/portal/4401921/595956.pdf">An "offense-last-move" game against perfect local defense at targets of arbitrary values</a>, Unpublished AT&T Bell Labs Memorandum, 1968.
%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
|
