Seminars and Colloquia by Series

Friday, December 7, 2018 - 15:00 , Location: None , None , None , Organizer: Lutz Warnke
Friday, November 23, 2018 - 15:00 , Location: None , None , None , Organizer: Lutz Warnke
Friday, October 19, 2018 - 15:00 , Location: Skiles 005 , Boris Bukh , Carnegie Mellon University , Organizer: Lutz Warnke
Friday, October 12, 2018 - 15:00 , Location: Skiles 005 , Prasad Tetali , Georgia Tech , Organizer: Lutz Warnke
Friday, September 28, 2018 - 15:00 , Location: Skiles 005 , Lutz Warnke , Georgia Tech , Organizer: Lutz Warnke
In 1973 Erdos asked whether there are n-vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integer g \ge 4 for which some g-element vertex-set contains at least g-2 triples.) We answer this question, by showing existence of approximate Steiner triple systems with arbitrary high girth. More concretely, for any fixed \ell \ge 4 we show that a natural constrained random process typically produces a partial Steiner triple system with (1/6-o(1))n^2 triples and girth larger than \ell. The process iteratively adds random triples subject to the constraint that the girth remains larger than \ell. Our result is best possible up to the o(1)-term, which is a negative power of n. Joint work with Tom Bohman.
Friday, September 21, 2018 - 15:00 , Location: Skiles 005 , Yi Zhao , Georgia State University , Organizer: Lutz Warnke
For integers k>2 and \ell0, there exist \epsilon>0 and C>0 such that for sufficiently large n that is divisible by k-\ell,the union of a k-uniform hypergraph with minimum vertex degree \alpha n^{k-1} and a binomial random k-uniform hypergraph G^{k}(n,p) on the same n-vertex set with p\ge n^{-(k-\ell)-\epsilon} for \ell\ge 2 and p\ge C n^{-(k-1)} for \ell=1 contains a Hamiltonian \ell-cycle with high probability. Our result is best possible up to the values of \epsilon and C and completely answers a question of Krivelevich, Kwan and Sudakov.This is a joint work with Jie Han.
Friday, September 14, 2018 - 15:00 , Location: Skiles 005 , Ernie Croot , Georgia Tech , Organizer: Lutz Warnke
Friday, September 7, 2018 - 15:00 , Location: Skiles 005 , Joshua Cooper , University of South Carolina , Organizer: Lutz Warnke
Friday, August 31, 2018 - 15:00 , Location: None , None , None , Organizer: Lutz Warnke
Monday, August 20, 2018 - 15:05 , Location: Skiles 005 , Esther Ezra , Georgia Tech , Organizer: Prasad Tetali
A recent extension by Guth (2015) of the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial for a given set of k-dimensional varieties in R^d, such that its zero set subdivides space into open cells, each meeting only a small fraction of the given varieties.  For k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently.  This, in particular, applies to the setting of n algebraic curves, or, in fact, just lines, in 3-space.  In this work we present an efficient algorithmic construction for this setting almost matching the bounds of Guth (2015); For any D > 0, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open cells, each of which meets at most O(n/D^2) curves from the input.  The construction time is O(n^2), where the constant of proportionality depends on the maximum degree of the polynomials defining the input curves.  For the case of lines in 3-space we present an improved implementation using a range search machinery. As a main application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently been studied by Aronov et al.  Joint work with Boris Aronov and Josh Zahl.

Pages