Seminars and Colloquia by Series

6-connected graphs are two-three linked

Series
Dissertation Defense
Time
Thursday, October 24, 2019 - 13:40 for 1.5 hours (actually 80 minutes)
Location
Skiles 005
Speaker
Shijie XieSchool of Mathematics, Georgia Tech

Let $G$ be a graph and $a_0, a_1, a_2, b_1,$ and $b_2$ be distinct vertices of $G$. Motivated by their work on Four Color Theorem, Hadwiger's conjecture for $K_6$, and Jorgensen's conjecture, Robertson and Seymour asked when does $G$ contain disjoint connected subgraphs $G_1, G_2$, such that $\{a_0, a_1, a_2\}\subseteq V(G_1)$ and $\{b_1, b_2\}\subseteq V(G_2)$. We prove that if $G$ is 6-connected then such $G_1,G_2$ exist. Joint work with Robin Thomas and Xingxing Yu.

Advisor: Dr. Xingxing Yu (School of Mathematics, Georgia Institute of Technology)

Committee: Dr. Robin Thomas (School of Mathematics, Georgia Institute of Technology), Dr. Prasad Tetali (School of Mathematics, Georgia Institute of Technology), Dr. Lutz Warnke (School of Mathematics, Georgia Institute of Technology), Dr. Richard Peng (School of Computer Science, Georgia Institute of Technology)

Reader: Dr. Gexin Yu (Department of Mathematics, College of William and Mary)

Topics On the Length of the Longest Common Subsequences With Blocks In Binary Random Words

Series
Dissertation Defense
Time
Thursday, August 8, 2019 - 13:00 for
Location
Skiles 246
Speaker
Yuze ZhangGeorgia Institute of Technology

The study of LIn, the length of the longest increasing subsequences, and of LCIn, the length of the longest common and increasing subsequences in random words is classical in computer science and bioinformatics, and has been well explored over the last few decades. This dissertation studies a generalization of LCIn for two binary random words, namely, it analyzes the asymptotic behavior of LCbBn, the length of the longest common subsequences containing a fixed number, b, of blocks. We first prove that after proper centerings and scalings, LCbBn, for two sequences of i.i.d. Bernoulli random variables with possibly two different parameters, converges in law towards limits we identify. This dissertation also includes an alternative approach to the one-sequence LbBn problem, and Monte-Carlo simulations on the asymptotics of LCbBn and on the growth order of the limiting functional, as well as several extensions of the LCbBn problem to the Markov context and some connection with percolation theory.

Quantum torus methods for Kauffman bracket skein modules

Series
Dissertation Defense
Time
Friday, July 26, 2019 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Jonathan PaprockiGeorgia Institute of Technology

We investigate aspects of Kauffman bracket skein algebras of surfaces and modules of 3-manifolds using quantum torus methods. These methods come in two flavors: embedding the skein algebra into a quantum torus related to quantum Teichmuller space, or filtering the algebra and obtaining an associated graded algebra that is a monomial subalgebra of a quantum torus. We utilize the former method to generalize the Chebyshev homomorphism of Bonahon and Wong between skein algebras of surfaces to a Chebyshev-Frobenius homomorphism between skein modules of marked 3-manifolds, in the course of which we define a surgery theory, and whose image we show is either transparent or (skew)-transparent. The latter method is used to show that skein algebras of surfaces are maximal orders, which implies a refined unicity theorem, shows that SL_2C-character varieties are normal, and suggests a conjecture on how this result may be utilized for topological quantum compiling.

On the Independent Spanning Tree Conjectures and Related Problems

Series
Dissertation Defense
Time
Wednesday, July 10, 2019 - 10:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Alexander HoyerGeorgia Institute of Technology

We say that trees with common root are (edge-)independent if, for any vertex in their intersection, the paths to the root induced by each tree are internally (edge-)disjoint. The relationship between graph (edge-)connectivity and the existence of (edge-)independent spanning trees is explored. The (Edge-)Independent Spanning Tree Conjecture states that every k-(edge-)connected graph has k-(edge-)independent spanning trees with arbitrary root.

We prove the case k=4 of the Edge-Independent Spanning Tree Conjecture using a graph decomposition similar to an ear decomposition, and give polynomial-time algorithms to construct the decomposition and the trees. We provide alternate geometric proofs for the cases k=3 of both the Independent Spanning Tree Conjecture and Edge-Independent Spanning Tree Conjecture by embedding the vertices or edges in a 2-simplex, and conjecture higher-dimension generalizations. We provide a partial result towards a generalization of the Independent Spanning Tree Conjecture, in which local connectivity between the root and a vertex set S implies the existence of trees whose independence properties hold only in S. Finally, we prove and generalize a theorem of Györi and Lovász on partitioning a k-connected graph, and give polynomial-time algorithms for the cases k=2,3,4 using the graph decompositions used to prove the corresponding cases of the Independent Spanning Tree Conjecture.

Lattice points, zonotopes, and oriented matroids

Series
Dissertation Defense
Time
Wednesday, July 3, 2019 - 11:00 for
Location
Skiles 006
Speaker
Marcel CelayaGeorgia Tech

The first half of this dissertation concerns the following problem: Given a lattice in $\mathbf{R}^d$ which refines the integer lattice $\mathbf{Z}^d$, what can be said about the distribution of the lattice points inside of the half-open unit cube $[0,1)^d$? This question is of interest in discrete geometry, especially integral polytopes and Ehrhart theory. We observe a combinatorial description of the linear span of these points, and give a formula for the dimension of this span. The proofs of these results use methods from classical multiplicative number theory.

