Diszkrét Struktúrák Csoport

Gráf és hipergráfelmélet

Elméleti és alkalmazott problémák széles skálája tartozik érdeklődési körünkbe. Egyrészt a Magyar Iskola hagyományos irányvonalát folytatjuk ( Ramsey elmélet, Gráfszinezések, Extremális Gráfelmélet ), a szakterület sok kiemelkedő kutatójával együttmüködve. Másrészt Gráfok és Hipergráfok algoritmikus és struktúrális kérdéseinek több területével foglalkozunk, például Hálózatok, Gráftávolságok, Online szinezések, Hipergáf Lefogórendszerek, Helly struktúrák, Intervallumrendszerek területén.

Kombinatorikus Információelmélet

Főirányunk itt a Rényi által inditott megközelités, a Keresés és Kommunikáció elmélet kombinarikus problémái. Speciálisan az utolsó néhány évben az optimális kódkonstrukciók hipergráfelméleti módszereire koncentráltunk, számos eredményt értünk el, sokszor társszerzőkkel (Ahlswede, Alon, Füredi, Tardos).
 

Legfontosabb hosszútávú partnereink: Memphisi Egyetem, Louisvillei Egyetem, Carnegie Mellon Egyetem.
 

Az elmúlt években a következo eredményeket nyerték a csoport tagjai.

Füredi és Ruszinkó exponenciálisan megjaví tották a szuperponált kódokra vonatkozó becsléseket. Milman eredményeit felhasználva az eredményeket kiterjesztették általános metrikus terekre.

Z. Füredi, M. Ruszinkó, An improved upper bound of the rate of Eucledian superimposed codes, IEEE Transactions on Information Theory, Vol. 45(2) (1999), 799-802.

Ahlswede, Alon, Erdos, Ruszinkó és Székely megcáfolták az Ahlswede-Cai-Zhang sejtést mely szerint az EKR tétel igaz rendszerekre is.

R. Ahlswede, N. Alon, P. L. Erdos and M. Ruszinkó, L. A. Székely, Intersecting systems, Combinatorics, Probability & Computing, Vol. 6(2) (1997), 127-137.

Ruszinkó és Vanroose optimális kódot konstruáltak többszörös hozzáférésu ütközéses csatornákhoz.

M. Ruszinkó and P. Vanroose, How an Erdos-Rényi type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback, IEEE Transactions on Information Theory, Vol. 43(1) (1997), 368-373.

Véges geometriai konstrukciókat alkalmazva - Blokhuis, Faudree, Gyárfás és Ruszinkó - általánosí tották Körner és Simonyi többfordulós élszinezési eredményeit.

A. Blokhuis, R. Faudree, A Gyárfás, M. Ruszinkó, Anti-Ramsey colorings in several rounds, Journal of Combinatorial Theory -B, accepted.

(Alon) Erdos, Gyárfás és Ruszinkó éles korlátok közé szorí tották a gráfok átmérojét csökkento minimális élszámot (korlátos fokszám) háromszögmentesség esetén.

N. Alon, A. Gyárfás, M. Ruszinkó, How to add edges to get graphs of small diameter, Journal of Graph Theory, Vol. 35(3) (2000), 161-172, and

P. Erdos, A. Gyárfás, M. Ruszinkó, How to decrease the diameter of triangle-free graphs, Combinatorica, Vol. 18(4) (1998), 493-501.

Sok új cikk született az itt Erdos és Gyárfás által bevezetett irányvonal mentén.

P. Erdos, A. Gyárfás, A variant of the classical Ramsey problem, Combinatorica, Vol. 17(4) (1997), 459-467.

Split és Ramsey gráfokat is tartalmazó újfajta kritikus gráfok kerültek bevezetésre.

A. Gyárfás, Generalized split graphs and Ramsey numbers, Journal of Combinatorial Theory.-A, Vol. 81(2) (1998), 255-261.

Meghatároztuk az on-line 3-szinezheto gráfok alapveto tulajdonságait.

A. Gyárfás, Z. Király, J. Lehel, On-line 3-chromatic graphs I. Triangle-free graphs, SIAM J. Disc. Math, Vol. 12(3) (1998), 385-411.

Szomorú alkalom Erdos Pál emlékkötetbe publikálni, mely Erdös utolsó munkáit hivatott leközölni.

P. Erdos, A. Gyárfás, Split and balanced colorings of complete graphs, Discrete Math, Vol. 17(4) (1997), 459-467.