SZTE Bolyai Intézet - Simonyi Gábor: Érdekességek Schrijver gráfokról

$help$

$Év szerint$	$Hónap szerint$	$Ugrás a hónaphoz$
Év szerint	Hónap szerint	Ugrás a hónaphoz

Simonyi Gábor: Érdekességek Schrijver gráfokról

$iCal fájl letöltése$

$Esemény exportálása$ Esemény exportálása

A leírásban a formázás megtartása (csak néhny naptár alkalmazás támogatja)

Péntek, 25. Április 2025, 10:00 - 11:30

Az SG(n,k) Schrijver gráf csúcsait az [n]={1,2,...,n} halmaz azon k elemű részhalmazai alkotják, melyek nem tartalmaznak ciklikusan szomszédos elemeket, azaz olyanokat, amikben i és i+1 vagy n és 1 egyszerre előfordul.
Két ilyen csúcs akkor van összekötve, ha a megfelelő halmazok diszjunktak.

Ez a gráf feszített részgráfja a KG(n,k) Kneser gráfnak, ami az [n] halmaz összes k elemű részhalmazán van hasonlóan definiálva és amiről Lovász híres eredménye, hogy a kromatikus száma pontosan n-2k+2.

Schrijver Lovász topologikus módszerét használva észrevette, hogy még SG(n,k) kromatikus száma is ugyanennyi, de annak bármely csúcsát elhagyva ez már nem igaz, vagyis SG(n,k) csúcs-színkritikus.

Az előadásban további kritikussági tulajdonságokról lesz szó, például, hogy mely élei lehetnek színkritikusak SG(n,k)-nak, illetve, hogy SG(n,k) milyen feszített részgráfja (csúcs)kritikus a tört kromatikus számra nézve, amely paraméter szintén azonos értéket vesz fel a KG(n,k) és az SG(n,k) gráfokon.

Az eredmények egyik része Tardos Gáborral, másik része Gujgiczer Annával közös.

Hely : Riesz terem

Vissza