Seminars and Colloquia by Series

Friday, April 15, 2016 - 15:00 , Location: Skiles 005 , Ohad Noy Feldheim , Stanford University , Organizer: Esther Ezra

Joint work with Yinon Spinka.

Consider a random coloring of a bounded domain in the bipartite graph Z^d with the probability of each color configuration proportional to exp(-beta*N(F)), where beta>0, and N(F) is the number of nearest neighboring pairs colored by the same color. This model of random colorings biased towards being proper, is the antiferromagnetic 3-state Potts model from statistical physics, used to describe magnetic interactions in a spin system. The Kotecky conjecture is that in such a model with d >= 3, Fixing the boundary of a large even domain to take the color $0$ and high enough beta, a sampled coloring would typically exhibits long-range order. In particular a single color occupies most of either the even or odd vertices of the domain. This is in contrast with the situation for small beta, when each bipartition class is equally occupied by the three colors. We give the first rigorous proof of the conjecture for large d. Our result extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the zero beta=infinity case, where the coloring is chosen uniformly for all proper three-colorings. In the talk we shell give a glimpse into the combinatorial methods used to tackle the problem. These rely on structural properties of odd-boundary subsets of Z^d. No background in statistical physics will be assumed and all terms will be thoroughly explained. 
Friday, April 1, 2016 - 15:00 , Location: Skiles 005 , Christian Houdré , Georgia Tech , Organizer: Esther Ezra
Both for random words or random permutations, I will present a panoramic view of  results on the (asymptotic) behavior of the length of the longest common subsequences . Starting with, now, classical results on expectations dating back to the nineteen-seventies I will move to recent results obtained by Ümit Islak and myself giving the asymptotic laws of this length and as such answering a decades-old well know question. 
Friday, March 11, 2016 - 15:05 , Location: Skiles 005 , Matt Baker , School of Mathematics, Georgia Tech , Organizer: Esther Ezra
We present an algebraic framework which simultaneously generalizes the notion of linear subspaces, matroids, valuated matroids, and oriented matroids. We call the resulting objects matroids over hyperfields. We give "cryptomorphic" axiom systems for such matroids in terms of circuits, Grassmann-Plucker functions, and dual pairs, and establish some basic duality theorems.
Friday, January 22, 2016 - 16:00 , Location: Skiles 154 , Georgios Petridis , University of Rochester , , Organizer: Esther Ezra
We show that there exists an absolute constant c>0 with the following property. Let A be a set in a finite field with q elements.  If |A|>q^{2/3-c}, then the set (A-A)(A-A) consisting of products of pairwise differences of elements of A contains at least q/2 elements. It appears that this is the first instance in the literature where such a conclusion is reached for such type sum-product-in-finite-fileds questions for sets of smaller cardinality than q^{2/3}. Similar questions have been investigated by Hart-Iosevich-Solymosi and Balog.
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 , Esther Ezra , 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 , Heather Smith , 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)