Seminars and Colloquia by Series

Asymptotic extremal graph theory is non-trivial

Series
Graph Theory Seminar
Time
Tuesday, May 18, 2010 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 270
Speaker
Sergey Norin – Princeton University

Please Note: Please note the location: Last minute room change to Skiles 270.

Many fundamental theorems in extremal graph theory can be expressed as linear inequalities between homomorphism densities. It is known that every such inequality follows from the positive semi-definiteness of a certain infinite matrix. As an immediate consequence every algebraic inequality between the homomorphism densities follows from an infinite number of certain applications of the Cauchy-Schwarz inequality. Lovasz and, in a slightly different formulation, Razborov asked whether it is true or not that every algebraic inequality between the homomorphism densities follows from a _finite_ number of applications of the Cauchy-Schwarz inequality. In this talk, we show that the answer to this question is negative by exhibiting explicit valid inequalities that do not follow from such proofs. Further, we show that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable. Joint work with Hamed Hatami.

East Coast Computer Algebra Day 2010

Series
Other Talks
Time
Saturday, May 15, 2010 - 08:00 for 8 hours (full day)
Location
Emory University
Speaker
East Coast Computer Algebra Day 2010 – Department of Mathematics and Computer Science, Emory University

Please Note: Anton Leykin is an invited speaker presenting "Certified numerical solving of systems of polynomial equations"

East Coast Computer Algebra Day (ECCAD) is an informal one-day meeting for those active or interested in computer algebra. It provides opportunities to learn and to share new results and work in progress.  The schedule includes invited speakers, a panel discussion, and contributed posters and software demonstrations. Importantly, plenty of time is allowed for unstructured interaction among the participants.  Researchers, teachers, students, and users of computer algebra are all welcome! Visit ECCAD for more details.

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 Howard – School 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 Herbin – Ecole 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 Devanur – Microsoft 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 Tzermias – University 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 Palmer – Georgia 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 Szymanska – Adam 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 Lacey – Georgia Tech
Club Math Presents The Mathematics of Futurama, by Dr. Michael Lacey.

Pages