Seminars and Colloquia by Series

Thursday, January 22, 2015 - 12:05 , Location: Skiles 005 , Peter Csikvari , MIT , , Organizer: Prasad Tetali
 In this talk we will survey some recent development on statistical properties of matchings of very large and infinite graphs. The main goal of the talk is to describe a few applications of a new concept called matching measure. These applications include new results on the number of (perfect) matchings in large girth graphs as well as simple new proofs of certain statistical physical theorems. In particular, we will sketch the proof of Friedland's Lower Matching Conjecture, and a new proof of Schrijver's and Gurvits's theorems. This talk is based on joint papers with various subsets of Miklos Abert, Peter E. Frenkel, Tamas Hubai and Gabor Kun.
Tuesday, January 13, 2015 - 12:05 , Location: Skiles 005 , Emma Cohen , Georgia Tech , Organizer: Prasad Tetali
Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. We consider natural local moves on some realizations of the Catalan sequence and derive estimates of the mixing time of the corresponding Markov chains. We present a new O(n^2 log n) bound on the mixing time for the random transposition chain on Dyck paths, and raise several open problems, including the optimality of the above bound.  (Joint work with Prasad Tetali and Damir Yelliusizov.)
Tuesday, January 6, 2015 - 12:05 , Location: Skiles 005 , Hiep Han , Emory University and University of Sao Paulo, Brazil , , Organizer: Prasad Tetali
Let B(d,n) denote the d-regular graph on n vertices which consists of the disjoint union of complete bipartite graphs. It follows from the results of Kahn and of Zhao that among all d-regular graphs on n vertices B(d,n) maximizes the number of independent sets. In this talk, we show a spectral stability phenomenon of this result in the following sense. The eigenvalues of (the adjacency matrix) of B(d,n) are known to be d, -d and zeroes and  we show that, if the smallest eigenvalue of G is bounded away from -d, then the number of independent sets in G is exponentially smaller than that of B(d,n). Furthermore, we extend this method to study the well-known hard-core model from statistical physics. Given a d-regular bipartite graph G whose second smallest eigenvalue is bounded away from -d. Let Ind(G) denote the set of all independent sets of G. Among others, we show that in this case the random independent set I\in Ind(G), drawn from the hard-core distribution with activation parameter lambda>> (log d)/d, is essentially completely (up to o(|I|) vertices) contained in one of the partition classes of G. (This is joint work with Prasad Tetali.)
Tuesday, December 9, 2014 - 13:35 , Location: Skiles 005 , Maksim Zhukovskii , MIPT, Moscow, Russia , Organizer: Prasad Tetali
In the talk, an asymptotic behaviour of first order properties of the Erdos-Renyi random graph G(n,p) will be considered. The random graph obeys the zero-one law if for each first-order property L either its probability tends to 0 or tends to 1. The random graph obeys the zero-one k-law if for each property L which can be expressed by first-order formula with quantifier depth at most k either its probability tends to 0 or tends to 1. Zero-one laws were proved for different classes of functions p=p(n). The class n^{-a} is at the top of interest. In 1988 S. Shelah and J.H. Spencer proved that the random graph G(n,n^{-a}) obeys zero-one law if a is positive and irrational. If a is rational from the interval (0,1], then G(n,n^{-a}) does not obey the zero-one law. I obtain zero-one k-laws for some rational a from (0,1]. For any first-order property L let us consider the set S(L) of a from (0,1) such that a probability of G(n,n^{-a}) to satisfy L does not converges or its limit is not zero or one. Spencer proved that there exists L such that S(L) is infinite. Recently in the joint work with Spencer we obtain new results on a distribution of elements of S(L) and its limit points.
Tuesday, December 2, 2014 - 13:30 , Location: Skiles 005 , Laura Florescu , Courant Institute, NYU , Organizer: Prasad Tetali
In a "rotor walk" the exits from each vertex follow a prescribed periodic sequence. On an infinite Eulerian graph embedded periodically in $\R^d$, we show that any simple rotor walk, regardless of rotor mechanism or initial rotor configuration, visits at least on the order of t^{d/(d+1)} distinct sites in t steps. We prove a shape theorem for the rotor walk on the comb graph with i.i.d.\ uniform initial rotors, showing that the range is of order t^{2/3} and the asymptotic shape of the range is a diamond. Using a connection to the mirror model and critical percolation, we show that rotor walk with i.i.d. uniform initial rotors is recurrent on two different directed graphs obtained by orienting the edges of the square grid, the Manhattan lattice and the F-lattice. Joint work with Lionel Levine and Yuval Peres.
Tuesday, November 25, 2014 - 13:30 , Location: Skiles 005 , Matt Baker , Georgia Tech , Organizer: Prasad Tetali
The Jacobian group Jac(G) of a finite graph G is a finite abelian group whose cardinality is the number of spanning trees of G.  It is natural to wonder whether there is a canonical simply transitive action of Jac(G) on the set of spanning trees which "explains" this numerical coincidence.  Surprisingly, this turns out to be related to topological embeddings: we will explain a certain precise sense in which the answer is yes if and only if G is planar.  We will also explain how tropical geometry sheds an interesting new light on this picture.  
Tuesday, November 4, 2014 - 13:30 , Location: Skiles 005 , Jie Han , Georgia State University , Organizer: Xingxing Yu
In graph/hypergraph theory, perfect matchings are fundamental objects of study. Unlike the graph case, perfect matchings in hypergraphs have not been well understood yet. It is quite natural and desirable to extend the classical theory on perfect matchings from graphs to hypergraphs, as many important problems can be phrased in this framework, such as Ryser's conjecture on transversals in Latin squares and the Existence Conjecture for block designs. I will focus on Dirac-type conditions (minimum degree conditions) in uniform hypergraphs and discuss some recent progresses. In particular, we determine the minimum codegree threshold for the existence of a near perfect matching in hypergraphs, which confirms a conjecture of Rodl, Rucinski and Szemeredi, and we show that there is a polynomial-time algorithm that can determine whether a k-uniform hypergraph with minimum codegree n/k has a perfect matching, which solves a problem of Karpinski, Rucinski and Szymanska completely.
Wednesday, October 29, 2014 - 15:05 , Location: Skiles 006 , Olivier Bernardi , Brandeis University , Organizer: Matt Baker
We will present the solution to a statistical mechanics model on random lattices. More precisely, we consider the Potts model on the set of planar triangulations (embedded planar graph such that every face has degree 3).  The partition function of this model is the generating function of vertex-colored triangulations counted according to the number of monochromatic edges and dichromatic edges. We characterize this partition function by a simple system of differential equations.  Some special cases, such as properly 4-colored triangulations, lead to particularly simple equations waiting for a more direct combinatorial explanation. This is joint work with Mireille Bousquet-Melou.
Tuesday, October 21, 2014 - 13:30 , Location: Skiles 005 , Esther Ezra , NYU Polytechnic School of Engineering , Organizer: Prasad Tetali
 In this talk I will present the notion of a \delta-packing for set systems of bounded primal shatter dimension (closely related to the notion of finite VC-dimension). The structure of \delta-packing, which has been studied by Dudley in 1978 and Haussler in 1995, emerges from empirical processes and is fundamental in theoretical computer science and in computational geometry in particular. Moreover, it has applications in geometric discrepancy, range searching, and epsilon-approximations, to name a few. I will discuss a variant of \delta-packings where all the sets have small cardinality, we call these structures "shallow packings", and then present an upper bound on their size under additional natural assumptions on the set system, which correspond to several geometric settings, among which is the case of points and halfspaces in d-dimensions.  
Tuesday, October 7, 2014 - 13:30 , Location: Skiles 005 , Georgios Piliouras , Cal Tech , Organizer: Prasad Tetali

Bio: Georgios Piliouras is a postdoc at Caltech, Center for Mathematics and
Computation. He received his PhD in Computer Science from Cornell
University and has been a Georgia Tech postdoc at the EE department.

In a recent series of papers a strong connection has been established between standard models of sexual evolution in mathematical biology and Multiplicative Weights Updates Algorithm, a ubiquitous model of online learning and optimization. These papers show that mathematical models of biological evolution are tantamount to applying discrete replicator dynamics, a close variant of MWUA on coordination games. We show that in the case of coordination games, under minimal genericity assumptions, discrete replicator dynamics converge to pure Nash equilibria for all but a zero measure of initial conditions. This result holds despite the fact that mixed Nash equilibria can be exponentially (or even uncountably) many, completely dominating in number the set of pure Nash equilibria. Thus, in haploid organisms the long term preservation of genetic diversity needs to be safeguarded by other evolutionary mechanisms, such as mutation and speciation. This is joint work with Ruta Mehta and Ioannis Panageas.