Sensitivity in Cayley graphs

Resumen

In 2019, Huang proved 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. The key point of hisargument is the proof that every set of more than half the vertices of the -dimensional hypercube induces a subgraph of maximum degree at least . Huang asked whether similar results can be obtained for other highly symmetric graphs.In this work we first prove that this result cannot be extended to general Cayley graphs.We present infinite families of Cayley graphs of groups of unbounded degree that contain induced subgraphs of maximum degree on more than half the vertices.Second, we propose Coxeter groups as a suitable generalization of the hypercube with respect to Huang's question. "Ve support our proposal with some partial results plus a large amount of computer assisted experiments.Finally, we provide examples of cube-free Cayley graphs where every induced subgraph on more than half the vertices has high maximum degree. Interestingly, these examples rely on point-line incidence results of projective planes over a finite field.