Discrete Random and Pseudorandom Structures

离散随机和伪随机结构

• 批准号: 2054503
• 负责人: Wesley Pegden
• 金额: $ 21万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2054503&HistoricalAwards=false
• 关键词: Discrete; Random; Pseudorandom; Structures

This project aims to better understand random and pseudorandom processes, and the interplay between them. In particular, the project studies models from statistical physics of aggregation processes built on both random and pseudorandom walks. For example, in the former case, diffusion limited aggregation processes produce intricate fractals through processes analogous to those that drive the formation of corals, but the propensity of these processes to give rise to long, spiny, structures is still not rigorously understood. In the latter case, the Abelian sandpile process builds a cluster of particles through a pseudorandom distribution of particles that ends up giving rise to intricate fractal patterns, as well as statistical laws which reappear throughout nature (e.g., as the frequency distributions of earthquakes, avalanches, etc).Among other goals, this project aims to better understand the dependence of the behavior of the Abelian sandpile on the underlying lattice. One particularly interesting case is that where a periodic lattice is subjected to random edge-deletions; in this case the Abelian sandpile is a pseudorandom aggregation process on a random environment, which we expect to behave like a random aggregation process on a periodic environment. Other topics include work on Euclidean functionals; in particular, refining our understanding of asymptotic relationships between structures like Traveling Salesperson Tours through typical (i.e. random) point sets, and their algorithmic approximations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

这个项目旨在更好地理解随机和伪随机过程，以及它们之间的相互作用。 特别是，该项目研究了建立在随机和伪随机游动基础上的聚合过程的统计物理模型。例如，在前一种情况下，扩散限制聚集过程通过类似于驱动珊瑚形成的过程产生复杂的分形，但这些过程产生长刺结构的倾向仍然没有得到严格的理解。 在后一种情况下，阿贝尔沙堆过程通过粒子的伪随机分布建立粒子簇，最终产生复杂的分形图案，以及在整个自然界中重现的统计定律（例如，如地震、雪崩等的频率分布）。除其他目标外，该项目旨在更好地理解阿贝尔沙堆的行为对底层晶格的依赖性。 一个特别有趣的情况是，周期性晶格受到随机边缘删除;在这种情况下，阿贝尔沙堆是随机环境中的伪随机聚集过程，我们期望其表现得像周期性环境中的随机聚集过程。 其他主题包括欧几里德泛函的工作;特别是，通过典型（即随机）点集，以及它们的算法近似，完善我们对旅行推销员图尔斯等结构之间渐近关系的理解。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

Multitrees in random graphs

随机图中的多树

• 发表时间: 2023
• 期刊: The Electronic journal of combinatorics
• 作者: Frieze, A.;Pegden, W.
• 通讯作者: Pegden, W.

Spanners in randomly weighted graphs: independent edge lengths

随机加权图中的扳手：独立的边长

• 发表时间: 2022
• 期刊: Discrete applied mathematics
• 影响因子: 1.1
• 作者: Frieze, A.;Pegden, W.
• 通讯作者: Pegden, W.

Spanners in randomly weighted graphs: Euclidean case

随机加权图中的扳手：欧几里得案例

• DOI: 10.1002/jgt.22950
• 发表时间: 2023
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Frieze, Alan;Pegden, Wesley
• 通讯作者: Pegden, Wesley

Subexponential mixing for partition chains on grid-like graphs

网格图上分区链的次指数混合

• 发表时间: 2023
• 期刊: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Frieze, Alan;Pegden, Wesley
• 通讯作者: Pegden, Wesley