Seminars and Colloquia by Series

Familes of Maximal Chains

Series
Combinatorics Seminar
Time
Friday, May 7, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
David HowardSchool of Math, Georgia Tech
In the paper "On the Size of Maximal Chains and the Number of Pariwise Disjoint Maximal Antichains" Duffus and Sands proved the following:If P is a poset whose maximal chain lengths lie in the interval [n,n+(n-2)/(k-2)] for some n>=k>=3 then there exist k disjoint maximal antichains in P. Furthermore this interval is tight. At the end of the paper they conjecture whether the dual statement is true (swap the words chain and antichain in the theorem). In this talk I will prove the dual and if time allows I will show a stronger version of both theorems.

The set-indexed Lévy processes

Series
Stochastics Seminar
Time
Thursday, May 6, 2010 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Erick HerbinEcole Centrale Paris
The aim of this joint work with Ely Merzbach is to present a satisfactory definition of the class of set-indexedL\'evy processes including the set-indexed Brownian motion, the spatial Poisson process, spatial compound Poisson processesand some other stable processes and to study their properties. More precisely, the L\'evy processes are indexed by a quite general class $\mathcal{A}$ of closed subsets in a measure space $(\mathcal{T} ,m)$. In the specific case where $\mathcal{T}$ is the $d$-dimensional rectangle$[0 ,1]^d$ and $m$ is the Lebesgue measure, a special kind of this definition was given and studied by Bass and Pyke and by Adler and Feigin. However, in our framework the parameter set is more general and, it will be shown that no group structure is needed in order to define the increment stationarity property for L\'evy processes.

New Convex Programs and Distributed Algorithms for Fisher Markets

Series
ACO Seminar
Time
Tuesday, May 4, 2010 - 16:00 for 1 hour (actually 50 minutes)
Location
Klaus 1116W
Speaker
Nikhil DevanurMicrosoft Research

Please Note: Hosted by Vijay Vazirani

I will talk about new results on convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. In particular: (i) show a new convex program for the linear utilities case of Fisher markets. This program easily extends to the case of spending constraint utilities as well, thus resolving an open question raised by Vazirani; (ii) show that the gradient descent algorithm with respect to a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate); (iii) show that the Proportional Response dynamics recently introduced by Zhang is equivalent to a gradient descent algorithm for solving the new convex program. This insight also gives us better convergence rates, and helps us generalize it to spending constraint utilities.

Factorization of Cauchy-Liouville-Mirimanoff polynomials

Series
Algebra Seminar
Time
Monday, May 3, 2010 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 171
Speaker
Pavlos TzermiasUniversity of Tennessee Knoxville
The polynomials mentioned in the title were introduced by Cauchy and Liouville in 1839 in connection with early attempts at a proof of Fermat's Last Theorem. They were subsequently studied by Mirimanoff who in 1903 conjectured their irreducibility over the rationals. During the past fifteen years it has become clear that Mirimanoff's conjecture is closely related to properties of certain special functions and to some deep results in diophantine approximation. Apparently, there is also a striking connection to hierarchies of certain evolution equations (which this speaker is not qualified to address). We will present and discuss a number of recent results on this problem.

Noncommutative Geometry and Compact Metric Spaces

Series
Dissertation Defense
Time
Monday, May 3, 2010 - 11:00 for 2 hours
Location
Skiles 255
Speaker
Ian PalmerGeorgia Tech
A construction is given for which the Hausdorff measure and dimension of an arbitrary abstract compact metric space (X, d) can be encoded in a spectral triple. By introducing the concept of resolving sequence of open covers, conditions are given under which the topology, metric, and Hausdorff measure can be recovered from a spectral triple dependent on such a sequence. The construction holds for arbitrary compact metric spaces, generalizing previous results for fractals, as well as the original setting of manifolds, and also holds when Hausdorff and box dimensions differ—in particular, it does not depend on any self-similarity or regularity conditions on the space or an embedding in an ambient space. The only restriction on the space is that it have positive s-dimensional Hausdorff measure, where s is the Hausdorff dimension of the space, assumed to be finite.

