Georgia Institute of Technology College of Sciences

Flajolet and Odlyzko (1990) derived asymptotic formulae for the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Gao and Richmond (1992) and Hwang (1996, 1998), in both cases by reducing the multivariate case to the univariate case. Pemantle and Wilson (2013) outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions. In this talk, we discuss these multivariate analytic techniques and use them to find asymptotic formulae for the coefficients of a broad class of bivariate generating functions with algebraic singularities. We will also look at how to apply such formulae to practical problems.

In the Rendezvous problem on the complete graph, two parties are trying to meet at some vertex at the same time, despite starting out with independent random labelings of the vertices. It is well known that the optimal strategy is for one player to wait at any vertex, while the other visits all n vertices in consecutive steps, which guarantees a rendezvous within n steps and takes (n + 1)/2 steps on average. This strategy is very far from being symmetric, however. E. Anderson and R. Weber presented a symmetric algorithm that achieves an expected meeting time of 0.829n, which has been conjectured to be optimal in the symmetric setting. We change perspective slightly: instead of trying to minimize the expected meeting time, we try to maximize the probability of successfully meeting within a specified number of timesteps. In this setting, for all time horizons that are linear in n, the Anderson-Weber strategy has a constant probability of failure. Surprisingly, we show that this is not optimal: there exists a different symmetric strategy that almost surely guarantees meeting within 4n timesteps. This bound is tight, in that the factor 4 cannot be replaced by any smaller constant. Our strategy depends on the construction of a new kind of combinatorial object that we dub”rendezvous code.”On the positive side, for T < n, we show that the probability of meeting within T steps is indeed (approximately) maximized by the Anderson-Weber strategy. Our results imply new lower bounds on the expected meeting time for any symmetric strategy, which establishes an asymptotic difference between the best symmetric and asymmetric strategies. Finally, we examine the symmetric rendezvous problem on other vertex-transitive graphs.

I will find upper and lower bounds for the mixing time as well as the likelihood order after sufficient time of the following involution walk on the symmetric group. Consider 2n cards on a table. Pair up all the cards. Ignore each pairing with probability $p \geq 1/2$. For any pair not being ignored, pick up the two cards and switch their spots. This walk is generated by involutions with binomially distributed two cycles. The upper bound of $\log_{2/(1+p)}(n)$ will result from spectral analysis using a combination of a series of monotonicity relations on the eigenvalues of the walk and the character polynomial for the representations of the symmetric group. A lower bound of $\log_{1/p}$ differs by a constant factor from the upper bound. This walk was introduced to study a conjecture about a random walk on the unitary group from the information theory of black holes.

Characters are a central tool for understanding arithmetic. For example, the most familiar character is the Legendre symbol, which detects the quadratic residues. In this talk I will present a few ideas as to how character sums may be useful in arithmetic combinatorics and vice versa. Traditionally, estimates for character sums have been used to count arithmetic configurations of interest to the combinatorialist. More recently, arithmetic combinatorics has proved useful in the estimation of certain character sums. Many character sums are easy to estimate provided they have enough summands - this is sometimes called the square-root barrier and is a natural obstruction. I will show how the sum-product phenomenon can be leveraged to push past this barrier.