Seminars and Colloquia by Series

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 Spencer – Courant 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 Bernstein – Georgia 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 Smith – Georgia 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 Sileikis – Charles 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
none – Georgia 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.

Dushnik-Miller dimension and Two Variations

Series
Combinatorics Seminar
Time
Friday, September 15, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tom Trotter – Georgia Tech
The original concept ofdimension for posets was formulatedby Dushnik and Miller in 1941 and hasbeen studied extensively in the literature.Over the years, a number of variant formsof dimension have been proposed withvarying degrees of interest and application.However, in the recent past, two variantshave received extensive attention. Theyare Boolean dimension and local dimension.This is the first of two talks on these twoconcepts, with the second talk givenby Heather Smith. In this talk, wewill introduce the two parameters and providemotivation for their study. We will alsogive some concrete examples andprove some basic inequalities.This is joint work with a GeorgiaTech team in which my colleaguesare Fidel Barrera-Cruz, Tom Prag,Heather Smith and Libby Taylor.

High degree vertices on recursive trees

Series
Combinatorics Seminar
Time
Friday, September 8, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Laura Eslava – Georgia Tech
Among the most studied tree growth processes there are recursive trees and linear preferential attachment trees. The study of these two models is motivated by the need of understanding the evolution of social networks. A key feature of social networks is the presence of vertices that serve as hubs, connecting large parts of the network. While such type of vertices had been widely studied for linear preferential attachment trees, analogous results for recursive trees were missing. In this talk, we will present joint laws for both the number and depth of vertices with near-maximal degrees and comment on the possibilities that our methods open for future research. This is joint work with Louigi Addario-Berry.

Rogue Fixed Points of Tree Automata on Galton-Watson Trees

Series
Combinatorics Seminar
Time
Friday, September 1, 2017 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Moumanti Podder – Georgia Tech –
This talk will focus on tree automata, which are tools to analyze existential monadic second order properties of rooted trees. A tree automaton A consists of a finite set \Sigma of colours, and a map \Gamma: \mathbb{N}^\Sigma \rightarrow \Sigma. Given a rooted tree T and a colouring \omega: V(T) \rightarrow \Sigma, we call \omega compatible with automaton A if for every v \in V(T), we have \omega(v) = \Gamma(\vec{n}), where \vec{n} = (n_\sigma: \sigma \in \Sigma) and n_\sigma is the number of children of v with colour \sigma. Under the Galton-Watson branching process set-up, if p_\sigma denotes the probability that a node is coloured \sigma, then \vec{p} = (p_\sigma: \sigma \in \Sigma) is obtained as a fixed point of a system of equations. But this system need not have a unique fixed point. Our question attempts to answer whether a fixed point of such a system simply arises out of analytic reasons, or if it admits of a probabilistic interpretation. I shall formally defined interpretation, and provide a nearly complete description of necessary and sufficient conditions for a fixed point to not admit an interpretation, in which case it is called rogue.Joint work with Tobias Johnson and Fiona Skerman.

Pages