## Seminars and Colloquia by Series

### On the chromatic number of a random d-regular graph

Series
Combinatorics Seminar
Time
Friday, March 27, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Graeme KemkesUCSD
Choose a graph uniformly at random from all d-regular graphs on n vertices. We determine the chromatic number of the graph for about half of all values of d, asymptotically almost surely (a.a.s.) as n grows large. Letting k be the smallest integer satisfying d < 2(k-1)\log(k-1), we show that a random d-regular graph is k-colorable a.a.s. Together with previous results of Molloy and Reed, this establishes the chromatic number as a.a.s. k-1 or k. If furthermore d>(2k-3)\log(k-1) then the chromatic number is a.a.s. k. This is an improvement upon results recently announced by Achlioptas and Moore. The method used is "small subgraph conditioning'' of Robinson and Wormald, applied to count colorings where all color classes have the same size. It is the first rigorously proved result about the chromatic number of random graphs that was proved by small subgraph conditioning. This is joint work with Xavier Perez-Gimenez and Nick Wormald.

### Longest Increasing Subsequence for Finite Alphabets

Series
SIAM Student Seminar
Time
Friday, March 27, 2009 - 12:30 for 2 hours
Location
Skiles 255
Speaker
Huy HuynhSchool of Mathematics, Georgia Tech
This is due to the paper of Dr. Christian Houdre and Trevis Litherland. Let X_1, X_2,..., X_n be a sequence of iid random variables drawn uniformly from a finite ordered alphabets (a_1,...,a_m) where a_1 < a_2 < ...< a_m. Let LI_n be the length of the longest increasing subsequence of X_1,X_2,...,X_n. We'll express the limit distribution of LI_n as functionals of (m-1)-dimensional Brownian motion. This is an elementary case taken from this paper.

### On the dimension of the Navier-Stokes singular set

Series
School of Mathematics Colloquium
Time
Thursday, March 26, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Walter CraigMcMaster University
A new estimate on weak solutions of the Navier-Stokes equations in three dimensions gives some information about the partial regularity of solutions. In particular, if energy concentration takes place, the dimension of the microlocal singular set cannot be too small. This estimate has a dynamical systems proof. These results are joint work with M. Arnold and A. Biryuk.

### Twistor Theory, Then and Now

Series
Other Talks
Time
Wednesday, March 25, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Howey Physics Lecture Room 5
Speaker
Roger PenroseMathematical Institute, University of Oxford
Twistor theory is now over 45 years old. In December 1963, I proposed the initial ideas of this scheme, based on complex-number geometry, which presents an alternative perspective to that of standard 4-dimensional space-time, for the basic arena in which (quantum) physics takes place. Over the succeeding years, there were numerous intriguing developments. But many of these were primarily mathematical, and there was little interest expressed by the physics community. Things changed rather dramatically, in December 2003, when E. Witten produced a 99-page article initiating the subject of “twistor-string theory” this providing a novel approach to high-energy scattering processes. In this talk, I shall provide an account of the original geometrical and physical ideas, and also outline various recent developments, some of which may help our understandings of the seeming paradoxes of quantum mechanics.

### Efficient Sampling on Lattices

Series
ACO Student Seminar
Time
Wednesday, March 25, 2009 - 13:30 for 2 hours
Location
ISyE Executive Classroom
Speaker
Dana RandallComputer Science, Georgia Tech
We will survey some old, some new, and some open problems in the area of efficient sampling. We will focus on sampling combinatorial structures (such as perfect matchings and independent sets) on regular lattices. These problems arise in statistical physics, where sampling objects on lattices can be used to determine many thermodynamic properties of simple physical systems. For example, perfect matchings on the Cartesian lattice, more commonly referred to as domino tilings of the chessboard, correspond to systems of diatomic molecules. But most importantly they are just cool problems with some beautiful solutions and a surprising number of unsolved challenges!

### Domain Decompostion Methods for Stokes Equations

