
 

Group of Discrete Structures  
Contact 
The Group is part of the Applied Mathematics Research Laboratory  
Research Areas 
Graph and Hypergraph Theory We are interested in a wide range of theoretical and applied problems. On one hand we continue traditional directions of the Hungarian School (Ramsey Theory, Graph Coloring, Extremal Graph Theory) where we collaborate with many outstanding researchers of the area, including Paul Erdos, with whom we published fifteen joint papers. One the other hand we work in several areas of structural and algorithmic Graph and Hypergraph Theory (Networks, Graph Distances, Online colorings, Hypergraph Transversals, Helly structures, Interval systems). Combinatrial Information Theory Our main direction here continues the approach initiated by Renyi, toconsider combinatorial problems coming from Communication Theory, Search Theory. In particular, in the last few years we concentrated on applications of hypergraph theoretic methods for optimal code constructions and achieved several results, many with coauthors (Ahlswede, Alon, Furedi, Tardos).  
Cooperations 
Most important long term cooperations: University of Memphis, University of Louisville, Carnegie Mellon University  
A few results of the last five years 
In the last few years the following results were obtained by the members of our group. Füredi and Ruszinkó improved the best known bounds on the rate of Euclidean Superimposed Codes. They also managed to extend those results  using a basic theorem of Millman  to arbitrary metric spaces; see 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), 799802.
Ahlswede, Alon, Erdos, Ruszinkó and Székely disproved the AhlswedeCaiZhang conjecture which claims that the ErdosKoRado theorem can be generalized to intersecting set systems, too; see R. Ahlswede, N. Alon, P. L. Erdos and M. Ruszinkó, L. A. Székely, Intersecting systems, Combinatorics, Probability & Computing, Vol. 6(2) (1997), 127137.
Ruszinkó and Vanroose gave an optimal code construction for multiple access collision channels with multiplicity feedback; see M. Ruszinkó and P. Vanroose, How an ErdosRé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), 368373.
Using constructions based on finite geometries  Blokhuis, Faudree, Gyárfás Ruszinkó  managed to generalize results of Körner and Simonyi on edge colorings of subgraphs of the complete graph in multiple rounds; see A. Blokhuis, R. Faudree, A Gyárfás, M. Ruszinkó, AntiRamsey colorings in several rounds, Journal of Combinatorial Theory B, accepted.
(Alon) Erdos, Gyárfás and Ruszinkó gave tight bounds for the minimum number of edges to be added to decrease the diameter of (bounded degree) trianglefree graphs; see 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), 161172, and P. Erdos, A. Gyárfás, M. Ruszinkó, How to decrease the diameter of trianglefree graphs, Combinatorica, Vol. 18(4) (1998), 493501.
There are many publications continuing the directions started in the following paper of Erdos, Gyárfás; P. Erdos, A. Gyárfás, A variant of the classical Ramsey problem, Combinatorica, Vol. 17(4) (1997), 459467.
A new type of critical graphs is introduced containing split and Ramsey graphs; see A. Gyárfás, Generalized split graphs and Ramsey numbers, Journal of Combinatorial Theory.A, Vol. 81(2) (1998), 255261.
This is the first part of a twopart part paper establishing basic properties of online 3colorable graphs; see A. Gyárfás, Z. Király, J. Lehel, Online 3chromatic graphs I. Trianglefree graphs,SIAM J. Disc. Math, Vol. 12(3) (1998), 385411.
It is a sad opportunity to publish a paper in the memorial volume of Discrete Mathematics which collected the last works of late Paul Erdos; see
P. Erdos, A. Gyárfás, Split and balanced colorings of complete
graphs,
Discrete Math, Vol. 17(4) (1997), 459467.
 