Some Problems on Pseudo-Random Structures in Discrete Mathematics

离散数学中伪随机结构的一些问题

• 批准号: 0603745
• 负责人: Janos Komlos
• 金额: --
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0603745&HistoricalAwards=false
• 关键词: Some; Problems; Pseudo; Random; Structures

Various structures in graph theory and number theorycapture pseudo-randomness by small excluded substructures.Conversely, truly random matrices introducestatistical structure (e.g., Wigner's Semi-Circle Law).The proposal addresses these general phenomenathrough three specific classes of problems:graph problems with certain excluded subgraphs(small cliques or trees), number theory problemsabout sum-free sequences of integers,and various structural theorems for random matrices.The proposed topics are applicable in mathematics and the sciences.In particular, the graph problems may find applicationsin Fourier analysis (and hence in Communications Technology),in Discrete Geometry (and hence in Robotics),in Number Theory (and hence in Coding Theory),and in designing and analysing efficientcomputer algorithms (Complexity Theory).Random matrices have their most notable applicationsin Mathematical Physics, but they are also very importantin a broad range of sciences and several branches of mathematicsfrom Multivariate Statistics to Operations Researchto Bioinformatics to Learning Theory-- just to mention some important ones.

图论和数论中的各种结构通过小的排除子结构来捕获伪随机性。相反，真正的随机矩阵引入了统计结构（例如，Wigner的半圆定律）。该提案通过三个特定类别的问题来解决这些普遍现象：具有某些排除子图的图问题（小集团或树），关于整数的无和序列的数论问题，以及随机矩阵的各种结构定理。所提出的主题适用于数学和科学。特别是，图形问题可能在傅立叶分析中找到应用（因此在通信技术），在离散几何（因此在机器人学中），在数论中（因此在编码理论中也是如此），and in designing设计and analyzing分析efficient有效computer计算机algorithms算法（复杂性理论）随机矩阵在数学物理学中有其最显著的应用，但它们在广泛的科学和数学的几个分支中也非常重要，从多元统计到运筹学，到生物信息学，再到学习理论--只是提到一些重要的。