Unitary signings and induced subgraphs of Cayley graphs of $\mathbb{Z}_2^{n}$
Advances in Combinatorics · 2020
DOI: 10.19086/aic.17912 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Combinatorics, 2020. Verfasst von Noga Alon und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Boolean functions play an important role in many different areas of computer science. The _local sensitivity_ of a Boolean function $f:\{0,1\}^n\to \{0,1\}$ on an input $x\in\{0,1\}^n$ is the number of coordinates whose flip changes the value of $f(x)$, i.e., the number of i's such that $f(x)\not=f(x+e_i)$, where $e_i$ is the $i$-th unit vector. The _sensitivity_ of a Boolean function is its maximum local sensitivity. In other words, the sensitivity measures the robustness of a Boolean function with respect to a perturbation of its input. Another notion that measures the robustness is block sensitivity. The _local block sensitivity_ of a Boolean function $f:\{0,1\}^n\to \{0,1\}$ on an input $x\in\{0,1\}^n$ is the number of disjoint subsets $I$ of $\{1,..,n\}$ such that flipping the coordinates indexed by $I$ changes the value of $f(x)$, and the _block sensitivity_ of $f$ is its maximum local block sensitivity. Since the local block sensitivity is at least the local sensitivity for any input $x$, the block sensitivity of $f$ is at least the sensitivity of $f$. The next example demonstrates that the block sensitivity of a Boolean function is not linearly bounded by its sensitivity. Fix an integer $k\ge 2$ and define a Boolean function $f:\{0,1\}^{2k^2}\to\{0,1\}$ as follows: the coordinates of $x\in\{0,1\}^{2k^2}$ are split into $k$ blocks of size $2k$ each and $f(x)=1$ if and only if at least one of the blocks contains exactly two entries equal to one and these entries are consecutive. While the sensitivity of the function $f$ is $2k$, its block sensitivity is $k^2$. The Sensitivity Conjecture, made by Nisan and Szegedy in 1992, asserts that the block sensitivity of a Boolean function is polynomially bounded by its sensivity. The example above shows that the degree of such a polynomial must be at least two. The Sensitivity Conjecture has been recently proven by Huang in [Annals of Mathematics 190 (2019), 949-955](https://doi.org/10.4007/annals.2019.190.3.6). He proved the following combinatorial statement that implies the conjecture (with the degree of the polynomial equal to four): any subset of more than half of the vertices of the $n$-dimensional cube $\{0,1\}^n$ induces a subgraph that contains a vertex with degree at least $\sqrt{n}$. The present article extends this result as follows: every Cayley graph with the vertex set $\{0,1\}^n$ and any generating set of size $d$ (the vertex set is viewed as a vector space over the binary field) satisfies that any subset of more than half of its vertices induces a subgraph that contains a vertex of degree at least $\sqrt{d}$. In particular, when the generating set consists of the $n$ unit vectors, the Cayley graph is the $n$-dimensional hypercube.
Zitieren
APA
Alon, N., & Zheng, K. (2020). Unitary signings and induced subgraphs of Cayley graphs of $\mathbb{Z}_2^{n}$. Advances in Combinatorics. https://doi.org/10.19086/aic.17912
Vancouver
Alon N, Zheng K. Unitary signings and induced subgraphs of Cayley graphs of $\mathbb{Z}_2^{n}$. Advances in Combinatorics. 2020. doi:10.19086/aic.17912
BibTeX
@article{Alon2020,
author = {Alon, Noga and Zheng, Kai},
title = {Unitary signings and induced subgraphs of Cayley graphs of $\mathbbZ_2^n$},
journal = {Advances in Combinatorics},
year = {2020},
doi = {10.19086/aic.17912}
}
EUVIMED