Combinatorial Quasirandomness and its Applications

University South Carolina Research Foundation, Columbia SC

Investigators

Abstract

The PI will study combinatorial quasirandomness, a subject with maturing connections to combinatorial uniformity/regularity, numerical integration, discrepancy, derandomization, discrete harmonic analysis, and Markov chain theory. "Quasirandomness" is a broad term referring to situations where combinatorial objects -- e.g., graphs, hypergraphs, lattice walks, permutations, subsets of groups -- resemble random objects of their class with respect to some set of statistics. Central goals of the project are to prove tight bounds on the discrepancy of several proposed quasirandom constructions, explore new quasirandom analogues of well-known probabilistic processes, and develop theory to describe implicative hierarchies of quasirandom properties. The investigator will further analogize and extend the very useful relationships between quasirandomness and uniformity/regularity already well understood for graphs, hypergraphs, permutations, and abelian groups. He will also study applications of quasirandomness to graph algorithms (e.g., network routing), coding theory (e.g., liar games), and numerical integration (e.g., walk-on-spheres Monte Carlo simulation). Probabilistic intuition has been a powerful and influential tool in the past half-century of mathematics, computer science, and physics. Surprisingly often, the best known solution to a problem arises from constructions that involve some amount of randomness. Probability theory has lent a decisive perspective on many theoretical questions, particularly in discrete mathematics, the realm of finite objects, relationships, and computations. Despite the extraordinary success of probabilistic methods, however, such approaches face a few serious shortcomings when implemented in real-world applications. First, they do not offer explicit solutions, but only ensure the desired properties with some positive probability. Second, "true" randomness is costly and time-consuming to obtain, as the physical universe behaves with consummate predictability on all but the tiniest scales. Lastly, sometimes, the fluctuations which inevitably accompany randomness prevent solutions from being completely optimal. One remedy to such deficiencies is to imitate -- or even improve upon -- useful aspects of randomness by carefully designed deterministic processes. Constructions which resemble random ones according to particular measurements are known as "quasirandom". Research on quasirandomness can provide guaranteed explicit constructions, obviate the need for randomness, and sometimes yield solutions that have even better properties than random constructions. The PI will continue his work on this subject, as well as continuing to mentor graduate and undergraduate students and organize meetings at the local, regional, and national levels to share ideas between researchers of related areas.