## Seminars and Colloquia by Series

### 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, 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)

### 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.

### 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 TrotterGeorgia 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 EslavaGeorgia 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 PodderGeorgia 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.

### Counting vertices in labeled rooted trees

Series
Combinatorics Seminar
Time
Friday, April 21, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Miklós BónaUniversity of Florida
Various parameters of many models of random rooted trees are fairly well understood if they relate to a near-root part of the tree or to global tree structure. In recent years there has been a growing interest in the analysis of the random tree fringe, that is, the part of the tree that is close to the leaves. Distance from the closest leaf can be viewed as the protection level of a vertex, or the seniority of a vertex within a network. In this talk we will review a few recent results of this kind for a number of tree varieties, as well as indicate the challenges one encounters when trying to generalize the existing results. One tree variety, that of decreasing binary trees, will be related to permutations, another one, phylogenetic trees, is frequent in applications in molecular biology.

### The Erdos-Ko-Rado Theorem and Generalizations on Graphs

Series
Combinatorics Seminar
Time
Friday, April 14, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Glenn HurlbertVirginia Commonwealth University
The fundamental EKR theorem states that, when n≥2r, no pairwise intersecting family of r-subsets of {1,2,...,n} is larger than the family of all r-subsets that each contain some fixed x (star at x), and that a star is strictly largest when n>2r. We will discuss conjectures and theorems relating to a generalization to graphs, in which only independent sets of a graph are allowed. In joint work with Kamat, we give a new proof of EKR that is injective, and also provide results on a special class of trees called spiders.