Calendar

Mar
31
Tue
Student Seminar: Yiguang Zhang @ Whitehead 304
Mar 31 @ 3:00 pm – 4:00 pm
Total Acquisition Number of Randomly Weighted Paths

There exists a significant body of work on determining the acquisition number of various graphs when the vertices of those graphs are each initially assigned a unit weight. We study the size of residual set of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number of the $n$-path when n “units” of integral weight, or chips, are randomly distributed across its vertices between $0.26n$ and $0.43n$. We then use Azuma’s Lemma to prove that this expected value is tightly concentrated. Additionally, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and compute the expected size of the resultant residual set.​

Back to top