Hírek

Tanszéki szeminárium

Március 26-án, kedden 14:15-től az IB134-ben Gujgiczer Anna fog beszélni, előadásának címe
"Schrijver-gráfok frakcionális kromatikus számra kritikus részgráfjai".

Bővebben:

A KG(n,k) Kneser-gráf csúcsai egy n elemű halmaz k elemű részhalmazai (ahol n legalább 2k), két csúcs pedig akkor szomszédos, ha a megfelelő részhalmazok diszjunktak. Nem nehéz olyan színezést mutatni erre a gráfra, ami csak n-2k+2 színt használ, azonban Kneser sejtését, hogy kevesebb szín nem lehet elég, sokkal nehezebbnek bizonyult belátni. Több mint 20 évvel a sejtés megjelenése után, Lovász Lászlónak sikerült megmutatnia, hogy az n-2k+2 egy alsó korlát is a kromatikus számra. Nem sokkal később Schrijver észrevette, hogy ennek a gráfnak már egy speciális feszített részgráfját sem lehet kevesebb színnel színezni és ez a részgráf csúcskritikus is a kromatikus számra, vagyis bármely csúcs törlésével a kromatikus szám csökken. Ezt a részgráfot nevezik azóta SG(n,k) Schrijver-gráfnak.

Egy másik gráfparaméterre, a frakcionális kromatikus számra (másik nevén tört kromatikus számra) is igaz, hogy a KG(n,k) Kneser-gráfra és az SG(n,k) Schrijver-gráfra megegyezik, értéke n/k. Viszont erre a paraméterre sem a Kneser-, sem a Schrijver-gráf nem kritikus. Ebben az előadásban a Schrijver-gráfoknak egy olyan feszített részgráfját fogjuk megismerni, aminek a frakcionális kromatikus száma ugyanez az érték, viszont csúcskritikus is erre a paraméterre nézve.

(2024-03-22)

Palincza Richárd házi védése

Palincza Richárd "Leszámlálási és extremális problémák az aritmetikai kombinatorikában" című doktori dolgozatának házi védése 2024. február 6-án 14:15-kor lesz az IB134-ben.

Minden érdeklődőt szeretettel várunk!

Tézisfüzet

(2024-01-25)

Demonstrátorok jelentkezését várjuk!

Tanszékünk demonstrátorok jelentkezését várja a tavaszi féléves Bevezetés a számításelméletbe 2., Algoritmuselmélet, Valószínűségszámítás (üzemmérnök informatikus képzés) tárgyak gyakorlatainak megtartására, továbbá a Rendszeroptimalizálás tárgy zhinak javítására. A jelentkezés határideje 2024. január 31., de kérjük, hogy jelentkezési szándékukat minél előbb jelezzék.

A jelentkezés részletei

(2024-01-16)

Recski András kitüntetése

A Kari Tanács döntése alapján Pro Facultate díjban részesült Recski András, tanszékünk korábbi tanszékvezetője.

Gratulálunk!

Kari hír

(2024-01-05)

Archívum