Ramsey Theory, Hypergraph Coloring, and Structural Problems in Graph Theory

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

9970325 Professor Mubayi plans to undertake research in graph theory with emphasis on Ramsey theory, hypergraph coloring, connectivity of cages, and graph covering. The main thrust of his project is to study variations of problems in Ramsey Theory posed by Paul Erdos. He will also develop the coloring theory of mixed hypergraphs, investigate the connectivity properties of cages, and study a new problem related to graph covering. The proposed research falls into the general area of combinatorics. One of the goals of combinatorics is to find efficient methods to study arrangements of objects. These methods are extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems or internet providers, deal with finite sets of objects and require combinatorial analysis. Ramsey theory studies the conditions under which certain substructures in a discrete setting are forced to appear. It has applications to efficient information retrieval, to clear communication with noisy channels, and to the effect of failure of intermediate facilities in a communication network.