with J. DeWitt;
Electronic J. Combin., 23(2) (2016)
We introduce some new classes of words and permutations characterized by the second difference condition $(f(i-1) + f(i+1) - 2f(i) \leq k)$, which we call the $k$-convexity condition. We demonstrate that for any sized alphabet and convexity parameter $k$, we may find a generating function which counts $k$-convex words of length $n$. We also determine a formula for the number of 0-convex words on any fixed-size alphabet for sufficiently large $n$ by exhibiting a connection to integer partitions. For permutations, we give an explicit solution in the case $k = 0$ and show that the number of 1-convex and 2-convex permutations of length $n$ are exponential, and use the transfer matrix method to give tight bounds on the exponential bases.
with J. DeWitt, F. Yang, and Y. Zhang;
DMTCS, 19(2) (2017)
We study a randomized algorithm for graph domination, by which, according to a uniformly chosen permutation, vertices are revealed and added to the dominating set if not already dominated. We determine the expected size of the dominating set produced by the algorithm for the path graph and use this to derive the expected size for some related families of graphs. We then provide a much-refined analysis of the worst and best cases of this algorithm on the graph and enumerate the permutations for which the algorithm has the worst-possible and best-possible performance.