Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs
✍ Scribed by Noga Alon; Văn H Vũ
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 435 KB
- Volume
- 79
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
Let / 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 / 1 (n)=n (1Â2+o(1)) n . This solves a problem of Graham and Sloane. Let m(n) denote the maximum possible number m such that given a set of m coins out of a collection of coins of two unknown distinct weights, one can decide if 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 Vu~. 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 Ha# stad of threshold gates that require large weights. 1997 Academic Press 1. INTRODUCTION For a real matrix A, the spectral norm of A is defined by &A& s = sup x{0 |Ax|Â|x|. If A is invertible, the condition number of A is c(A)= &A& s &A &1 & s . This quantity measures the sensibility of the equation Ax=b article no. TA962780 133 0097-3165Â97 25.00