The Complexity of Vertex Coloring Problems in Dense Uniform Hypergraphs

Series
Combinatorics Seminar
Time
Friday, April 30, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Edyta SzymanskaAdam Mickiewicz University
In the talk we will consider the problem of deciding whether agiven $r$-uniform hypergraph $H$ with minimum vertex degree atleast $c|V(H)|$, has a vertex 2-coloring. This problem has beenknown also as the Property B of a hypergraph. Motivated by an oldresult of Edwards for graphs, we summarize what can be deducedfrom his method about the complexity of the problem for densehypergraphs. We obtain the optimal dichotomy results for2-colorings of $r$-uniform hypergraphs when $r=3,4,$ and 5. During the talk we will present the NP-completeness results followed bypolynomial time algorithms for the problems above the thresholdvalue. The coloring algorithms rely on the known Tur\'{a}n numbersfor graphs and hypergraphs and the hypergraph removal lemma.

The Mathematics of Futurama

Series
Other Talks
Time
Thursday, April 29, 2010 - 19:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Michael LaceyGeorgia Tech
Club Math Presents The Mathematics of Futurama, by Dr. Michael Lacey.

Matrix cut-norms and their relations to graphs

Series
Graph Theory Seminar
Time
Thursday, April 29, 2010 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Vladimir NikiforovUniversity of Memphis
In 1997 Kannan and Frieze defined the \emph{cut-norm} $\left\Vert A\right\Vert_{\square}$ of a $p\times q$ matrix $A=\left[ a_{ij}\right] $ as%\[\left\Vert A\right\Vert _{\square}=\frac{1}{pq}\max\left\{ \left\vert\sum_{i\in X}\sum_{j\in Y}a_{ij}\right\vert :X\subset\left[ p\right],Y\subset\left[ q\right] ,\text{ }X,Y\neq\varnothing\right\} .\]More recently, Lov\'{a}sz and his collaborators used the norm $\left\VertA\right\Vert _{\square}$ to define a useful measure of similarity between anytwo graphs, which they called \emph{cut-distance. }It turns out that the cut-distance can be extended to arbitrary complexmatrices, even non-square ones. This talk will introduce the basics of thecut-norm and \ cut-distance for arbitrary matrices, and present relationsbetween these functions and some fundamental matricial norms, like theoperator norm. In particular, these relations give a solution to a problem of Lov\'{a}sz.Similar questions are discussed about the related norm\[\left\Vert A\right\Vert _{\boxdot}=\max\left\{ \frac{1}{\sqrt{\left\vertX\right\vert \left\vert Y\right\vert }}\left\vert \sum_{i\in X}\sum_{j\inY}a_{ij}\right\vert :X\subset\left[ p\right] ,Y\subset\left[ q\right],\text{ }X,Y\neq\varnothing\right\} .\]which plays a central role in the \textquotedblleft expander mixinglemma\textquotedblright.

On complex orthogonal polynomials related with Gaussian quadrature of oscillatory integrals

Series
Analysis Seminar
Time
Wednesday, April 28, 2010 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Alfredo DeañoUniversidad Carlos III de Madrid (Spain)
We present results on the asymptotic behavior of a family of polynomials which are orthogonal with respect to an exponential weight on certain contours of the complex plane. Our motivation comes from the fact that the zeros of these polynomials are the nodes for complex Gaussian quadrature of an oscillatory integral defined on the real axis and having a high order stationary point. The limit distribution of these zeros is also analyzed, and we show that they accumulate along a contour in the complex plane that has the S-property in the presence of an external field. Additionally, the strong asymptotics of the orthogonal polynomials is obtained by applying the nonlinear Deift--Zhou steepest descent method to the corresponding Riemann--Hilbert problem. This is joint work with D. Huybrechs and A. Kuijlaars, Katholieke Universiteit Leuven (Belgium).

Pages