Georgia Institute of Technology College of Sciences

We establish the existence of scaling limits for several combinatorial optimization models on Erdos-Renyi and sparse random regular graphs. For a variety of models, including maximum independent sets, MAX-CUT, coloring and K-SAT, we prove that the optimal value appropriately rescaled, converges to a limit with high probability (w.h.p.), as the size of the underlying graph divergesto infinity. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. thus resolving an open problem. Our approach is based on developing a simple combinatorial approach to an interpolation method developed recently in the statistical physics literature. Among other things, theinterpolation method was used to prove the existence of the so-called free energy limits for several spin glass models including Viana-Bray and random K-SAT models. Our simpler combinatorial approach allows us to work with the zero temperature case (optimization) directly and extend the approach to many other models. Additionally, using our approach, we establish the large deviationsprinciple for the satisfiability property for constraint satisfaction problems such as coloring, K-SAT and NAE(Not-All-Equal)-K-SAT. The talk will be completely self-contained. No background on random graph theory/statistical physics is necessary. Joint work with Mohsen Bayati and Prasad Tetali

Mean field theory for infinite sparse networks of spiking neurons shows that a balanced state of highly irregular activity arises under a variety of conditions. The state is considered to be a model for the ground state of cortical activity. In the first part, we analytically investigate its irregular dynamics in finite networks keeping track of all individual spike times and the identities of individual neurons. For delayed, purely inhibitory interactions, we show that the dynamics is not chaotic but in fact stable. Moreover, we demonstrate that after long transients the dynamics converges towards periodic orbits and that every generic periodic orbit of these dynamical systems is stable. These results indicate that chaotic and stable dynamics are equally capable of generating the irregular neuronal activity. More generally, chaos apparently is not essential for generating high irregularity of balanced activity, and we suggest that a mechanism different from chaos and stochasticity significantly contributes to irregular activity in cortical circuits. In the second part, we study the propagation of synchrony in front of a background of irregular spiking activity. We show numerically and analytically that supra-additive dendritic interactions, as recently discovered in single neuron experiments, enable the propagation of synchronous activity even in random networks. This can lead to intermittent events, characterized by strong increases of activity with high-frequency oscillations; our model predicts the shape of these events and the oscillation frequency. As an example, for the hippocampal region CA1, events with 200Hz oscillations are predicted. We argue that these dynamics provide a plausible explanation for experimentally observed sharp-wave/ripple events.

Orthogonal Polynomials and their generalizations have a great many applications in areas ranging from signal processing to random matrices to combinatorics. We outline a few of the connections, and present some possible Ph. D Problems

State polytopes in commutative algebra can be used to detect the geometric invariant theory (GIT) stability of points in the Hilbert scheme. I will review the construction of state polytopes and their role in GIT, and present recent work with Ian Morrison in which we use state polytopes to estabilish stability for curves of small genus and low degree, confirming predictions of the minimal model program for the moduli space of curves.