HUN-REN Számítástechnikai és Automatizálási Kutatóintézet
projekt kezdete
2002-01-01
projekt vége
2005-12-31
aktuális összeg (MFt)
2.217
FTE (kutatóév egyenérték)
0.00
állapot
lezárult projekt
Zárójelentés
kutatási eredmények (magyarul)
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.
kutatási eredmények (angolul)
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.
M. Csűrös and M. Ruszinkó: Single user tracing superimposed codes, Proceedings 2004 International Symposium on Information Theory (ISIT), June 27-July 2, 2004, Chicago, Illinois, page 255. IEEE, Piscataway NJ. ISBN 0-7803-8280-3, 2004
T. Bohman, C. Cooper, A. Frieze, R. Martin, M. Ruszinkó: On Randomly Generated Intersecting Hypergraphs, Electronic Journal of Combinatorics, Vol. 10 (2003), #R29, 2003
Z. Füredi, M. Ruszinkó: Large Convex Cones in Hypercubes, Discrete Applied Mathematics (közlésre elfogadva), 2006
T. Bohman, A. Frieze, R. Martin, M. Ruszinkó, C. Smyth: On Randomly Generated Intersecting Hypergraphs II, Random Structures and Algorithms (közlésre benyújtva), 0
M Csűrös and M. Ruszinkó: Single-user tracing and disjointly superimposed codes, IEEE Transactions on Information Theory, Vol. 51(4) (2005), 1606-1611, 2005
A. Gyárfás, M. Ruszinkó, G. Sárközy, E. Szemerédi: Tripartite Ramsey numbers for paths, Combinatorica (közlésre elfogadva), 2006
A. Frieze, R. Martin, J. Moncel, M. Ruszinkó, C. Smyth: Identifying Codes in Random Networks, Proc. of 2005 IEEE International Symposium on Information Theory, 4-9 September, Adelaide, Australia, ISBN 0-7803-9151-9/05, pp. 1464-1467., 2005
A. Gyárfás, M. Ruszinkó, G. Sárközy, E. Szemerédi: An improved bound for the monochromatic cycle, Journal of Combinatorial Theory, Series B (közlésre elfogadva), 2006
M. Ruszinkó: Turán Systems, The CRC Handbook of Combinatorial Designs, 2nd Edition, CRC Press (közlésre elfogadva), 2006
A. Gyárfás, M. Ruszinkó, G. Sárközy, E. Szemerédi: One-sided coverings of colored complete bipartite graphs, Volume dedicated to J. Nesetril's 60th birthday, Springer (közlésre elfogadva), 2006
A. Gyárfás, M. Ruszinkó, G. Sárközy, E. Szemerédi: Tripartite Ramsey numbers for paths, Journal of Graph Theory, Series B (közlésre benyújtva), 0
A. Frieze, R. Martin, J. Moncel, M. Ruszinkó, C. Smyth: Codes identifying sets of vertices in random networks, Discrete Mathematics (közlésre benyújtva), 0
L. Györfi, S. Győri, B. Laczay, M. Ruszinkó: Multiple Access Channels, NATO series, 250 oldal (75%) készen, 0
B. Laczay, M. Ruszinkó: Multiple user tracing codes, 2006 IEEE International Symposium on Information Theory (közlésre benyújtva), 0
