Random Structures and Algorithms

该项目研究随机选择的离散数学对象的可能性质。它从美学和计算的角度来处理它们。在许多情况下，对象是网络，该项目旨在了解各种相关参数的典型值。这方面的一个具体例子涉及随机选择的图中最大圈的长度。PI希望解决的一个问题如下：假设我们只从网络中采样，其中每个顶点至少与三条边关联。需要多少条随机边，才能大概率地有一个循环通过每个顶点一次且只有一次，即哈密尔顿循环。作为计算问题的典型例子，考虑如下：网络的边被赋予随机权重，并且人们希望找到最小权重的生成树，即连接网络顶点的一组边。另外，假设边具有随机成本，并且树有不能超过的预算。PI为这一问题提供了一种算法，该算法以极高的概率非常快地找到接近最优解。PI指出，在预算无限的情况下，问题很容易解决，但对于有限的预算，在最坏的情况下，问题很难解决。此外，这个项目为研究生提供了研究培训的机会。该项目处理与有限域上的随机图、超图和矩阵相关的结构和算法问题。PI将试图证明一个具有Cn、C3/2个随机边并且条件为至少具有3个最小度的随机图是高概率哈密顿图。PI将尝试简化稀疏随机图中最长路径长度的渐近表达式。PI将尝试回答这些与随机有向图有关的问题。PI将继续他在随机边加权图中分析最小加权结构的工作，受成本预算的限制。PI将继续他在随机行走方面的工作。PI还将努力改进他在稠密图覆盖时间的确定性估计方面的结果。PI将研究有限域上随机矩阵的秩数，试图从组合的角度解释为什么实际域似乎并不重要。PI还将把二进制情况视为随机拟阵的一个例子。最后，PI将尝试将他对简单粒子扩散过程的分析从一个维度扩展到多个维度。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The project deals with the likely properties of randomly chosen discrete mathematical objects. It deals with them from an aesthetic and a computational angle. In many cases the objects are networks and the project aims to learn the typical values of various associated parameters. One particular example of this concerns the length of the largest cycle in a randomly chosen graph. One question the PI hopes to resolve is the following: suppose we only sample from networks where each vertex is incident with at least three edges. How many random edges are needed so that with high probability there is a cycle that goes through each vertex once and only once i.e. a Hamilton cycle. As a typical example of a computational problem consider the following: the edges of a network are given random weights and one wishes to find a minimum weight spanning tree i.e. a set of edges that connects the vertices of the network. Suppose that in addition, the edges have random costs and there is a budget for the tree that cannot be exceeded. The PI provides an algorithm for this problem that with high probability finds a near optimal solution very quickly. The PI notes that with an infinite budget, the problem is easily solved, but for a finite budget, the problem is hard in the worst-case. In addition this project provides research training opportunities for graduate students.The project deals with structural and algorithmic questions associated with random graphs, hypergraphs and matrices over a finite field. The PI will try to show that a random graph with cn, c3/2 random edges and conditioned to have minimum degree at least three, is Hamiltonian with high probability. The PI will try to simplify our asymptotic expression for the length of the longest path in a sparse random graph. the PI will attempt to answer these questions in relation to random digraphs. The PI will continue his work on analyzing minimum weighted structures in randomly edge weighted graphs, subject to constraints on a cost budget. The PI will continue his work on random walks. the PI will also try to improve his results on deterministic estimates of the covertime of dense graphs. The PI will study the rank of random matrices over finite fields, trying to explain combinatorially why the actual field does not seem to be important. The PI will also consider the binary case as an example of a random matroid. Finally, the PI will try to extend his analysis of a simple particle dispersion process from one to more than one dimension.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.