Seminars and Colloquia by Series

Friday, April 21, 2017 - 15:05 , Location: Skiles 005 , Miklós Bóna , University of Florida , bona@ufl.edu , Organizer: Torin Greenwood
  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. 
Friday, April 14, 2017 - 15:05 , Location: Skiles 005 , Glenn Hurlbert , Virginia Commonwealth University , ghurlbert@vcu.edu , Organizer: Heather Smith
Friday, April 7, 2017 - 16:00 , Location: Skiles 005 , Karola Meszaros , Cornell University , karola@math.cornell.edu , Organizer: Megan Bernstein
Friday, April 7, 2017 - 15:00 , Location: Skiles 005 , Lionel Levine , Cornell University , Organizer: Megan Bernstein
Monday, March 27, 2017 - 15:05 , Location: Skiles 005 , Damir Yeliussizov , UCLA , yeldamir@gmail.com , Organizer: Prasad Tetali
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.)
Friday, March 10, 2017 - 15:05 , Location: Skiles 005 , Tom Trotter , Georgia Tech , Organizer: Fidel Barrera-Cruz
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.
Friday, March 3, 2017 - 15:05 , Location: Skiles 005 , Tomasz Łuczak , Adam Mickiewicz University , tomasz@amu.edu.pl , Organizer: Lutz Warnke
In the talk we state, explain, comment, and finally prove a theorem (proved jointly with Yuval Peled) on the size and the structure of certain homology groups of random simplicial complexes. The main purpose of this presentation is to demonstrate that, despite topological setting, the result can be viewed as a statement on Z-flows in certain model of random hypergraphs, which can be shown using elementary algebraic and combinatorial tools.
Friday, February 24, 2017 - 15:05 , Location: Skiles 005 , Jay Pantone , Dartmouth College , jaypantone@dartmouth.edu , Organizer: Torin Greenwood
In enumerative combinatorics, it is quite common to have in hand a number of known initial terms of a combinatorial sequence whose behavior you'd like to study. In this talk we'll describe two techniques that can be used to shed some light on the nature of a sequence using only some known initial terms. While these methods are, on the face of it, experimental, they often lead to rigorous proofs. As we talk about these two techniques -- automated conjecturing of generating functions, and the method of differential approximation -- we'll exhibit their usefulness through a variety of combinatorial topics, including matchings, permutation classes, and inversion sequences.
Friday, February 17, 2017 - 15:05 , Location: Skiles 005 , Csaba Biró , University of Louisville , Organizer: Fidel Barrera-Cruz
Many classical hard algorithmic problems on graphs, like coloring, clique number, or the Hamiltonian cycle problem can be sped up for planar graphs resulting in algorithms of time complexity $2^{O(\sqrt{n})}$. We study the coloring problem of unit disk intersection graphs, where the number of colors is part of the input. We conclude that, assuming the Exponential Time Hypothesis, no such speedup is possible. In fact we prove a series of lower bounds depending on further restrictions on the number of colors. Generalizations for other shapes and higher dimensions were also achieved. Joint work with E. Bonnet, D. Marx, T. Miltzow, and P Rzazewski.
Friday, February 10, 2017 - 15:05 , Location: Skiles 005 , Bartosz Walczak , Jagiellonian University in Kraków , walczak@tcs.uj.edu.pl , Organizer: Heather Smith
A class of graphs is *χ-bounded* if the chromatic number of all graphs in the class is bounded by some function of their clique number. *String graphs* are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are *χ*-bounded. In particular, it is known since 2012 that the class of all string graphs is not *χ*-bounded. We prove that for every integer *t*≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve *c* in at least one and at most *t* points is *χ*-bounded. This result is best possible in several aspects; for example, the upper bound *t* on the number of crossings of each curve with *c* cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called *k*-quasi-planar topological graphs. This is joint work with Alexandre Rok.

Pages