Griggs 9701211 This award funds further research in extremal combinatorics. In extremal set theory, one can replace the old questions, ``how many sets can one have under the following restrictions'', by new ones, ``how many families of sets can one have under the following restrictions''. The investigators will advance projects in this area of research, which was started by R. Ahlswede et al. with strong motivation from information theory. The investigators will study subset sum distributions of vectors and abelian group elements. This area of knowledge started with the Littlewood-Offord problem and became dependent on extremal set theory. Extensions to higher dimensions suggest tantalizing new problems of fundamental interest. Problems from extremal graph theory the investigators will investigate include: (1) Bounds for the independence ratio in degree-bounded graphs, with restricted maximum clique size, and algorithms for independent sets guaranteed to achieve the bounds. (2) The maximum size of bipartite graphs with given parts under excluded cycle conditions. (3) The maximum size of n-vertex graphs such that no k vertices have more than m edges, continuing work (by Griggs et al.) on generalizations of theorems of Turan and Dirac Szekely recently discovered a connection between crossing numbers of graphs and the Szemeredi-Trotter theorems in combinatorial geometry. The investigators will build on this progress by considering these problems from extremal topological graph theory: (4) Bounds for crossing numbers of graphs. (5) Further investigation of the connection between crossing numbers and combinatorial geometry. (6) Graph drawings, where many pairwise crossing edges are excluded. This is research in extremal combinatorics, a subject at the very core of our understanding of how discrete structures work and how to use them optimally. Significant longstanding open problems are abundant in extremal combinatorics, and new problems frequently come from nearby rapidly d eveloping fields such as information theory, computer science, computational biology, or number theory. Certain database security models require the solution of certain extremal combinatorics problems in order to optimize their performance.
