Seminars and Colloquia by Series

On killing the affine line

Series
Geometry Topology Seminar
Time
Monday, October 5, 2015 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Inna ZakharevichUniversity of Chicago
The Grothendieck ring of varieties is defined to be the free abelian group generated by k-varieties, modulo the relation that for any closed subvariety Y of a variety X, we impose the relation that [X] = [Y] + [X \ Y]; the ring structure is defined by [X][Y] = [X x Y]. Last December two longstanding questions about the Grothendieck ring of varieties were answered: 1. If two varieties X and Y are piecewise isomorphic then they are equal in the Grothendieck ring; does the converse hold? 2. Is the class of the affine line a zero divisor? Both questions were answered by Borisov, who constructed an element in the kernel of multiplication by the affine line; coincidentally, the proof also constructed two varieties whose classes in the Grothendieck ring are the same but which are not piecewise isomorphic. In this talk we will investigate these questions further by constructing a topological analog of the Grothendieck ring and analyzing its higher homotopy groups. Using this extra structure we will sketch a proof that Borisov's coincidence is not a coincidence at all: that any element in the annihilator of the Lefschetz motive can be represented by a difference of varieties which are equal in the Grothendieck ring but not piecewise isomorphic.

Survival of the Smartest: Sparse Recovery in Biology

Series
Applied and Computational Mathematics Seminar
Time
Monday, October 5, 2015 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Felix LiederMathematisches Institut Lehrstuhl für Mathematische Optimierung
Survival can be tough: Exposing a bacterial strain to new environments will typically lead to one of two possible outcomes. First, not surprisingly, the strain simply dies; second the strain adapts in order to survive. In this talk we are concerned with the hardness of survival, i.e. what is the most efficient (smartest) way to adapt to new environments? How many new abilities does a bacterium need in order to survive? Here we restrict our focus on two specific bacteria, namely E.coli and Buchnera. In order to answer the questions raised, we first model the underlying problem as an NP-hard decision problem. Using a re-weighted l1-regularization approach, well known from image reconstruction, we then approximate ”good” solutions. A numerical comparison between these ”good” solutions and the ”exact” solutions concludes the talk.

Extremal Cuts of Sparse Random Graphs

Series
ACO Seminar
Time
Monday, October 5, 2015 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Amir DemboStanford University
The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of M=N d/2 edges, the leading correction to M/2 (the typical cut size), is P_* sqrt(N M/2). Here P_* is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula. This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.

Morphing planar triangulations

Series
Combinatorics Seminar
Time
Friday, October 2, 2015 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Fidel Barrera CruzGeorgia Tech
A morph between two drawings of the same graph can be thought of as a continuous deformation between the two given drawings. In this talk we consider the algorithmic problem of morphing between any two planar drawings of a planar triangulation while preserving planarity during the morph. We outline two different solutions to the morphing problem. The first solution gives a strengthening of the result of Alamdari et al. where each step is a unidirectional morph. The second morphing algorithm finds a planar morph consisting of O(n²) steps between any two Schnyder drawings while remaining in an O(n)×O(n) grid, here n is the number of vertices of the graph. However, there are drawings of planar triangulations which are not Schnyder drawings, and for these drawings we show that a unidirectional morph consisting of O(n) steps that ends at a Schnyder drawing can be found. (Joint work with Penny Haxell and Anna Lubiw)

Gaussian fluctuations for linear statistics of Wigner matrices

Series
Stochastics Seminar
Time
Thursday, October 1, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Philippe SosoeHarvard University
In the 1970s, Girko made the striking observation that, after centering, traces of functions of large random matrices have approximately Gaussian distribution. This convergence is true without any further normalization provided f is smooth enough, even though the trace involves a number of terms equal to the dimension of the matrix. This is particularly interesting, because for some rougher, but still natural observables, like the number of eigenvalues in an interval, the fluctuations diverge. I will explain how such results can be obtained, focusing in particular on controlling the fluctuations when the function is not very regular.

Cycles lengths in graphs with large minimum degree

Series
Graph Theory Seminar
Time
Thursday, October 1, 2015 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jie MaUniversity of Science and Technology of China
There has been extensive research on cycle lengths in graphs with large minimum degree. In this talk, we will present several new and tight results in this area. Let G be a graph with minimum degree at least k+1. We prove that if G is bipartite, then there are k cycles in G whose lengths form an arithmetic progression with common difference two. For general graph G, we show that G contains \lfloor k/2\rfloor cycles with consecutive even lengths, and in addition, if G is 2-connected and non-bipartite, then G contains \lfloor k/2\rfloor cycles with consecutive odd lengths. Thomassen (1983) made two conjectures on cycle lengths modulo a fixed integer k: (1) every graph with minimum degree at least k+1 contains cycles of all even lengths modulo k; (2) every 2-connected non-bipartite graph with minimum degree at least $k+1$ contains cycles of all lengths modulo k. These two conjectures, if true, are best possible. Our results confirm both conjectures! when k is even. And when k is odd, we show that minimum degree at least $+4 suffices. Moreover, our results derive new upper bounds of the chromatic number in terms of the longest sequence of cycles with consecutive (even or odd) lengths. This is a joint work with Chun-Hung Liu.

Bochner-Riesz multipliers associated to convex planar domains with rough boundary

Series
Analysis Seminar
Time
Wednesday, September 30, 2015 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Laura CladekUniversity of Wisconsin, Madison
We consider generalized Bochner-Riesz multipliers $(1-\rho(\xi))_+^{\lambda}$ where $\rho(\xi)$ is the Minkowski functional of a convex domain in $\mathbb{R}^2$, with emphasis on domains for which the usual Carleson-Sj\"{o}lin $L^p$ bounds can be improved. We produce convex domains for which previous results due to Seeger and Ziesler are not sharp. For integers $m\ge 2$, we find domains such that $(1-\rho(\xi))_+^{\lambda}\in M^p(\mathbb{R}^2)$ for all $\lambda>0$ in the range $\frac{m}{m-1}\le p\le 2$, but for which $\inf\{\lambda:\,(1-\rho)_+^{\lambda}\in M_p\}>0$ when $p<\frac{m}{m-1}$. We identify two key properties of convex domains that lead to improved $L^p$ bounds for the associated Bochner-Riesz operators. First, we introduce the notion of the ``additive energy" of the boundary of a convex domain. Second, we associate a set of directions to a convex domain and define a sequence of Nikodym-type maximal operators corresponding to this set of directions. We show that domains that have low higher order energy, as well as those which have asymptotically good $L^p$ bounds for the corresponding sequence of Nikodym-type maximal operators, have improved $L^p$ bounds for the associated Bochner-Riesz operators over those proved by Seeger and Ziesler.

Pages