TY - JOUR
T1 - The equivalence of two problems on the cube
AU - Gotsman, C.
AU - Linial, N.
N1 - Funding Information:
* Supported in part by an Eshkol doctoral fellowship, Council for R&D, Israel Ministry of Science. + Research supported in part by US-Israel Binational Science Foundation and a grant from the Israel Academy of Sciences.
PY - 1992/9
Y1 - 1992/9
N2 - Denote by Qn the graph of the hypercube Cn = { +1, -1}n. The following two seemingly unrelated questions are equivalent: 1. Let G be an induced subgraph of Qn such that |V(G)| ≠ 2n-1. Denote Δ(G) = maxx ∈ V(G)degG(x) and Γ(G) = max(Δ(G), Δ(Qn - G)). Can Γ(G) be bounded from below by a function of n?; 2. Let f: Cn → {+1, -1} be a boolean function. The sensitivity of f at x, denoted s(f, x), is the number of neighbors y of x in Qn such that f(x) ≠ f(y). The sensitivity of f is s(f) = maxx ∈ Cn s(f, x). Denote by d(f) the degree of the unique representation of f as a real multilinear polynomial on Cn. Can d(f) be bounded from above by a function of s(f)?
AB - Denote by Qn the graph of the hypercube Cn = { +1, -1}n. The following two seemingly unrelated questions are equivalent: 1. Let G be an induced subgraph of Qn such that |V(G)| ≠ 2n-1. Denote Δ(G) = maxx ∈ V(G)degG(x) and Γ(G) = max(Δ(G), Δ(Qn - G)). Can Γ(G) be bounded from below by a function of n?; 2. Let f: Cn → {+1, -1} be a boolean function. The sensitivity of f at x, denoted s(f, x), is the number of neighbors y of x in Qn such that f(x) ≠ f(y). The sensitivity of f is s(f) = maxx ∈ Cn s(f, x). Denote by d(f) the degree of the unique representation of f as a real multilinear polynomial on Cn. Can d(f) be bounded from above by a function of s(f)?
UR - http://www.scopus.com/inward/record.url?scp=0001700058&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0001700058&partnerID=8YFLogxK
U2 - 10.1016/0097-3165(92)90060-8
DO - 10.1016/0097-3165(92)90060-8
M3 - Article
AN - SCOPUS:0001700058
SN - 0097-3165
VL - 61
SP - 142
EP - 146
JO - Journal of Combinatorial Theory, Series A
JF - Journal of Combinatorial Theory, Series A
IS - 1
ER -