Series
Applied and Computational Mathematics Seminar
Time
Wednesday, March 25, 2009 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Junping WangNSF
This talk will first review domain decomposition methods for second order elliptic equations, which should be accessible to graduate students. The second part of the talk will deal with possible extensions to the Stokes equation when discretized by finite element methods. In particular, we shall point out the difficulties in such a generalization, and then discuss ways to overcome the difficulties.

### Stabilization of multimeric enzymes: structural adaptation to stress conditions

Series
Mathematical Biology Seminar
Time
Wednesday, March 25, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Ruslan RafikovMedical College of Georgia
The stress condition calls for an adequate activity of key enzymatic systems of cellular defense. Massive protein destabilization and degradation is occurring in stressed cells. The rate of protein re-synthesis (DNA->RNA->protein) is inadequate to adapt to rapidly changing environment. Therefore, an alternative mechanism should exist maintaining sufficient activity of defense enzymes. Interestingly, more than 50% of enzymes consist of identical subunits which are forming multimeric interface. Stabilization of multimers is important for enzymatic activity. We found that it can be achieved by the formation of inter-subunit covalent bridges in response to stress conditions. It shows an elegance of the structure design that directs selective subunits linkage and increases enzyme's robustness and chances of cell survival during the stress. In contrast, modification of aminoacids involved in linkage leads to protein destabilization, unfolding and degradation. These results describe a new instantaneous mechanism of structural adaptation that controls enzymatic system under stress condition.

### Aeons Before the Big Bang?

Series
Other Talks
Time
Tuesday, March 24, 2009 - 17:30 for 2 hours
Location
LeCraw Auditorium, Room 100
Speaker
Roger PenroseMathematical Institute, University of Oxford
There is much impressive observational evidence, mainly from the cosmic microwave background (CMB), for an enormously hot and dense early stage of the universe --- referred to as the Big Bang. Observations of the CMB are now very detailed, but this very detail presents new puzzles of various kinds, one of the most blatant being an apparent paradox in relation to the second law of thermodynamics. The hypothesis of inflationary cosmology has long been argued to explain away some of these puzzles, but it does not resolve some key issues, including that raised by the second law. In this talk, I describe a quite different proposal, which posits a succession of universe aeons prior to our own. The expansion of the universe never reverses in this scheme, but the space-time geometry is nevertheless made consistent through a novel geometrical conception. Some very recent analysis of the CMB data, obtained with the WMAP satellite, will be described, this having a profound but tantalizing bearing on these issues.

### Global existence for nonlinear elastic and viscoelastic materials

Series
PDE Seminar
Time
Tuesday, March 24, 2009 - 15:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Thomas SiderisUniversity of California, Santa Barbara
We will give an overview of results on the global existence of solutions to the initial value problem for nonlinear elastic and viscoelastic materials in 3d without boundary. Materials will be assumed to be isotropic, but both compressible and incompressible cases will be discussed. In the compressible case, a key null condition must be imposed to control nonlinear interactions of pressure waves. This necessary assumption is consistent with the physical model. Initial conditions are small perturbations of a stress free reference state. Existence is proven using a fixed point argument which combines energy estimates and with some new dispersive estimates.

### Matrix Completion from Fewer Entries

Series
ACO Seminar
Time
Monday, March 23, 2009 - 16:30 for 2 hours
Location
Skiles 269
Speaker
Andrea MontanariStanford University
Low-rank models are frequently used in machine learning and statistics. An important domain of application is provided by collaborative filtering, whereby a low-rank matrix describes the ratings that a large set of users attribute to a large set of products. The problem is in this case to predict future ratings from a sparse subset currently available. The dataset released for the Netflix challenge provides an ideal testbed for theory and algorithms for learning low-rank matrices. Given M, a random n x n matrix of rank r, we assume that a uniformly random subset E of its entries is observed. We describe an efficient procedure that reconstructs M from |E| = O(rn) observed entries with arbitrarily small root mean square error, whenever M is satisfies an appropriate incoherence condition. If r = O(1), the algorithm reconstructs M exactly from O(n log n) entries. This settles a recent open problem by Candes and Recht. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices. [Based on joint work with R. H. Keshavan and S. Oh]