Group of Discrete Structures

The Group is part of the Applied Mathematics Research Laboratory

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, On-line 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).

Most important long term cooperations: University of Memphis, University of Louisville, Carnegie Mellon University

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), 799-802.

Ahlswede, Alon, Erdos, Ruszinkó and Székely disproved the Ahlswede-Cai-Zhang conjecture which claims that the Erdos-Ko-Rado 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), 127-137.

Ruszinkó and Vanroose gave an optimal code construction for multiple access collision channels with multiplicity feedback; see

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.

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ó, Anti-Ramsey 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) triangle-free 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), 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.

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), 459-467.

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), 255-261.

This is the first part of a two-part part paper establishing basic properties of on-line 3-colorable graphs; see

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.

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), 459-467.