Sensitivity in Cayley graphs

• Ignacio Garcia-Marco ^[1] ; Kolja Knauer ^[2]
  1. [1] Universidad de La Laguna

     Universidad de La Laguna

     San Cristóbal de La Laguna, España

     
  2. [2] Universitat de Barcelona

     Universitat de Barcelona

     Barcelona, España

     
• Localización: EACA 2022: XVII Encuentro de Álgebra Computacional y Aplicaciones / coord. por Carlos Galindo Pastor , Philippe Giménez , Fernando Javier Hernando Carrillo, F. Monserrat Delpalillo , Julio José Moyano Fernández, 2023, ISBN 978-84-19647-46-7, págs. 87-90
• Idioma: inglés
• Enlaces
  • Texto Completo Libro
• 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.