The Equivalence of Two Problems on the Cube
The Equivalence of Two Problems on the Cube
复制标题
DOI：
10.1016/0097-3165(92)90060-8
复制
发表时间：
1992-09
期刊：
影响因子：
--
通讯作者：
C. Gotsman;N. Linial
中科院分区：
文献类型：
--
作者：
C. Gotsman;N. Linial
用Qn表示超立方体Cn = {+1，−1}n的图。下面两个看似无关的问题是等价的：1。设G是Qn的导出子图，使得|V（G）|2n−1。记Δ（G）= maxx∈V（G）degG（x）和Γ（G）= max（Δ（G），Δ（Qn-G））。Γ（G）能被n的函数从下有界吗？2.设f：Cn→ {+1，−1}是一个布尔函数。atx的灵敏度表示为（f，x），是xinQn使得f（x）<$f（y）的邻域数。fiss（f）= maxx∈Cns（f，x）的灵敏度。将byd（f）表示为Cn上的真实的多线性多项式的唯一表示的次数。Cand（f）从上到下受s（f）的函数约束？
Denote byQnthe graph of the hypercubeCn= { +1, −1}n. The following two seemingly unrelated questions are equivalent: 1. LetGbe an induced subgraph ofQnsuch 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 ofn?; 2. Letf:Cn→ {+1, −1} be a boolean function. Thesensitivityoffatx, denoteds(f,x), is the number of neighborsyofxinQnsuch thatf(x) ≠f(y). The sensitivity offiss(f) = maxx∈Cns(f,x). Denote byd(f) the degree of the unique representation offas a real multilinear polynomial onCn. Cand(f) be bounded from above by a function ofs(f)?