Proposal Number: DMS 9803780 PI: James Allen Fill Institution: The Johns Hopkins University Project: Probability and Combinatorial Structures Abstract: The theme of the this research is the study of certain important combinatorial structures using probabilistic methods. One important class of structures is that of self-organizing data structures, which dynamically maintain a file of records in easily retrievable order while using up little memory space and which have been investigated by probabilists and computer scientists for more than 25 years. Such self-organizing systems have been applied to problems in very large-scale integration (VLSI) circuit simulation, data compression, communications networks, and genetics. The research analyzes more realistically complex probability models than have heretofore been treated, and in doing so provides a unifying framework for previous studies. Trees form another important class of combinatorial structures. The investigator analyzes the "shape" of random m-ary search trees, fundamental structures in computer science that also arise naturally in connection with self-organizing data structures. The work involves generalizing and analyzing the already large class of recursive trees, which have been used to model such things as the spread of epidemics, family trees of ancient manuscripts, and pyramid schemes. The researcher also develops a continuous-time model for pyramid schemes and derives for it operational characteristics which have not been obtained under the corresponding discrete-time model. Another facet of this work is a generalization of the analysis of the height of an incomplete digital search tree, or trie; the generalization has applications to the election of multiple leaders in a computer network. This work relates clearly to the Federal Strategic Area of high-performance computing and communi cation.
