Hírek

VII. Kőnig Dénes diszkrétmatematika-verseny

A Kőnig Dénes Diszkrétmatematika-verseny ezévi fordulóját 2024. április 30-án, kedden rendezzük meg 17:00-tól 19:30-ig, helyszín az IB 025 terem.

Ez a verseny a Számítástudományi és Információelméleti Tanszék által szervezett kari matematikaverseny. Névadója, Kőnig Dénes (Budapest, 1884. szeptember 21. – Budapest, 1944. október 19.) a műszaki egyetem volt tanára, és az első gráfelméleti könyv szerzője.

A versenyen szereplő feladatok a mérnökinformatikus képzés Bevezetés a Számításelméletbe és a villamosmérnök képzés Számítástudomány alapjai kurzusokon oktatott kombinatorikai és gráfelméleti ill. lineáris algebrai alapokra épülnek. Azokat a hallgatókat várjuk a versenyre, akiknek a fenti tárgyak gyakorlatain előkerülő feladatok megoldása és megértése nem okozott különösebb problémát. A feladatok eltérő nehézségűek, többségük kimondottan gondolkodtató. Akárcsak a zh-kon, részpontszámok is szerezhetők, nem csak a kifogástalan megoldásokat értékeljük.

A versenyen bármely VIK-es BSc vagy MSc, illetve TTK-s BSc hallgató részt vehet.

A verseny weboldala, ahol a regisztrációs űrlap is megtalálható: http://www.cs.bme.hu/konig/ [www.cs.bme.hu]

(2024-04-23)

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)

Archívum