Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs

[摘要] Let chi(1)(n) denote the maximum possible absolute value of an entry of the inverse of an n by n invertible matrix with 0,1 entries. It is proved that chi 1(n) = n((1/2+o(1))n). This solves a problem of Graham and Sloane. Let m(iz) denote the maximum possible number in such that given a set of m coins out of a collection of coins of two unknown distinct weights, one can decide ii all the coins have the same weight or not using n weighings in a regular balance beam. It is shown that m(n)= n((1/2+o(1))n). This settles a problem of Kozlov and V (u) over tilde. Let D(n) denote the maximum possible degree of a regular multi-hypergraph on n vertices that contains no proper regular nonempty subhypergraph. It is shown that D(n) = n((1/2+o(1))n). This improves estimates of Shapley, van Lint and Pollak. All these results and several related ones are proved by a similar technique whose main ingredient is an extension of a construction of Hastad of threshold gates that require large weights. (C) 1997 Academic Press.

[发布日期] 1997-07-01