Seminars and Colloquia by Series

Disproof of a packing conjecture of Alon and Spencer

Series
Combinatorics Seminar
Time
Friday, November 17, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Huseyin AcanRutgers University
A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph G_{n,1/2} typically admits a covering of a constant fraction of its edges by edge-disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for k ≪ \sqrt{n} and A_1, ..., A_t chosen uniformly and independently from the k-subsets of {1…n}, what can one say about P(|A_i ∩ A_j|≤1 ∀ i≠j)? Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently. Joint work with Jeff Kahn.

Choices and Intervals (joint with Stochastics Seminar: note unusual date+time)

Series
Combinatorics Seminar
Time
Thursday, November 9, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Elliot PaquetteThe Ohio State University
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.

86 Years of Ramsey R(3,k). (and counting!)

Series
Combinatorics Seminar
Time
Friday, November 3, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Joel SpencerCourant Institute, New York University
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 Erdos Magic and, indeed, many of the most important advances in the Probabilistic Method have come from these investigations.

Progress in showing cutoff for random walks on the symmetric group

Series
Combinatorics Seminar
Time
Friday, October 27, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Megan BernsteinGeorgia Tech
Cutoff is a remarkable property of many Markov chains in which they rapidly transition from an unmixed to a mixed distribution. Most random walks on the symmetric group, also known as card shuffles, are believed to mix with cutoff, but we are far from being able to proof this. We will survey existing cutoff results and techniques for random walks on the symmetric group, and present three recent results: cutoff for a biased transposition walk, cutoff for the random-to-random card shuffle (answering a 2001 conjecture of Diaconis), and pre-cutoff for the involution walk, generated by permutations with a binomially distributed number of two-cycles. The results use either probabilistic techniques such as strong stationary times or diagonalization through algebraic combinatorics and representation theory of the symmetric group. Includes joint work with Nayantara Bhatnagar, Evita Nestoridi, and Igor Pak.

The list chromatic number of graphs with small clique number (joint with ARC; note the unusual time!)

Series
Combinatorics Seminar
Time
Friday, October 20, 2017 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mike Molloy University of Toronto
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}$.

Local dimension and size of a poset

Series
Combinatorics Seminar
Time
Friday, October 13, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Heather SmithGeorgia Tech
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, Erdő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, Tomáš Masařı́k, Warren Shull, Andrew Uzzell, and Zhiyu Wang)

Small subgraph counts in random graphs: a survey

Series
Combinatorics Seminar
Time
Friday, October 6, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Matas SileikisCharles University Prague
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'.

No seminar: ACO Student Seminar + ACO Colloquium + Atlanta Lecture Series (on Thursday + Friday + Weekend)

Series
Combinatorics Seminar
Time
Friday, September 29, 2017 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
noneGeorgia Tech
No Combinatorics Seminar, but many others of interest: (a) on Friday [September 29th, 1pm-2pm in Skiles 005] He Guo, will give an ACO Student Seminar on "Packing nearly optimal Ramsey R(3,t) Graphs" (b) on Thursday [September 28th, 11am-12am in Skiles 006] Tom Bohman will give an ACO colloquim talk on "Randomized Controlled Trials for Combinatorial Construction" (c) on Saturday and Sunday [September 30th and October 1st] Atlanta Lecture Series in Combinatorics and Graph Theory XX takes place at Georgia Tech, with featured speaker Paul Seymour

No Seminar: Ravi Kannan speaking in The IDEaS Seminar Series

Series
Combinatorics Seminar
Time
Friday, September 22, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
-
Speaker
--
Clash with "The IDEaS Seminar Series": the talk of Ravi Kannan at 3pm on "Topic Modeling: Proof to Practice" might of interest (Location: TSRB Auditorium) -- Topic Modeling is used in a variety of contexts. This talk will outline from first principles the problem, and the well-known Latent Dirichlet Al-location (LDA) model before moving to the main focus of the talk: Recent algorithms to solve the model-learning problem with provable worst-case error and time guarantees. We present a new algorithm which enjoys both provable guarantees as well performance to scale on corpora with billions of words on a single box. Besides corpus size, a second challenge is the growth in the number of topics. We address this with a new model in which topics lie on low-dimensional faces of the topic simplex rather than just vertices.

Pages