ABSTRACT For any we show that the Hamming graph admits an imbalanced partition into sets, each inducing a subgraph of low maximum degree. This improves previous results by Tandya and by Potechin and Tsang, and disproves the Strong ‐ary Sensitivity Conjecture of Asensio, García‐Marco, and Knauer. On the other hand, we prove their weaker ‐ary Sensitivity Conjecture by showing that the sensitivity of any ‐ary function is bounded from below by a polynomial expression in its degree.
Building similarity graph...
Analyzing shared references across papers
Loading...
S. García Asensio
Yuval Filmus
Ignacio García‐Marco
Journal of Graph Theory
Universitat de Barcelona
Technion – Israel Institute of Technology
Universidad de La Laguna
Building similarity graph...
Analyzing shared references across papers
Loading...
Asensio et al. (Mon,) studied this question.
www.synapsesocial.com/papers/69ccb63f16edfba7beb87f57 — DOI: https://doi.org/10.1002/jgt.70034