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)
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 "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!
(2024-01-25)
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.
(2024-01-16)
cím :
Budapest, 1117,
Magyar tudósok körútja 2.
I épület, IB132
tel : +36 1 463 2585
fax : +36 1 463 3157
email : Kattintson ide