The investigator is interested in a wide range of questions from extremal combinatorics and related fields. A common theme is the exploration of new ideas for the construction of extremal objects; in particular, the investigator suggests new ideas for constructions in the settings of Shannon capacity, the lonely runner conjecture, and combinatorial discrepancy. In the area of Shannon capacity, the investigator has developed a new construction for independent sets in the powers of odd cycles that is, in a sense, asymptotically optimal. It is hoped that the algebraic ideas used in this construction can be further developed to give more insight into the Shannon capacities of odd cycles. The investigator suggests a similar algebraic approach to a number of conjectures (conjectures that follow from recent work of R. Holzman, D. Kleitman and the investigator) concerning the extremal objects for the so-called lonely runner conjecture. The research on combinatorial discrepancy is motivated by a conjecture of Lovasz, Spencer and Vestergombi on the relationship between the linear discrepancy and hereditary discrepancy of a hypergraph. In addition to work on new constructions, this research includes questions in the fields of random graphs and the combinatorics of cellular automata.
Questions considered in extremal combinatorics are of the form: `How large (or small) can an object that lies in a particular discrete mathematical system and satisfies a certain condition be?' We are usually interested in the size of extremal objects for very large systems. Interest in such questions grew extensively during the twentieth century. Pioneers of the field, such as Paul Erdos, had posed many fascinating questions of this form and had devised powerful methods for solving them even before the close connections between extremal combinatorics and various other fields (including computer science, statistical physics and information theory) had been discovered. Shannon capacity is a prime example of the significant link between extremal combinatorics and information theory. Shannon capacity gives a measure of the zero-error performance of a noisy communications channel. The investigator has developed new, near--optimal codes for some notoriously difficult channels, and the proposed research includes further development of these codes with the goal of determining the zero-error optimum of these channels. The study of cellular automata has been part of the recent interaction between extremal combinatorics and statistical physics. Cellular automata are discrete dynamical systems that have been used to model a wide range of physical phenomena. The investigator proposes research on the regularity of growth of certain cellular automata that model crystal growth. This work is expected to have impact on our understanding of the shapes achieved by these models and their randomized counterparts.
