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.

Pravice

URN

URN:NBN:SI:DOC-10EH7ZFN

COBISSID

43107843

Objavljeno

28.04.2021

Metapodatki

Citiranje

APA:

Lehner, Florian, Verret, Gabriel (2020). Counterexamples to "A conjecture on induced subgraphs of Cayley graphs". Ars mathematica contemporanea, letnik 19, številka 1, str. 77-82. URN:NBN:SI:DOC-10EH7ZFN from http://www.dlib.si

MLA:

Lehner, Florian, Verret, Gabriel. "Counterexamples to "A conjecture on induced subgraphs of Cayley graphs"." Ars mathematica contemporanea letnik 19. številka 1 (2020) str. 77-82.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-10EH7ZFN>

Ars mathematica contemporanea
2008-
(Zbirni zapis)