Georgia Institute of Technology College of Sciences

Thresholds for increasing properties are a central concern in probabilistic combinatorics and elsewhere. (An increasing property, say F, is a superset-closed family of subsets of some (here finite) set X; the threshold question for such an F asks, roughly, about how many random elements of X should one choose to make it likely that the resulting set lies in F? For example: about how many random edges from the complete graph K_n are typically required to produce a Hamiltonian cycle?) We'll discuss recent progress and lack thereof on a few threshold-type questions, and try to say something about a ludicrously general conjecture of G. Kalai and the speaker to the effect that there is always a pretty good naive explanation for a threshold being what it is.

I will talk about the asymptotic geometry of Teichmuller space equipped with the Weil-Petersson metric. In particular, I will give a criterion for determining when two points in the asymptotic cone of Teichmuller space can be separated by a point; motivated by a similar characterization in mapping class groups by Behrstock-Kleiner-Minsky-Mosher and in right angled Artin groups by Behrstock-Charney. As a corollary, I will explain a new way to uniquely characterize the Teichmuller space of the genus two once punctured surface amongst all Teichmuller space in that it has a divergence function which is superquadratic yet subexponential.

Recently, there has been great interest in understanding the fundamental limits of our ability to sample from the independent sets (i.s.) of a graph. One approach involves the study of the so-called hardcore model, in which each i.s. is selected with probability proportional to some fixed activity $\lambda$ raised to the cardinality of the given i.s. It is well-known that for any fixed degree $\Delta$, there exists a critical activity $\lambda_{\Delta}$ s.t. for all activities below $\lambda_{\Delta}$, the sampled i.s. enjoys a long-range independence (a.k.a. uniqueness) property when implemented on graphs with maximum degree $\Delta$, while for all activities above $\lambda_{\Delta}$, the sampled i.s. exhibits long-range dependencies. Such phase transitions are known to have deep connections to the inherent computational complexity of the underlying combinatorial problems. In this talk, we study a family of measures which generalizes the hardcore model by taking more structural information into account, beyond just the number of nodes belonging to the i.s., with the hope of further probing the fundamental limits of what we can learn about the i.s. of a graph using only local information. In our model, the probability assigned to a given i.s. depends not only on its cardinality, but also on how many excluded nodes are adjacent to exactly $k$ nodes belonging to the i.s., for each $k$, resulting in a parameter for each $k$. We generalize the notion of critical activity to these ``neighborly measures", and give necessary and sufficient conditions for long-range independence when certain parameters satisfy a log-convexity(concavity) requirement. To better understand the phase transitions in this richer model, we view the classical critical activity as a particular point in the parameter space, and ask which directions can one move and still maintain long-range independence. We show that the set of all such ``directions of uniqueness” has a simple polyhedral description, which we use to study how moving along these directions changes the probabilities associated with the sampled i.s. We conclude by discussing implications for choosing how to sample when trying to optimize a linear function of the underlying probabilities.

I will review the well known method (pushed mainly by Karlin and McGregor) to study birth-and-death processes with the help of orthogonal polynomials. I will then look at several extensions of this idea, including ¨poker dice¨ (polynomials in several variables) and quantum walks (polynomials in the unit circle).