Seminars and Colloquia by Series

Sampling Random Spanning Trees Faster than Matrix Multiplication

Series
ACO Student Seminar
Time
Friday, February 17, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
David Durfee – College of Computing, Georgia Tech
We present an algorithm that, with high probability, generates a random spanning treefrom an edge-weighted undirected graph in O (n^{5/3}m^{1/3}) time. The tree is sampled from adistribution where the probability of each tree is proportional to the product of its edge weights.This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(n^\omega). For the special case of unweighted graphs, this improves upon thebest previously known running time of ˜O(min{n^\omega, mn^{1/2}, m^{4/3}}) for m >> n^{7/4} (Colbourn et al. ’96, Kelner-Madry ’09, Madry et al. ’15).The effective resistance metric is essential to our algorithm, as in the work of Madry et al., butwe eschew determinant-based and random walk-based techniques used by previous algorithms.Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance ispreserved in the graph resulting from eliminating a subset of vertices (called a Schur complement).As part of our algorithm, we show how to compute -approximate effective resistances for a set Sof vertex pairs via approximate Schur complements in O (m + (n + |S|)/\eps^{ −2}) time, without usingthe Johnson-Lindenstrauss lemma which requires eO(min{(m+|S|) \eps{−2},m+n /eps^{−4} +|S|/eps^{ −2}}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn’t sufficiently accurate.Joint work with Rasmus Kyng, John Peebles, Anup Rao, and Sushant Sachdeva

Conley-Zehnder index of periodic Reeb orbits

Series
Geometry Topology Student Seminar
Time
Wednesday, February 15, 2017 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Surena Hozoori – Georgia Tech
In this talk, I will define Conley-Zehnder index of a periodic Reeb orbit and will give several characterizations of this invariant. Conley-Zehnder index plays an important role in computing the dimension of certain families of J-holomorphic curves in the symplectization of a contact manifold.

0-concordance of 2-knots

Series
Geometry Topology Seminar
Time
Monday, February 13, 2017 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Nathan Sunukjian – Calvin College
A 2-knot is defined to be an embedding of S^2 in S^4. Unlike the theory of concordance for knots in S^3, the theory of concordance of 2-knots is trivial. This talk will be framed around the related concept of 0-concordance of 2-knots. It has been conjectured that this is also a trivial theory, that every 2-knot is 0-concordant to every other 2-knot. We will show that this conjecture is false, and in fact there are infinitely many 0-concordance classes. We'll in particular point out how the concept of 0-concordance is related to understanding smooth structures on S^4. The proof will involve invariants coming from Heegaard-Floer homology, and we will furthermore see how these invariants can be used shed light on other properties of 2-knots such as amphichirality and invertibility.

Coloring curves that cross a fixed curve

Series
Combinatorics Seminar
Time
Friday, February 10, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Bartosz Walczak – Jagiellonian University in Kraków –
A class of graphs is *χ-bounded* if the chromatic number of all graphs in the class is bounded by some function of their clique number. *String graphs* are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are *χ*-bounded. In particular, it is known since 2012 that the class of all string graphs is not *χ*-bounded. We prove that for every integer *t*≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve *c* in at least one and at most *t* points is *χ*-bounded. This result is best possible in several aspects; for example, the upper bound *t* on the number of crossings of each curve with *c* cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called *k*-quasi-planar topological graphs. This is joint work with Alexandre Rok.

Energy identity for a sequence of Sacks-Uhlenbeck maps to a sphere

Series
PDE Seminar
Time
Friday, February 10, 2017 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jiayu Li – University of Science and Technology of China –
For a map u from a Riemann surface M to a Riemannian manifold and a>1, the a-energy functional is defined as E_a(u)=\int_M |\nabla u|^{2a}dx. We call u_a a sequence of Sacks-Uhlenbeck maps if u_a is a critical point of E_a, and sup_{a>1} E_a(u_a)<\infty. In this talk, when the target manifold is a standard sphere S^K, we prove the energy identity for a sequence of Sacks-Uhlenbeck maps during blowing up.

Building Morse/Floer type homology theories II

Series
Geometry Topology Working Seminar
Time
Friday, February 10, 2017 - 14:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
John Etnyre – Georgia Tech

Please Note: Note the semianr scheduled for 1.5 hours. (We might take a short break in the middle and then go slightly longer.)

In this series of talks I will descibe a general proceedure to construct homology theories using analytic/geometric techiques. We will then consider Morse homology in some detail and a simple example of this process. Afterwords we will consider other situations like Floer theory and possibly contact homology.

Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings

Series
ACO Student Seminar
Time
Friday, February 10, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sarah Cannon – College of Computing, Georgia Tech
We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall, and Spencer in 2002. The technique used, adapted from spin system analysis in statistical physics and not widely used in computer science literature, involves a multilevel decomposition of the state space and is of independent interest. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2^{-s}, (a+1)2^{-s}] x [b2^{-t}, (b+1)2^{-t}] for non-negative integers a,b,s,t. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n^{4.09}), which implies that the mixing time is at most O(n^{5.09}). We complement this by showing that the relaxation time is at least \Omega(n^{1.38}), improving upon the previously best lower bound of \Omega(n log n) coming from the diameter of the chain. This is joint work with David Levin and Alexandre Stauffer.

Geodesics in First-Passage Percolation

Series
Stochastics Seminar
Time
Thursday, February 9, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Christopher Hoffman – University of Washington –
First-passage percolation is a classical random growth model which comes from statistical physics. We will discuss recent results about the relationship between the limiting shape in first passage percolation and the structure of the infinite geodesics. This incudes a solution to the midpoint problem of Benjamini, Kalai and Schramm. This is joint work with Gerandy Brito and Daniel Ahlberg.

Large Even Factors of Graphs

Series
Graph Theory Seminar
Time
Thursday, February 9, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Genghua Fan – Center for Discrete Mathematics, Fuzhou University
A spanning subgraph $F$ of a graph $G$ iscalled an even factor of $G$ if each vertex of $F$ has even degreeat least 2 in $F$. It was proved that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)$, which is best possible. Recently, Cheng et al.extended the result by considering vertices of degree 2. They provedthat if a graph $G$ has an even factor, then it has an even factor$F$ with $|E(F)|\geq {4\over 7}(|E(G)| + 1)+{1\over 7}|V_2(G)|$,where $V_2(G)$ is the set of vertices of degree 2 in $G$. They alsogave examples showing that the second coefficient cannot be largerthan ${2\over 7}$ and conjectured that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)+ {2\over 7}|V_2(G)|$. We note that the conjecture isfalse if $G$ is a triangle. We confirm the conjecture for all graphson at least 4 vertices. Moreover, if $|E(H)|\leq {4\over 7}(|E(G)| +1)+ {2\over 7}|V_2(G)|$ for every even factor $H$ of $G$, then everymaximum even factor of $G$ is a 2-factor in which each component isan even circuit.

Pages