Counterexamples to "A conjecture on induced subgraphs of Cayley graphs" - Lehner, Florian (Ars mathematica contemporanea, 2020)
Nedavno je Huang predstavil zelo eleganten dokaz t. i. občutljivostne domneve, ko je dokazal, da imajo grafi hiperkock naslednjo lastnost: vsak induciran podgraf na množici, ki vsebuje več kot polovico točk, ima maksimalno stopnjo najmanj ?$\sqrt{d}$?, kjer je ?$d$? valenca hiperkocke. Ta rezultat sta posplošila Alon in Zheng, ki sta dokazala, da ima vsak Cayleyev graf na elementarni abelski 2-grupi isto lastnost. Prav pred kratkim sta Potechin in Tsang dokazala analogen rezultat za Cayleyeve grafe na abelskih grupah. Postavila sta tudi domnevo, da imajo vsi Cayleyevi grafi analogno lastnost. To domnevo ovržemo s konstrukcijo različnih protiprimerov, med katerimi je tudi neskončna družina Cayleyevih grafov neomejene stopnje, ki dopuščajo induciran podgraf maksimalne stopnje 1 na množici, ki vsebuje več kot polovico točk.
Keywords: Cayley graphs; Cayleyevi grafi; občutljivostna domneva; sensitivity conjecture; točkovno tranzitivni grafi; vertex-transitive graphs