In the second half of the dissertation, we investigate oriented matroids from the point of view of tropical geometry. Given an oriented matroid, we describe, in detail, a polyhedral complex which plays the role of the Bergman complex for ordinary matroids. We show how this complex can be used to give a new proof of the celebrated Bohne-Dress theorem on tilings of zonotopes by zonotopes with an approach which relies on a novel interpretation of the chirotope of an oriented matroid.

Topics in Dynamical Systems

Series
Dissertation Defense
Time
Wednesday, June 5, 2019 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Longmei ShuGeorgia Inst. of Technology

Isospectral reductions is a network/graph reduction that preserves the
eigenvalues and the eigenvectors of the adjacency matrix. We analyze the
conditions under which the generalized eigenvectors would be preserved and
simplify the proof of the preservation of eigenvectors. Isospectral reductions
are associative and form a dynamical system on the set of all matrices/graphs.
We study the spectral equivalence relation defined by specific characteristics
of nodes under isospectral reductions and show some examples of the attractors.
Cooperation among antigens, cross-immunoreactivity (CR) has been observed in
various diseases. The complex viral population dynamics couldn't be explained
by traditional math models. A new math model was constructed recently with
promising numerical simulations. In particular, the numerical results recreated
local immunodeficiency (LI), the phenomenon where some viruses sacrifice
themselves while others are not attacked by the immune system. Here we analyze
small CR networks to find the minimal network with a stable LI. We also
demonstrate that you can build larger CR networks with stable LI using this
minimal network as a building block.

Short time solution to the master equation of a first order mean field game

Series
Dissertation Defense
Time
Friday, May 3, 2019 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sergio MayorgaGraduate student

For a first order (deterministic) mean-field game with non-local running and initial couplings, a classical solution is constructed for the associated, so-called master equation, a partial differential equation in infinite-dimensional space with a non-local term, assuming the time horizon is sufficiently small and the coefficients are smooth enough, without convexity conditions on the Hamiltonian. 

Percolation Theory: The complement of the infinite cluster & The acceptance profile of the invasion percolation

Series
Dissertation Defense
Time
Thursday, May 2, 2019 - 13:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Bounghun BockGeorgia Tech

In independent bond percolation  with parameter p, if one removes the vertices of the infinite cluster (and incident edges), for which values of p does the remaining graph contain an infinite cluster? Grimmett-Holroyd-Kozma used the triangle condition to show that for d > 18, the set of such p contains values strictly larger than the percolation threshold pc. With the work of Fitzner-van der Hofstad, this has been reduced to d > 10. We reprove this result by showing that for d > 10 and some p>pc, there are infinite paths consisting of "shielded"' vertices --- vertices all whose adjacent edges are closed --- which must be in the complement of the infinite cluster. Using numerical values of pc, this bound can be reduced to d > 7. Our methods are elementary and do not require the triangle condition.

Invasion percolation is a stochastic growth model that follows a greedy algorithm. After assigning i.i.d. uniform random variables (weights) to all edges of d-dimensional space, the growth starts at the origin. At each step, we adjoin to the current cluster the edge of minimal weight from its boundary. In '85, Chayes-Chayes-Newman studied the "acceptance profile"' of the invasion: for a given p in [0,1], it is the ratio of the expected number of invaded edges until time n with weight in [p,p+dp] to the expected number of observed edges (those in the cluster or its boundary) with weight in the same interval. They showed that in all dimensions, the acceptance profile an(p) converges to one for ppc. In this paper, we consider an(p) at the critical point p=pc in two dimensions and show that it is bounded away from zero and one as n goes to infinity.

The Polaron Hydrogenic Atom in a Strong Magnetic Field

Series
Dissertation Defense
Time
Thursday, May 2, 2019 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Rohan GhantaSchool of Mathematics

An electron interacting with the vibrational modes of a polar crystal is called a polaron. Polarons are the simplest Quantum Field Theory models, yet their most basic features such as the effective mass, ground-state energy and wave function cannot be evaluated explicitly. And while several successful theories have been proposed over the years to approximate the energy and effective mass of various polarons, they are built entirely on unjustified, even questionable, Ansätze for the wave function. 

In this talk I shall provide the first explicit description of the ground-state wave function of a polaron in an asymptotic regime: For the Fröhlich polaron localized in a Coulomb potential and exposed to a homogeneous magnetic field of strength $B$ it will be shown that the ground-state electron density in the direction of the magnetic field converges pointwise and in a weak sense as $B\rightarrow\infty$ to the square of a hyperbolic secant function--a sharp contrast to the Gaussian wave functions suggested in the physics literature. 

Discrete Optimal Transport With Applications in Path Planning and Data Clustering

Series
Dissertation Defense
Time
Wednesday, April 17, 2019 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Haoyan ZhaiGeorgia Tech

Optimal transport is a thoroughly studied field in mathematics and introduces the concept of Wasserstein distance, which has been widely used in various applications in computational mathematics, machine learning as well as many areas in engineering. Meanwhile, control theory and path planning is an active branch in mathematics and robotics, focusing on algorithms that calculates feasible or optimal paths for robotic systems. In this defense, we use the properties of the gradient flows in Wasserstein metric to design algorithms to handle different types of path planning and control problems as well as the K-means problems defined on graphs.

Pages