Essential covers of the cube by hyperplanes

Linial, Nathan ; Radhakrishnan, Jaikumar (2005) Essential covers of the cube by hyperplanes Journal of Combinatorial Theory, Series A, 109 (2). pp. 331-338. ISSN 0097-3165

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/j.jcta.2004.07.012

Abstract

A set L of linear polynomials in variables X1,X2,...,Xn with real coefficients is said to be an essential cover of the cube {0,1}n if (E1) for each v∈{0,1}n, there is a p∈L such that p(v)=0; (E2) no proper subset of L satisfies (E1), that is, for every p∈L, there is a v∈{0,1}n such that p alone takes the value 0 on v; (E3) every variable appears (in some monomial with non-zero coefficient) in some polynomial of L. Let e(n) be the size of the smallest essential cover of {0,1}n. In the present note we show that ̅η+1+1)≤e(n)≤⌈n/2⌉+1.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:57649
Deposited On:29 Aug 2011 08:38
Last Modified:29 Aug 2011 08:38

Repository Staff Only: item control page