Seminars and Colloquia by Series

Geometric Discrepancy Via the Entropy Method

Series
Job Candidate Talk
Time
Tuesday, December 3, 2013 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Esther Ezra – Courant Institute, NYU
Discrepancy theory, also referred to as the theory of irregularities of distribution, has been developed into a diverse and fascinating field, with numerous closely related areas, including, numerical integration, Ramsey theory, graph theory, geometry, and theoretical computer science, to name a few. Informally, given a set system S defined over an n-item set X, the combinatorial discrepancy is the minimum, over all two-colorings of X, of the largest deviation from an even split, over all sets in S. Since the celebrated ``six standard deviations suffice'' paper of Spencer in 1985, several long standing open problems in the theory of combinatorial discrepancy have been resolved, including tight discrepancy bounds for halfspaces in d-dimensions [Matousek 1995] and arithmetic progressions [Matousek and Spencer 1996]. In this talk, I will present new discrepancy bounds for set systems of bounded ``primal shatter dimension'', with the property that these bounds are sensitive to the actual set sizes. These bounds are nearly-optimal. Such set systems are abstract, but they can be realized by simply-shaped regions, as halfspaces, balls, and octants in d-dimensions, to name a few. Our analysis exploits the so-called "entropy method" and the technique of "partial coloring", combined with the existence of small "packings".

The skeleton of the Jacobian and the Jacobian of the skeleton

Series
Algebra Seminar
Time
Monday, December 2, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Joseph Rabinoff – Georgia Tech –
Let X be an algebraic curve over a non-archimedean field K. If the genus of X is at least 2 then X has a minimal skeleton S(X), which is a metric graph of genus <= g. A metric graph has a Jacobian J(S(X)), which is a principally polarized real torus whose dimension is the genus of S(X). The Jacobian J(X) also has a skeleton S(J(X)), defined in terms of the non-Archimedean uniformization theory of J(X), and which is again a principally polarized real torus with the same dimension as J(S(X)). I'll explain why S(J(X)) and J(S(X)) are canonically isomorphic, and I'll indicate what this isomorphism has to do with several classical theorems of Raynaud in arithmetic geometry.

Total diameter and area of closed submanifolds

Series
Geometry Topology Seminar
Time
Monday, December 2, 2013 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Mohammad Ghomi – Georgia Tech –
The total diameter of a closed planar curve C is the integral of its antipodal chord lengths. We show that this quantity is bounded below by twice the area of C. Furthermore, when C is convex or centrally symmetric, the lower bound is twice as large. Both inequalities are sharp and the equality holds in the convex case only when C is a circle. We also generalize these results to m dimensional submanifolds of R^n, where the "area" will be defined in terms of the mod 2 winding numbers of the submanifold about the n-m-1 dimensional affine subspaces of R^n.

Asymptotics of the extremal exceedance set statistic

Series
Combinatorics Seminar
Time
Wednesday, November 27, 2013 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Erik Lundberg – Purdue University
The number of permutations with specified descent set is maximized on the (classical) alternating permutations, which are counted by the Euler numbers. Asymptotics for the Euler numbers are well-studied. A counterpart of the descent statistic is the exceedance set statistic which is known to be maximized on a single run of consecutive exceedances. An exact enumeration is known, but the asymptotics have not been studied. We provide asymptotics using multivariate analytic combinatorics (providing a uniformity that goes beyond the range of a basic central limit theorem). This answers a question of E. Clark and R. Ehrenborg. As further applications we also discuss generalized pattern avoidance, and the number of orbit types (n-cycles) that admit a stretching pair (a certificate for "turbulence" in the context of combinatorial dynamics). This includes joint work with R. Ferraz de Andrade and B. Nagle and J. N. Cooper.

Recent advances in First Passage Percolation

Series
Job Candidate Talk
Time
Tuesday, November 26, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Skyles 005
Speaker
Antonio Auffinger – University of Chicago
First-passage percolation is a model of a random metric on a infinite network. It deals with a collection of points which can be reached within a given time from a fixed starting point, when the network of roads is given, but the passage times of the road are random. It was introduced back in the 60's but most of its fundamental questions are still open. In this talk, we will overview some recent advances in this model focusing on the existence, fluctuation and geometry of its geodesics. Based on joint works with M. Damron and J. Hanson.

Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probability

Series
ACO Seminar
Time
Tuesday, November 26, 2013 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Christian Borgs – Microsoft Research (New England), Cambridge, MA –
Many real-world graphs are large and growing. This naturally raises the question of a suitable concept of graph convergence. For graphs with average degree proportional to the number of vertices (dense graphs), this question is by now quite well-studied. But real world graphs tend to be sparse, in the sense that the average or even the maximal degree is bounded by some reasonably small constant. In this talk, I study several notions of convergence for graphs of bounded degree and show that, in contrast to dense graphs, where various a priori different notions of convergence are equivalent, the corresponding notions are not equivalent for sparse graphs. I then describe a notion of convergence formulated in terms of a large deviation principle which implies all previous notions of convergence.

Polygonal billiards, translations flows, and deforming geometries

Series
CDSNS Colloquium
Time
Monday, November 25, 2013 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 05
Speaker
Rodrigo Trevino – Cornell Univ./Tel Aviv Univ.
The three objects in the title come together in the study of ergodic properties of geodesic flows on flat surfaces. I will go over how these three things are intimately related, state some classical results about the unique ergodicity of translation flows and present new results which generalize much of the classical theory and also apply to non-compact (infinite genus) surfaces.

Two ways of degenerating the Jacobian are the same

Series
Algebra Seminar
Time
Monday, November 25, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jesse Kass – University of South Carolina –
The Jacobian variety of a smooth complex curve is a complex torus that admits two different algebraic descriptions. The Jacobian can be described as the Picard variety, which is the moduli space of line bundles, or it can be described as the Albanese variey, which is the universal abelian variety that contains the curve. I will talk about how to extend a family of Jacobians varieties by adding degenerate fibers. Corresponding to the two different descriptions of the Jacobian are two different extensions of the Jacobian: the Neron model and the relative moduli space of stable sheaves. I will explain what these two extensions are and then prove that they are equivalent. This equivalence has surprising consequences for both the Neron model and the moduli space of stable sheaves.

Vassiliev Invariants of Virtual Legendrian Knots

Series
Geometry Topology Seminar
Time
Monday, November 25, 2013 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Patricia Cahn – University of Pennsylvania
We introduce a theory of virtual Legendrian knots. A virtual Legendrian knot is a cooriented wavefront on an oriented surface up to Legendrian isotopy of its lift to the unit cotangent bundle and stabilization and destablization of the surface away from the wavefront. We show that the groups of Vassiliev invariants of virtual Legendrian knots and of virtual framed knots are isomorphic. In particular, Vassiliev invariants cannot be used to distinguish virtual Legendrian knots that are isotopic as virtual framed knots and have equal virtual Maslov numbers. This is joint work with Asa Levi.

Smoothed analysis on connected graphs

Series
Combinatorics Seminar
Time
Friday, November 22, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Daniel Reichman – Weizmann Institute
The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties. In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph G on n vertices can be a very bad expander, can have very large diameter, very high mixing time, and possibly has no long paths. The situation changes dramatically when \eps n random edges are added on top of G, the so obtained graph G* has with high probability the following properties: - its edge expansion is at least c/log n; - its diameter is O(log n); - its vertex expansion is at least c/log n; - it has a linearly long path; - its mixing time is O(log^2n) All of the above estimates are asymptotically tight. Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).

Pages