|
|
|
|
|
|
|
|
Év szerint | Hónap szerint | Ugrás a hónaphoz | |
|
|
Pluhár András: Néhány hipergráf paraméter |
|
|
|
|
Péntek, 23. Szeptember 2016, 10:00 - 12:00
|
|
Absztrakt. Egy H=(V, E) hipergráf halmazrendszer a V felett. Egy X részhalmaza V-nek fedés (vagy transzverzális) ha minden E-beli halmazt metsz. Ezek minimális méretére vonatkozott Tuza egy kérdése, melyet Noga Alon 1990-ben (aszimptotikusan) megválaszolt. A kérdés és a válasz is lényegében ugyanaz, mint minimális dominálóhalmazt keresni egy d minimális fokú gráfban.
A másik paraméter a kromatikus szám, pontosabban a 2-színezhetőség. Erdős klasszikus bizonyítása visszavezethető Alon tételére ill. valamilyen értelemben fordítva is érdekes a visszavezetés. |
|
Hely : Bolyai Intézet, I. emelet, Riesz terem, Aradi Vértanúk tere 1., Szeged |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013
Esemény exportálása