Seminars and Colloquia by Series

Wednesday, January 20, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of $K_5$. This conjecture was proved by Ma and Yu for graphs containing $K_4^-$. Recently, we proved this entire Kelmans-Seymour conjecture. In this talk, I will give a sketch of our proof, and discuss related problems. This is joint work with Dawei He and Xingxing Yu.
Friday, January 15, 2016 - 15:05 , Location: Skiles 006 , June Huh , Princeton / IAS , Organizer: Josephine Yu
I will give a broad overview of the Hard Lefschetz property and the Hodge-Riemann relations in the theory of polytopes, complex manifolds, invariants, algebraic varieties, and tropical varieties.
Friday, December 4, 2015 - 15:00 , Location: Skiles 005 , , Georgia Tech , , Organizer: Esther Ezra

Joint work with Shachar Lovett.

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,\Sigma), where each element x \in X lies in t randomly selected sets of \Sigma, where t \le |X| is an integer parameter. We provide new discrepancy bounds in this case. Specifically, we show that when |\Sigma| \ge |X| the hereditary discrepancy of (X,\Sigma) is with high probability O(\sqrt{t \log t}), matching the Beck-Fiala conjecture upto a \sqrt{\log{t}} factor. Our analysis combines the Lov{\'a}sz Local Lemma with a new argument based on partial matchings.
Friday, November 20, 2015 - 15:00 , Location: Skiles 006 , , Georgia Tech , , Organizer: Esther Ezra
Represent a genome with an edge-labelled, directed graph having maximum total degree two. We explore a number of questions regarding genome rearrangement, a common mode of molecular evolution. In the single cut-or-join model for genome rearrangement, a genome can mutate in one of two ways at any given time: a cut divides a degree two vertex into two degree one vertices while a join merges two degree one vertices into one degree two vertex. Fix a set of genomes, each having the same set of edge labels. The number of ways for one genome to mutate into another can be computed in polynomial time. The number of medians can also be computed in polynomial time. While single cut-or-join is, computationally, the simplest mathematical model for genome rearrangement, determining the number of most parsimonious median scenarios remains #P-complete. We will discuss these and other complexity results that arose from an abstraction of this problem. [This is joint work with Istvan Miklos.]
Friday, October 9, 2015 - 15:00 , Location: Skiles 005 , Torin Greenwood , Georgia Tech , , Organizer: Esther Ezra
Flajolet and Odlyzko (1990) derived asymptotic formulae for the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Gao and Richmond (1992) and Hwang (1996, 1998), in both cases by reducing the multivariate case to the univariate case. Pemantle and Wilson (2013) outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions. In this talk, we discuss these multivariate analytic techniques and use them to find asymptotic formulae for the coefficients of a broad class of bivariate generating functions with algebraic singularities.  We will also look at how to apply such formulae to practical problems.
Friday, October 2, 2015 - 15:00 , Location: Skiles 005 , Fidel Barrera Cruz , Georgia Tech , , Organizer: Esther Ezra
A morph between two drawings of the same graph can be thought of as a continuous deformation between the two given drawings. In this talk we consider the algorithmic problem of morphing between any two planar drawings of a planar triangulation while preserving planarity during the morph. We outline two different solutions to the morphing problem. The first solution gives a strengthening of the result of Alamdari et al. where each step is a unidirectional morph. The second morphing algorithm finds a planar morph consisting of O(n²) steps between any two Schnyder drawings while remaining in an O(n)×O(n) grid, here n is the number of vertices of the graph. However, there are drawings of planar triangulations which are not Schnyder drawings, and for these drawings we show that a unidirectional morph consisting of O(n) steps that ends at a Schnyder drawing can be found. (Joint work with Penny Haxell and Anna Lubiw)
Friday, September 18, 2015 - 15:00 , Location: Skiles 005 , , The University of New Mexico , , Organizer: Esther Ezra
In the Rendezvous problem on the complete graph, two parties are trying to meet at some vertex at the same time, despite starting out with independent random labelings of the vertices. It is well known that the optimal strategy is for one player to wait at any vertex, while the other visits all n vertices in consecutive steps, which guarantees a rendezvous within n steps and takes (n + 1)/2 steps on average. This strategy is very far from being symmetric, however. E. Anderson and R. Weber presented a symmetric algorithm that achieves an expected meeting time of 0.829n, which has been conjectured to be optimal in the symmetric setting. We change perspective slightly: instead of trying to minimize the expected meeting time, we try to maximize the probability of successfully meeting within a specified number of timesteps. In this setting, for all time horizons that are linear in n, the Anderson-Weber strategy has a constant probability of failure. Surprisingly, we show that this is not optimal: there exists a different symmetric strategy that almost surely guarantees meeting within 4n timesteps. This bound is tight, in that the factor 4 cannot be replaced by any smaller constant. Our strategy depends on the construction of a new kind of combinatorial object that we dub”rendezvous code.”On the positive side, for T < n, we show that the probability of meeting within T steps is indeed (approximately) maximized by the Anderson-Weber strategy. Our results imply new lower bounds on the expected meeting time for any symmetric strategy, which establishes an asymptotic difference between the best symmetric and asymmetric strategies. Finally, we examine the symmetric rendezvous problem on other vertex-transitive graphs.
Wednesday, September 16, 2015 - 16:00 , Location: Skiles 006 , , University of Cambridge , , Organizer: Esther Ezra
Let $T$ be a finite subset of  ${\Bbb Z}^n$. It may or may not tile  ${\Bbb Z}^n$, in the sense of  ${\Bbb Z}^n$ having a partition into copies of $T$. But is there a dimension $d$ such that $T$ does tile  ${\Bbb Z}^d$ ? Our talk will focus on this question.
Friday, September 11, 2015 - 15:00 , Location: Skiles 005 , Megan Bernstein , Georgia Tech , Organizer: Esther Ezra
I will find upper and lower bounds for the mixing time as well as the likelihood order after sufficient time of the following involution walk on the symmetric group. Consider 2n cards on a table. Pair up all the cards. Ignore each pairing with probability $p \geq 1/2$. For any pair not being ignored, pick up the two cards and switch their spots. This walk is generated by involutions with binomially distributed two cycles. The upper bound of $\log_{2/(1+p)}(n)$ will result from spectral analysis using a combination of a series of monotonicity relations on the eigenvalues of the walk and the character polynomial for the representations of the symmetric group. A lower bound of $\log_{1/p}$ differs by a constant factor from the upper bound. This walk was introduced to study a conjecture about a random walk on the unitary group from the information theory of black holes.
Tuesday, May 19, 2015 - 13:30 , Location: Skiles 005 , Annachiara Korchmaros , University of Basilicata , Organizer: Christine Heitsch
In the study of combinatorial aspects of symmetric groups, a major problem arising from applications to Genetics consists in finding a minimum factorization of any permutation with factors from a given generating set. The difficulty in developing an adequate theory as well as the hardness of the computational complexity may heavily vary depending on the generator set. In this talk, the generating set consists of all block transpositions introduced by Bafna and Pevzner in 1998 for the study of a particular ''genome rearrangement problem''. Results, open problems, and generalizations are discussed in terms of Cayley graphs and their automorphism groups.