A következő kombinatorika szeminárium ideje

helye a szokásossá váló

és előadása:

Egy műszaki probléma bizonyos megoldásait és általánosításait viszgáljuk. Ha adott egy G gráf (hálózat) akkor az jó eséllyel így is van, és a legrosszabb esetben is legfeljebb egy éle hibásodik meg. Tegyük fel, hogy meg akarjuk találni a hibás élt (ha van ilyen). A legegyszerűbb, de elég költséges megoldás végignézni az összes élt. Egy másik megközelítés, hogy a G gráf H₁, ..., H_k részgráfjait tekintjük, és tegyük fel, hogy egy lépésben el tudjuk dönteni, hogy egy H_i összes éle működik-e. H₁, ..., H_k teszthalmaz, ha ebből kitalalható, hol a hibás él.

Kicsit erősebb definíció: H₁, ..., H_k szeparáló, ha bármely e, f élekre (rendezett párkent tekintve) van olyan i, hogy e eleme H_i-nek, f pedig nem eleme H_i-nek.

A teszt (szeparáló) halmazok elemszámát minimalizálni szeretnénk. Ezekre különböző feltételek mellett adódnak alsó és felső korlátok. Az egyik legérdekesebb kérdés talán az, utakkal akarunk szeparálni. Kialakult egy általánosnak tűnő sejtés: van olyan K konstans, hogy bármely G szeparálható Kn úttal, ahol n a G gráf pontszáma.

Az előadás közös eredményeken alapul, melyben Balogh József, Csaba Béla és Ryan Martin vett meg részt.

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

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073, Telemedicine Oriented Research in the Fields of Mathematics, Informatics and Medical Sciences