Seminars and Colloquia by Series

Low-Rank Estimation of Smooth Kernels on Graphs

Series
Dissertation Defense
Time
Monday, July 21, 2014 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Pedro Rangel – School of Mathematics, Georgia Tech
This dissertation investigates the problem of estimating a kernel over a large graph based on a sample of noisy observations of linear measurements of the kernel. We are interested in solving this estimation problem in the case when the sample size is much smaller than the ambient dimension of the kernel. As is typical in high-dimensional statistics, we are able to design a suitable estimator based on a small number of samples only when the target kernel belongs to a subset of restricted complexity. In our study, we restrict the complexity by considering scenarios where the target kernel is both low-rank and smooth over a graph. The motivations for studying such problems come from various real-world applications like recommender systems and social network analysis. We study the problem of estimating smooth kernels on graphs. Using standard tools of non-parametric estimation, we derive a minimax lower bound on the least squares error in terms of the rank and the degree of smoothness of the target kernel. To prove the optimality of our lower-bound, we proceed to develop upper bounds on the error for a least-square estimator based on a non-convex penalty. The proof of these upper bounds depends on bounds for estimators over uniformly bounded function classes in terms of Rademacher complexities. We also propose a computationally tractable estimator based on least-squares with convex penalty. We derive an upper bound for the computationally tractable estimator in terms of a coherence function introduced in this work. Finally, we present some scenarios wherein this upper bound achieves a near-optimal rate.

Linear Systems on Metric graphs and Some Applications to Tropical Geometry and Non-Archimedean Geometry

Series
Dissertation Defense
Time
Thursday, June 26, 2014 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ye Luo – School of Mathematics, Georgia Tech
The work in this dissertation is mainly focused on three subjects which are essentially related to linear systems on metric graphs and its application: (1) rank-determining sets of metric graphs, which can be employed to actually compute the rank function of arbitrary divisors on an arbitrary metric graph, (2) a tropical convexity theory for linear systems on metric graphs, and (3) smoothing of limit linear series of rank one on refined metrized complex (an intermediate object between metric graphs and algebraic curves),

A Numerical Study of Vorticity-Enhanced Heat Transfer

Series
Dissertation Defense
Time
Tuesday, June 24, 2014 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiaolin Wang – School of Mathematics, Georgia Tech
In this work, we numerically studied the effect of the vorticity on the enhancement of heat transfer in a channel flow. Based on the model we proposed, we find that the flow exhibits different properties depending on the value of four dimensionless parameters. In particularly, we can classify the flows into two types, active and passive vibration, based on the sign of the incoming vortices. The temperature profiles according to the flow just described also show different characteristics corresponding to the active and passive vibration cases. In active vibration cases, we find that the heat transfer performance is directly related to the strength of the incoming vortices and the speed of the background flow. In passive vibration cases, the corresponding heat transfer process is complicated and varies dramatically as the flow changes its properties. Compared to the fluid parameters, we also find that the thermal parameters have much less effect on the heat transfer enhancement. Finally, we propose a more realistic optimization problem which is to minimize the maximum temperature of the solids with a given input energy. We find that the best heat transfer performance is obtained in the active vibration case with zero background flow.

Graph Structures and Well-Quasi-Ordering

Series
Dissertation Defense
Time
Thursday, June 12, 2014 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Chun-Hung Liu – Georgia Tech
Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). An application of these theorems is that every property that is closed under deleting vertices, edges, and contracting (or "splitting off", respectively) edges can be characterized by finitely many graphs, and hence can be decided in polynomial time. In this thesis we are concerned with the topological minor relation. We say that a graph G contains another graph H as a topological minor if H can be obtained from a subgraph of G by repeatedly deleting a vertex of degree two and adding an edge incident with the neighbors of the deleted vertex. Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980's that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. This thesis consists of two main results. The first one is a structure theorem for excluding a fixed graph as a topological minor, which is analogous to a cornerstone result of Robertson and Seymour, who gave such structure for graphs that exclude a fixed minor. Results for topological minors were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for the next theorem. The second main result is a proof of Robertson's conjecture. As a corollary, properties on certain graphs closed under deleting vertices, edges, and "suppressing" vertices of degree two can be characterized by finitely many graphs, and hence can be decided in polynomial time.

Invariant densities for dynamical systems with random switching

Series
Dissertation Defense
Time
Thursday, May 1, 2014 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Tobias Hurth – Georgia Institute of Technology –
We consider a class of dynamical systems with random switching with the following specifics: Given a finite collection of smooth vector fields on a finite-dimensional smooth manifold, we fix an initial vector field and a starting point on the manifold. We follow the solution trajectory to the corresponding initial-value problem for a random, exponentially distributed time until we switch to a new vector field chosen at random from the given collection. Again, we follow the trajectory induced by the new vector field for an exponential time until we make another switch. This procedure is iterated. The resulting two-component process whose first component records the position on the manifold, and whose second component records the driving vector field at any given time, is a Markov process. We identify sufficient conditions for its invariant measure to be unique and absolutely continuous. In the one-dimensional case, we show that the invariant densities are smooth away from critical points of the vector fields and derive asymptotics for the invariant densities at critical points.

Flag algebras and the stable coefficients of the Jones polynomial

Series
Dissertation Defense
Time
Friday, April 25, 2014 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Thao Vuong – Georgia Institute of Technology –
We study the structure of the stable coefficients of the Jones polynomial of an alternating link. We start by identifying the first four stable coefficients with polynomial invariants of a (reduced) Tait graph of the link projection. This leads us to introduce a free polynomial algebra of invariants of graphs whose elements give invariants of alternating links which strictly refine the first four stable coefficients. We conjecture that all stable coefficients are elements of this algebra, and give experimental evidence for the fifth and sixth stable coefficient. We illustrate our results in tables of all alternating links with at most 10 crossings and all irreducible planar graphs with at most 6 vertices.

