Kombinatorikus informatika = Combinatorial Computer Science

Ruszinkó, Miklós (2006) Kombinatorikus informatika = Combinatorial Computer Science. Project Report. OTKA.

Preview

PDF 38198_ZJ1.pdf Download (90kB)

Abstract

A [1, 3, 4, 7-9, 13, 14] eredmények közvetlenül kódokhoz kapcsolódnak. A [7, 9, 3] dolgozatokban bevezettük az egy felhasználót meghatározó superimposed kódokat, majd Alon és Körner eredményeit felhasználva sikerült kód korlátokat kapni. Vizsgáltuk az identifying kódókat véletlen gráfokban [1,8]. Itt (1 valószínüséggel) éles korlátokat kaptunk a minimális kód méretére. A kódokhoz kapcsolódó Turán rendszereket írtunk le a The CRC Handbook of Combinatorial Designs-ba [13]. Ezen kívül könyvet írunk a többszörös hozzáférésű csatornák kódolásáról, 250 oldal elkészült. A kódok korrelációs tulajdonságaihoz kapcsolódó véletlen metsző halmaz-rendszerek tulajdonságait (1 valószínüséggel) leírtuk adott részhalmaz méreten belül [5,6]. Az elméleti informatikában nagyon fontos Ramsey problémákat vizsgáltunk [2,10-12]. A Szemerédi lemma segítségével néhány régi Ramsey típusú nyitott problémát sikerült megoldani. Meghatároztuk az utak Ramsey számát pontosan három szín esetén (több, mint 25 éven át volt nyitott probléma), a körfedési számot pontosítottuk és teljes páros gráfok Ramsey szinezéseit is vizsgáltuk. | Our results in [1, 3, 4, 7-9, 13, 14] are related to codes. In [7, 9, 3] we introduced the single user tracing superimposed codes and using results of Alon, Körner we gave bounds on their minimum length. We investigated identifying codes in random graphs [1, 8]. We obtained (with probability 1) tight bounds on the minimum size of the code. We described the Turán systems related to codes [13]. We are writing a book on coding of multiple access channels, 250 pages are ready. The related to correlation properties of codes, random intersecting systems were described (with probability 1) in [5, 6] up to a certain subset size. We investigated some Ramsey problems [2,10-12] which in general are very important in theoretical computer science. Using the Szemerédi lemma we managed to solve some long standing open Ramsey problems. We determined exactly the Ramsey number of paths in case of three colors (this problem was open for more than 25 years), narrowed the bounds on cycle partition number and we also investigated the Ramsey colorings of bipartite graphs.

Actions (login required)

Edit Item