Combinatorics with Applications

University Of South Carolina At Columbia, Columbia SC

Investigators

Abstract

COMBINATORICS WITH APPLICATIONS Jerrold R. Griggs and Laszlo A. Szekely The proposers seek results in extremal combinatorics that exhibit structures which are key to applications, or which provide bounds on what can be achieved by any algorithm. The proposers will search for a profitable crossover of ideas and methods, including applications of algebraic and analytic tools. The particular problems include * improving current bounds on the maximum concentration of subset sums of vectors, especially for problems arising from models of database security * finding better algorithms for graph drawing, developing the theory of crossing numbers of graphs, and working out further applications of of the theory to geometric problems * developing robust algorithms for reconstructing very large phylogenetic trees, and analyzing conditions necessary for reconstruction, with attention to models where the i.i.d. property fails * completing the solution of maximum non-spanning sets in finite abelian groups * advancing the study of algorithms for large independent sets in graphs of given maximum degree and clique size * classifying graph subdivision problems which admit small threshold function * leading the development of the theory of graph labellings spawned by the problem of optimal channel assignments with multiple levels of interference Research in combinatorics and graph theory is proposed in a wide variety of areas, including those that arise in such rapidly developing fields as computer science, computational biology, and number theory. Problems arise at the very core of our understanding of how discrete structures work and how to use them optimally. Among the questions they will study are these: * How can one optimize public access to a statistical database (containing, say, salaries of a department's employees) by maximizing the number of queries, each one asking for the average salary of some collection of the employees, that can be answered without compromising the salary of any individual? * Given corresponding aligned segments of the DNA sequences of many biological taxa (or species), how does one build large phylogenetic trees reflecting their true evolutionary relationship? * How can one draw a very large network such that the viewer can grasp it from a clear drawing? * How can the frequency spectrum span alloted to a network of transmitters (radio stations, mobile phones, etc.) be minimized, such that channels assigned to nearby transmitters must avoid interference? * What is an efficient method to select a large number of transmitters, no two close together, given a network and information bounding the complexity of the network? Fundamental problems of this kind arise in many settings. Involvement of graduate students in research on these problems will enable the investigators to continue their successful training program for careers in industry, government, and academia.