## Seminars and Colloquia by Series

Friday, December 8, 2017 - 15:00 , Location: Skiles 005 , Matthew Yancey , Inst. for Defense Analysis , Organizer: Lutz Warnke
Friday, December 1, 2017 - 15:00 , Location: Skiles 005 , , MIT , , Organizer: Lutz Warnke
Suppose we want to find the largest independent set or maximal cut in a sparse Erdos-Renyi graph, where the average degree is constant. Many algorithms proceed by way of local decision rules, for instance, the "nibbling" procedure. I will explain a form of local algorithms that captures many of these. I will then explain how these fail to find optimal independent sets or cuts once the average degree of the graph gets large. There are some nice connections to entropy and spin glasses.
Friday, November 24, 2017 - 14:00 , Location: Skiles 005 , none , Georgia Tech , Organizer: Lutz Warnke
Official School Holiday: Thanksgiving Break
Friday, November 17, 2017 - 15:00 , Location: Skiles 005 , Huseyin Acan , Rutgers University , Organizer: Lutz Warnke
Thursday, November 9, 2017 - 15:00 , Location: Skiles 006 , Elliot Paquette , The Ohio State University , , Organizer: Lutz Warnke
We study an online algorithm for making a well—equidistributed random set of points in an interval, in the spirit of "power of choice" methods. Suppose finitely many distinct points are placed on an interval in any arbitrary configuration. This configuration of points subdivides the circle into a finite number of intervals. At each time step, two points are sampled uniformly from the interval. Each of these points lands within some pair of intervals formed by the previous configuration. Add the point that falls in the larger interval to the existing configuration of points, discard the other, and then repeat this process. We then study this point configuration in the sense of its largest interval, and discuss other "power of choice" type modifications. Joint work with Pascal Maillard.
Friday, November 3, 2017 - 15:00 , Location: Skiles 005 , , Courant Institute, New York University , Organizer: Lutz Warnke
The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe, America, Korea and Rio de Janiero. We explore it through a CS lens, giving algorithms that provide the various upper and lower bounds. The arguments are various more or less sophisticated uses of Erdoes Magic and, indeed, many of the most important advances in the Probabilistic Method have come from these investigations.
Friday, October 27, 2017 - 15:00 , Location: Skiles 005 , Megan Bernstein , Georgia Tech , Organizer: Lutz Warnke
Friday, October 20, 2017 - 11:00 , Location: Skiles 005 , , University of Toronto , Organizer: Lutz Warnke
We prove that every triangle-free graph with maximum degree $D$ has list chromatic number at most $(1+o(1))\frac{D}{\ln D}$. This matches the best-known bound for graphs of girth at least 5.  We also provide a new proof  that for any $r \geq 4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{D\ln\ln D}{\ln D}$.
Friday, October 13, 2017 - 15:00 , Location: Skiles 005 , Heather Smith , Georgia Tech , Organizer: Lutz Warnke
The original notion of poset dimension is due to Dushnik and Miller (1941). Last year, Uerckerdt (2016) proposed a variant, called local dimension, which has garnered considerable interest. A local realizer of a poset P is a collection of partial linear extensions of P that cover the comparabilities and incomparabilities of P. The local dimension of P is the minimum frequency of a local realizer where frequency is the maximum multiplicity of an element of P. Hiraguchi (1955) proved that any poset with n points has dimension at most n/2, which is sharp. We prove that the local dimension of a poset with n points is O(n/log n). To show that this bound is best possible, we use probabilistic methods to prove the following stronger result which extends a theorem of Chung, Erdős, and Spencer (1983): There is an n-vertex bipartite graph in which each difference graph cover of the edges will cover one of the vertices Θ(n/log n) times. (This is joint work with Jinha Kim, Ryan R. Martin, Tomáš Masařı́k, Warren Shull, Andrew Uzzell, and Zhiyu Wang)
Friday, October 6, 2017 - 15:00 , Location: Skiles 005 , Matas Sileikis , Charles University Prague , Organizer: Lutz Warnke
Given a (fixed) graph H, let X be the number of copies of H in the random binomial graph G(n,p). In this talk we recall the results on the asymptotic behaviour of X, as the number n of vertices grows and pis allowed to depend on. In particular we will focus on the problem of estimating probability that X is significantly larger than its expectation, which earned the name of the 'infamous upper tail'.