Stein fillings of contact manifolds supported by planar open books.

Series
Dissertation Defense
Time
Wednesday, April 16, 2014 - 11:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Amey Kaloti – Georgia Tech –
In this thesis we study topology of symplectic fillings of contact manifolds supported by planar open books. We obtain results regarding geography of the symplectic fillings of these contact manifolds. Specifically, we prove that if a contact manifold $(M,\xi)$ is supported by a planar open book, then Euler characteristic and signature of any Stein filling of $(M,\xi)$ is bounded. We also prove a similar finiteness result for contact manifolds supported by spinal open books with planar pages. Moving beyond the geography of Stein fillings, we classify fillings of some lens spaces.In addition, we classify Stein fillings of an infinite family of contact 3-manifolds up to diffeomorphism. Some contact 3-manifolds in this family can be obtained by Legendrian surgeries on $(S^3,\xi_{std})$ along certain Legendrian 2-bridge knots. We also classify Stein fillings, up to symplectic deformation, of an infinite family of contact 3-manifolds which can be obtained by Legendrian surgeries on $(S^3,\xi_{std})$ along certain Legendrian twist knots. As a corollary, we obtain a classification of Stein fillings of an infinite family of contact hyperbolic 3-manifolds up to symplectic deformation.

Pfaffian Orientations, Flat Embeddings, and Steinberg’s Conjecture

Series
Dissertation Defense
Time
Tuesday, April 15, 2014 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peter Whalen – Georgia Institute of Technology –
The first result of this thesis is a partial result in the direction of Steinberg's Conjecture. Steinberg's Conjecture states that any planar graph without cycles of length four or five is three colorable. Borodin, Glebov, Montassier, and Raspaud showed that planar graphs without cycles of length four, five, or seven are three colorable and Borodin and Glebov showed that planar graphs without five cycles or triangles at distance at most two apart are three colorable. We prove a statement that implies the first of these theorems and is incomparable with the second: that any planar graph with no cycles of length four through six or cycles of length seven with incident triangles distance exactly two apart are three colorable. We are next concerned with the study of Pfaffian orientations. A theorem proved by William McCuaig and, independently, Neil Robertson, Paul Seymour, and Robin Thomas provides a good characterization for whether or not a bipartite graph has a Pfaffian orientation as well as a polynomial time algorithm for that problem. We reprove this characterization and provide a new algorithm for this problem. First, we generalize a preliminary result needed to reprove this theorem. Specifically, we show that any internally 4-connected, non-planar bipartite graph contains a subdivision of K3,3 in which each path has odd length. We then make use of this result to provide a much shorter proof of this characterization using elementary methods. In the final piece of the thesis we investigate flat embeddings. A piecewise-linear embedding of a graph in 3-space is flat if every cycle of the graph bounds a disk disjoint from the rest of the graph. We first provide a structural theorem for flat embeddings that indicates how to build them from small pieces. We then present a class of flat graphs that are highly non-planar in the sense that, for any fixed k, there are an infinite number of members of the class such that deleting k vertices leaves the graph non-planar.

TBA by Jun Lu

Series
Dissertation Defense
Time
Monday, March 31, 2014 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Jun Lu – School of Mathematics, Georgia Tech
This thesis proposes a novel and efficient method (Method of Evolving Junctions) for solving optimal control problems with path constraints, and whose optimal paths are separable. A path is separable if it is the concatenation of finite number of subarcs that are optimal and either entirely constraint active or entirely constraint inactive. In the case when the subarcs can be computed efficiently, the search for the optimal path boils down to determining the junctions that connect those subarcs. In this way, the original infinite dimensional problem of finding the entire path is converted into a finite dimensional problem of determining the optimal junctions. The finite dimensional optimization problem is then solved by a recently developed global optimization strategy, intermittent diffusion. The idea is to add perturbations (noise) to the gradient flow intermittently, which essentially converts the ODE's (gradient descent) into a SDE's problem. It can be shown that the probability of finding the globally optimal path can be arbitrarily close to one. Comparing to existing methods, the method of evolving junctions is fundamentally faster and able to find the globally optimal path as well as a series of locally optimal paths. The efficiency of the algorithm will be demonstrated by solving path planning problems, more specifically, finding the optimal path in cluttered environments with static or dynamic obstacles.

Algebraic degrees of stretch factors in mapping class groups

Series
Dissertation Defense
Time
Monday, March 31, 2014 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Hyunshik Shin – Georgia Institute of Technology –
Given a closed surface S_g of genus g, a mapping class f is said to be pseudo-Anosov if it preserves a pair of transverse measured foliations such that one is expanding and the other one is contracting by a number $\lambda$. The number $\lambda$ is called a stretch factor (or dilatation) of f. Thurston showed that a stretch factor is an algebraic integer with degree bounded above by 6g-6. However, little is known about which degrees occur. Using train tracks on surfaces, we explicitly construct pseudo-Anosov maps on S_g with orientable foliations whose stretch factor $\lambda$ has algebraic degree 2g. Moreover, the stretch factor $\lambda$ is a special algebraic number, called Salem number. Using this result, we show that there is a pseudo-Anosov map whose stretch factor has algebraic degree d, for each positive even integer d such that d is less than or equal to g. Our examples also give a new approach to a conjecture of Penner.

Pages