- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

The flow polytope associated to an acyclic graph is the set of all
nonnegative flows on the edges of the graph with a fixed netflow at each
vertex. We will examine flow polytopes arising from permutation matrices,
alternating sign matrices and Tesler matrices. Our inspiration is the
Chan-Robins-Yuen polytope (a face of the polytope of doubly-stochastic
matrices), whose volume is equal to the product of the first n Catalan
numbers (although there is no known combinatorial proof of this fact!). The
volumes of the polytopes we study all have nice product formulas.

Series: Combinatorics Seminar

The theme of this talk is walks in a random environment of "signposts"
altered by the walker. I'll focus on three related examples:
1. Rotor walk on Z^2. Your initial signposts are independent with the
uniform distribution on {North,East,South,West}. At each step you rotate
the signpost at your current location clockwise 90 degrees and then follow
it to a nearest neighbor. Priezzhev et al. conjectured that in n such steps
you will visit order n^{2/3} distinct sites. I'll outline an elementary
proof of a lower bound of this order. The upper bound, which is still open,
is related to a famous question about the path of a light ray in a grid of
randomly oriented mirrors. This part is joint work with Laura Florescu and
Yuval Peres.
2. p-rotor walk on Z. In this walk you flip the signpost at your current
location with probability 1-p and then follow it. I'll explain why your
scaling limit will be a Brownian motion perturbed at its extrema. This part
is joint work with Wilfried Huss and Ecaterina Sava-Huss.
3. p-rotor walk on Z^2. Rotate the signpost at your current location
clockwise with probability p and counterclockwise with probability 1-p, and
then follow it. This walk “organizes” its environment of signposts. The
stationary environment is an orientation of the uniform spanning forest,
plus one additional edge. This part is joint work with Swee Hong Chan, Lila
Greco and Boyao Li.

Series: Combinatorics Seminar

I will talk about the problem of computing the number of integer partitions
into parts lying in some integer sequence. We prove that for certain
classes of infinite sequences the number of associated partitions of an
input N can be computed in time polynomial in its bit size, log N. Special
cases include binary partitions (i.e. partitions into powers of two) that
have a key connection with Cayley compositions and polytopes. Some
questions related to algebraic differential equations for partition
sequences will also be discussed.
(This is joint work with Igor Pak.)

Series: Combinatorics Seminar

Researchers here at Georgia Tech initiated a "Ramsey Theory" on binary trees and used the resulting tools to show that the local dimension of a poset is not bounded in terms of the tree-width of its cover graph. Subsequently, in collaboration with colleagues in Germany and Poland, we extended these Ramsey theoretic tools to solve a problem posed by Seymour. In particular, we showed that there is an infinite sequence of graphs with bounded tree-chromatic number and unbounded path-chromatic number. An interesting detail is that our research showed that a family conjectured by Seymour to have this property did not. However, the insights gained in this work pointed out how an appropriate modification worked as intended.
The Atlanta team consists of Fidel Barrera-Cruz, Heather Smith, Libby Taylor and Tom Trotter The European colleagues are Stefan Felsner, Tamas Meszaros, and Piotr Micek.