Seminars and Colloquia by Series

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.
Friday, April 27, 2018 - 15:00 , Location: Skiles 005 , Florian Frick , Cornell University , Organizer: Lutz Warnke
Given a collection of finite sets, Kneser-type problems aim to partition this collection into parts with well-understood intersection pattern, such as in each part any two sets intersect. Since Lovász' solution of Kneser's conjecture, concerning intersections of all k-subsets of an n-set, topological methods have been a central tool in understanding intersection patterns of finite sets. We will develop a method that in addition to using topological machinery takes the topology of the collection of finite sets into account via a translation to a problem in Euclidean geometry. This leads to simple proofs of old and new results.
Thursday, March 29, 2018 - 13:30 , Location: Skiles 005 , Jan Volec , McGill , Organizer: Lutz Warnke
A long-standing conjecture of Erdős states that any n-vertex triangle-free graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most 4n^2/25+O(n) edges. In the case of H=K_6, we actually prove the exact bound 4n^2/25 and show that this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of Füredi on stable version of Turán's theorem. This is a joint work with P. Hu, B. Lidický, T. Martins-Lopez and S. Norin.
Friday, March 16, 2018 - 15:00 , Location: Skiles 006 , Mark Skandera , Lehigh University , Organizer: Greg Blekherman
The (type A) Hecke algebra H_n(q) is an n!-dimensional q-analog of the symmetric group.  A related trace space of certain functions on H_n(q) has dimension equal to the number of integer partitions of n. If we could evaluate all functions belonging to some basis of the trace space on all elements of some basis of H_n(q), then by linearity we could evaluate em all traces on all elements of H_n(q).  Unfortunately there is no simple published formula which accomplishes this. We will consider a basis of H_n(q) which is related to structures called wiring diagrams, and a combinatorial rule for evaluating one trace basis on all elements of this wiring diagram basis. This result, the first of its kind, is joint work with Justin Lambright and Ryan Kaliszewski. 
Tuesday, March 6, 2018 - 12:00 , Location: Skiles 256 , Jeong Han Kim , Korean Institute for Advanced Study , hmkkim@gmail.com , Organizer: Prasad Tetali
  How many triangles are needed to make the new graphs not look like random graphs? I am trying to answer this question.  (The talk will be during 12:05-1:15pm; please note the room is *Skiles 256*)
Friday, March 2, 2018 - 15:00 , Location: Skiles 005 , Alexander Barvinok , University of Michigan , barvinok@umich.edu , Organizer: Prasad Tetali
This is Lecture 3 of a series of 3 lectures. See the abstract on Tuesday's ACO colloquium of this week.(Please note that this lecture will be 80 minutes' long.)
Friday, February 23, 2018 - 15:05 , Location: Skiles 005 , Robert Hough , SUNY, Stony Brook , robert.bough@stonybrook.edu , Organizer: Prasad Tetali
I will describe two new local limit theorems on the Heisenberg group, and on an arbitrary connected, simply connected nilpotent Lie group.  The limit theorems admit general driving measures and permit testing against test functions with an arbitrary translation on the left and the right. The techniques introduced include a rearrangement group action, the Gowers-Cauchy-Schwarz inequality, and a Lindeberg replacement scheme which approximates the driving measure with the corresponding heat kernel.  These results generalize earlier local limit theorems of Alexopoulos and Breuillard, answering several open questions.  The work on the Heisenberg group is joint with Persi Diaconis. 
Friday, February 16, 2018 - 15:00 , Location: Skiles 005 , Hao Huang , Emory University , hao.huang@emory.edu , Organizer: Lutz Warnke
A tight k-uniform \ell-cycle, denoted by TC_\ell^k, is a k-uniform hypergraph whose vertex set is v_0, ..., v_{\ell-1}, and the edges are all the k-tuples {v_i, v_{i+1}, \cdots, v_{i+k-1}}, with subscripts modulo \ell. Motivated by a classic result in graph theory that every n-vertex cycle-free graph has at most n-1 edges, Sos and, independently, Verstraete asked whether for every integer k, a k-uniform n-vertex hypergraph without any tight k-uniform cycles has at most \binom{n-1}{k-1} edges. In this talk I will present a construction giving negative answer to this question, and discuss some related problems. Joint work with Jie Ma.
Friday, January 26, 2018 - 15:00 , Location: Skiles 005 , Gerandy Brito , Georgia Tech , Organizer: Lutz Warnke
We study the number of random permutations needed to invariably generate the symmetric group, S_n, when the distribution of cycle counts has the strong \alpha-logarithmic property. The canonical example is the Ewens sampling formula, for which the number of k-cycles relates to a conditioned Poisson random variable with mean \alpha/k. The special case \alpha=1 corresponds to uniformly random permutations, for which it was recently shown that exactly four are needed.For strong \alpha-logarithmic measures, and almost every \alpha, we show that precisely $\lceil( 1- \alpha \log 2 )^{-1} \rceil$ permutations are needed to invariably generate S_n. A corollary is that for many other probability measures on S_n no bounded number of permutations will invariably generate S_n with positive probability. Along the way we generalize classic theorems of Erdos, Tehran, Pyber, Luczak and Bovey to permutations obtained from the Ewens sampling formula. 
Friday, December 8, 2017 - 15:00 , Location: Skiles 005 , Matthew Yancey , Inst. for Defense Analysis , Organizer: Lutz Warnke
For a fixed graph $G$, let $\mathcal{L}_G$ denote the family of Lipschitz functions $f:V(G) \rightarrow \mathbb{R}$ such that $0 = \sum_u f(u)$. The \emph{spread} of $G$ is denoted $c(G) := \frac{1}{|V(G)|} \max_{f \in \mathcal{L}_G} \sum_u f(u)^2$ and the subgaussian constant is $e^{\sigma_G^2} := \sup_{t > 0} \max_{f \in \mathcal{L}_G} \left( \frac{1}{|V(G)|} \sum_u e^{t f(u)} \right)^{2/t^2}$. Motivation of these parameters comes from their relationship with the isoperimetric number of a graph (given a number $t$, find a set $W \subset V(G)$ such that $2|W| \geq |V(G)|$ that minimizes $i(G,t) := |\{u : d(u, W) \leq t \}|$). While the connection to the isoperimetric number is interesting, the spread and subgaussian constant have not been any easier to understand. In this talk, we will present results that describe the functions $f$ achieving the optimal values. As a corollary to these results, we will resolve two conjectures (one false, one true) about these parameters. The conjectures that we resolve are the following. We denote the Cartesian product of $G$ with itself $d$ times as $G^d$. Alon, Boppana, and Spencer proved that the set $\{u: f(u) < k\}$ for extremal function $f$ for the spread of $G^d$ gives a value that is asymptotically close to the isoperimetric number when $d, t$ grow at specific rates and $k=0$; and they conjectured that the value is exactly correct for large $d$ and $k,t$ in ``appropriate ranges.'' The conjecture was proven true for hypercubes by Harper and the discrete torus of even order by Bollob\'{a}s and Leader. Bobkov, Houdr\'{e}, and Tetali constructed a function over a cycle that they conjectured to be optimal for the subgaussian constant, and it was proven correct for cycles of even length by Sammer and Tetali. This work appears in the manuscript https://arxiv.org/abs/1705.09725 .

Pages