Combinatorics with Applications

组合学与应用杰罗尔德·r·格里格斯和拉斯洛·a·谢克利两位作者寻求极值组合学的结果，这些结果展示了对应用至关重要的结构，或者提供了任何算法可以实现的界限。提议者将寻找思想和方法的有益交叉，包括代数和分析工具的应用。具体的问题包括*改进向量子集和的最大集中的当前边界，特别是数据库安全模型引起的问题*找到更好的图形绘制算法，发展图的交叉数理论，并研究出该理论在几何问题中的进一步应用*开发用于重建非常大的系统发育树的鲁棒算法；并分析重建所需的条件，关注了i.i.d性质不成立的模型*完成了有限阿贝尔群中最大非生成集的求解*推进了给定最大度和团大小的图中大独立集算法的研究*对允许小阈值函数的图细分问题进行了分类*引领了由多级最优信道分配问题衍生的图标记理论的发展许多领域都提出了对组合学和图论的研究，包括那些在计算机科学、计算生物学和数论等快速发展的领域中出现的研究。问题出现在我们对离散结构如何工作以及如何最佳地使用它们的理解的核心。他们将研究的问题包括：*如何通过最大化查询的数量来优化公共访问统计数据库（例如，包含一个部门员工的工资），每个查询都要求某些员工集合的平均工资，而这些查询可以在不损害任何个人工资的情况下得到回答？*给定许多生物类群（或物种）对应的DNA序列片段，如何构建反映它们真正进化关系的大型系统发育树？*一个人怎样才能画出一个非常大的网络，使观众能够从清晰的图纸中掌握它？*如何将分配给发射机（无线电台、流动电话等）网络的频谱范围减至最小，以使分配给附近发射机的频道必须避免干扰？*在给定网络和信息限制网络复杂性的情况下，选择大量发射机，且没有两个发射机紧密相连的有效方法是什么？这类基本问题在许多情况下都会出现。研究生参与对这些问题的研究将使研究人员能够继续他们在工业、政府和学术界的职业生涯中成功的培训计划。

COMBINATORICS WITH APPLICATIONS Jerrold R. Griggs and Laszlo A. SzekelyThe 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 interferenceResearch 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 careersin industry, government, and academia.