Some Problems on Pseudo-Random Structures in Discrete Mathematics

点击翻译按钮获取中文摘要

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.