## Seminars and Colloquia by Series

### Markov Chains at the Interface of Combinatorics, Computing, and Statistical Physics

Series
Dissertation Defense
Time
Wednesday, March 14, 2012 - 13:00 for 2 hours
Location
Skiles 005
Speaker
Amanda Pascoe StreibSchool of Mathematics, Georgia Tech
The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives. First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_{mon} requires exponential time to converge. Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_{nn} in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x < y in order with bias 1/2 <= p_{xy} <= 1 and out of order with bias 1-p_{xy}. The Markov chain M_{mon} was known to have connections to a simplified version of this biased card-shuffling. We provide new connections between M_{nn} and M_{mon} by using simple combinatorial bijections, and we prove that M_{nn} is always rapidly mixing for two general classes of positively biased {p_{xy}}. More significantly, we also prove that the general conjecture is false by exhibiting values for the p_{xy}, with 1/2 <= p_{xy} <= 1 for all x < y, but for which the transposition chain will require exponential time to converge. Finally, we consider a model of colloids, which are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. This clustering has proved elusive to verify, since all local sampling algorithms are known to be inefficient at high density, and in fact a new nonlocal algorithm was recently shown to require exponential time in some cases. We characterize the high and low density phases for a general family of discrete interfering binary mixtures by showing that they exhibit a "clustering property" at high density and not at low density. The clustering property states that there will be a region that has very high area, very small perimeter, and high density of one type of molecule. Special cases of interfering binary mixtures include the Ising model at fixed magnetization and independent sets.

### Planar and Hamiltonian Cover Graphs

Series
Dissertation Defense
Time
Friday, November 18, 2011 - 13:00 for 2 hours
Location
Skiles 005
Speaker
Noah StreibSchool of Mathematics, Georgia Tech
This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h \geq 2, there exists a least positive integer c_h so that if P is a poset having a planar cover graph (hence P is a planar poset as well) and the height of P is h, then the dimension of P is at most c_h. In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c_h, noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a Hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's Theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this class has the HC-SCP property.

### Empirical likelihood and Extremes

Series
Dissertation Defense
Time
Wednesday, November 16, 2011 - 15:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 171
Speaker
Yun GongSchool of Mathematics, Georgia Tech

In 1988, Owen introduced empirical likelihood as a nonparametric method for constructing confidence intervals and regions. It is well known that empirical likelihood has several attractive advantages comparing to its competitors such as bootstrap: determining the shape of confidence regions automatically; straightforwardly incorporating side information expressed through constraints; being Bartlett correctable. In this talk, I will discuss some extensions of the empirical likelihood method to several interesting and important statistical inference situations including: the smoothed jackknife empirical likelihood method for the receiver operating characteristic (ROC) curve, the smoothed empirical likelihood method for the conditional Value-at-Risk with the volatility model being an ARCH/GARCH model and a nonparametric regression respectively. Then, I will propose a method for testing nested stochastic models with discrete and dependent observations.

### Hybrid Modeling and Analysis of Multiscale Biochemical Reaction Networks

Series
Dissertation Defense
Time
Monday, October 24, 2011 - 13:30 for 1 hour (actually 50 minutes)
Location
Klaus Conference Room 1212
Speaker
Jialiang WuSchool of Mathematics, Georgia Tech

### Two Problems in Mathematical Physics: Villani's Conjecture and a Trace Inequality for the Fractional Laplacian

Series
Dissertation Defense
Time
Monday, August 29, 2011 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Amit EinavSchool of Mathematics, Georgia Tech
The presented work deals with two distinct problems in the field of Mathematical Physics, and as such will have two parts addressing each problem. The first part is dedicated to an 'almost' solution of Villani's conjecture, a known conjecture related to a Statistical Mechanics model invented by Kac in 1956, giving a rigorous explanation of some simple cases of the Boltzman equation. In 2003 Villani conjectured that the time it will take the system of particles in Kac's model to equalibriate is proportional to the number of particles in the system. Our main result in this part is an 'almost proof' of that conjecture, showing that for all practical purposes we can consider it to be true. The second part of the presentation is dedicated to a newly developed trace inequality for the fractional Laplacian, connecting between the fractional Laplacian of a function and its restriction to the intersection of the hyperplanes x_n =...= x_n-j+1 = 0 , where 1 <= j < n. The newly found inequality is sharp and the functions that attain inequality in it are completely classified.

### Topics in Spatial and Dynamical Phase Transitions of Interacting Particle Systems

