The equivalence of two problems on the cube

C. Gotsman, N. Linial

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

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)?

Original languageEnglish (US)
Pages (from-to)142-146
Number of pages5
JournalJournal of Combinatorial Theory, Series A
Volume61
Issue number1
DOIs
StatePublished - Sep 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'The equivalence of two problems on the cube'. Together they form a unique fingerprint.

Cite this