In this paper, we show that every $(2^n-1+1)$-vertex induced subgraph of
the $n$-dimensional cube graph has maximum degree at least $n$. This
result is best possible, and improves a logarithmic lower bound shown by Chung,
Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that
the sensitivity and degree of a boolean function are polynomially related,
solving an outstanding foundational problem in theoretical computer science,
the Sensitivity Conjecture of Nisan and Szegedy.
Beschreibung
[1907.00847] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
%0 Journal Article
%1 huang2019induced
%A Huang, Hao
%D 2019
%K mathematics proof-systems theory
%T Induced subgraphs of hypercubes and a proof of the Sensitivity
Conjecture
%U http://arxiv.org/abs/1907.00847
%X In this paper, we show that every $(2^n-1+1)$-vertex induced subgraph of
the $n$-dimensional cube graph has maximum degree at least $n$. This
result is best possible, and improves a logarithmic lower bound shown by Chung,
Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that
the sensitivity and degree of a boolean function are polynomially related,
solving an outstanding foundational problem in theoretical computer science,
the Sensitivity Conjecture of Nisan and Szegedy.
@article{huang2019induced,
abstract = {In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of
the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This
result is best possible, and improves a logarithmic lower bound shown by Chung,
F\"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that
the sensitivity and degree of a boolean function are polynomially related,
solving an outstanding foundational problem in theoretical computer science,
the Sensitivity Conjecture of Nisan and Szegedy.},
added-at = {2019-09-13T18:46:26.000+0200},
author = {Huang, Hao},
biburl = {https://www.bibsonomy.org/bibtex/25793348add84634c903ec350c5d7a403/kirk86},
description = {[1907.00847] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture},
interhash = {192b43ed1c84fb467c233af4c0c188c4},
intrahash = {5793348add84634c903ec350c5d7a403},
keywords = {mathematics proof-systems theory},
note = {cite arxiv:1907.00847},
timestamp = {2019-09-13T18:46:26.000+0200},
title = {Induced subgraphs of hypercubes and a proof of the Sensitivity
Conjecture},
url = {http://arxiv.org/abs/1907.00847},
year = 2019
}