Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Random Walks, Number Partitioning, and Regular Graphs

Pan, Amanda
http://rave.ohiolink.edu/etdc/view?acc_num=osu1692604574588542

Abstract Details

2024, Doctor of Philosophy, Ohio State University, Mathematics.
We present three projects related to random walks. Consider a random walk $S_n = \sum_{i=1}^n a_i x_i$ where $A=\{a_1,\dots,a_n\}$ are integers and $x_i$ are independent variables that are $\pm 1$ with probability $1/2$. First, we prove various inverse Littlewood--Offord theorems, showing that if there is a high probability that $S_n$ is a particular number, then $A$ has additive structure. This $S_n$ can also be used to state the optimal partitioning problem of partitioning $A$ into two subsets whose sums are as close as possible. We prove a phase transition in the event that this minimum discrepancy is at most 1, for when the $a_i$ are drawn iid from some discrete distribution. We also find the limiting distribution of the discrepancies near 0, generalizing several results of Borgs, Chayes, and Pittel. Finally, we bound the probability that the adjacency matrix of a random $d$-regular digraph on $n$ vertices is singular by $n^{-1/3+o(1)}$, improving a bound by Huang. To do this, we study the probability that the matrix is singular over the finite field $\F_p$.
Hoi Nguyen (Advisor)
James Jontes (Committee Member)
Caroline Terry (Committee Member)
David Sivakoff (Committee Member)
Mathematics

Recommended Citations

Citations

  • Pan, A. (2024). Random Walks, Number Partitioning, and Regular Graphs [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1692604574588542

    APA Style (7th edition)

  • Pan, Amanda. Random Walks, Number Partitioning, and Regular Graphs. 2024. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1692604574588542.

    MLA Style (8th edition)

  • Pan, Amanda. "Random Walks, Number Partitioning, and Regular Graphs." Doctoral dissertation, Ohio State University, 2024. http://rave.ohiolink.edu/etdc/view?acc_num=osu1692604574588542

    Chicago Manual of Style (17th edition)

osu1692604574588542
309
© , all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.
Release 3.2.12