Series
Dissertation Defense
Time
Monday, August 15, 2011 - 11:00 for 2 hours
Location
Skiles 005
Speaker
Ricardo Restrepo LopezSchool of Mathematics, Georgia Tech
In this work we provide several improvements in the study of phase transitions of interacting particle systems: 1. We determine a quantitative relation between non-extremality of the limiting Gibbs measure of a tree-based spin system, and the temporal mixing of the Glauber Dynamics over its finite projections. We define the concept of sensitivity' of a reconstruction scheme to establish such a relation. In particular, we focus in the independent sets model, determining a phase transition for the mixing time of the Glauber dynamics at the same location of the extremality threshold of the simple invariant Gibbs version of the model. 2. We develop the technical analysis of the so-called spatial mixing conditions for interacting particle systems to account for the connectivity structure of the underlying graph. This analysis leads to improvements regarding the location of the uniqueness/non-uniqueness phase transition for the independent sets model over amenable graphs; among them, the elusive hard-square model in lattice statistics, which has received attention since Baxter's solution of the analogue hard-hexagon in 1980. 3. We build on the work of Montanari and Gerschenfeld to determine the existence of correlations for the coloring model in sparse random graphs. In particular, we prove that correlations exist above the clustering' threshold of such model; thus providing further evidence for the conjectural algorithmic `hardness' occurring at such point.

### Normally Elliptic Singular Perturbation Problems: Local Invariant Manifolds and Applications

Series
Dissertation Defense
Time
Monday, May 16, 2011 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Nan LuSchool of Mathematics, Georgia Tech

We study the normally elliptic singular perturbation problems including both finite and infinite dimensional cases, which could also be nonautonomous. In particular, we establish the existence and smoothness of O(1) local invariant manifolds and provide various estimates which are independent of small singular parameters. We also use our results on local invariant manifolds to study the persistence of homoclinic solutions under weakly dissipative and conservative perturbations.

### Judicious Partitions of Graphs and Hypergraphs

Series
Dissertation Defense
Time
Tuesday, April 26, 2011 - 12:30 for 2 hours
Location
Skiles 005
Speaker
Jie MaSchool of Mathematics, Georgia Tech
Classical partitioning problems, like the Max-Cut problem, ask for partitions that optimize one quantity, which are important to such fields as VLSI design, combinatorial optimization, and computer science. Judicious partitioning problems on graphs or hypergraphs ask for partitions that optimize several quantities simultaneously. In this dissertation, we work on judicious partitions of graphs and hypergraphs, and solve or asymptotically solve several open problems of Bollobas and Scott on judicious partitions, using the probabilistic method and extremal techniques.

### Hardy-Sobolev-Maz'ya Inequalities for Fractional Integrals on Halfspaces and Convex Domains

Series
Dissertation Defense
Time
Tuesday, April 19, 2011 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Craig A. SloaneSchool of Mathematics, Georgia Tech
Classical Hardy, Sobolev, and Hardy-Sobolev-Maz'ya inequalities are well known results that have been studied for awhile. In recent years, these results have been been generalized to fractional integrals. This Dissertation proves a new Hardy inequality on general domains, an improved Hardy inequality on bounded convex domains, and that the sharp constant for any convex domain is the same as that known for the upper halfspace. We also prove, using a new type of rearrangement on the upper halfspace, based in part on Carlen and Loss' concept of competing symmetries, the existence of the fractional Hardy-Sobolev-Maz'ya inequality in the case p = 2, as well as proving the existence of minimizers, at least in limited cases.

### Isospectral Graph Reductions, Estimates of Matrices' Spectra, and Eventually Negative Schwarzian Systems

Series
Dissertation Defense
Time
Tuesday, March 8, 2011 - 09:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Benjamin WebbSchool of Mathematics, Georgia Tech
Real world networks typically consist of a large number of dynamical units with a complicated structure of interactions. Until recently such networks were most often studied independently as either graphs or as coupled dynamical systems. To integrate these two approaches we introduce the concept of an isospectral graph transformation which allows one to modify the network at the level of a graph while maintaining the eigenvalues of its adjacency matrix. This theory can then be used to rewire dynamical networks, considered as dynamical systems, in order to gain improved estimates for whether the network has a unique global attractor. Moreover, this theory leads to improved eigenvalue estimates of Gershgorin-type. Lastly, we will discuss the use of Schwarzian derivatives in the theory of 1-d dynamical systems.