 |
|
| Monday 10 |
3:10-4 pm, room 1432. Graph Theory and Combinatorics Seminar. Matjaz Konvalinka, Vanderbilt University. Geometry and complexity of O'Hara's algorithm. In the early 1980s, Remmel and Gordon found (rather involved)
bijective proofs of basic partition identities due to Andrews. The latter
are direct extensions of Euler's distinct/odd theorem and have a similarly
straightforward analytic proof. Some years later, O'Hara made a surprising
discovery that Remmel's and Gordon's bijections can be streamlined to give
the same bijective map with a simple construction. In fact, O'Hara proved
that the resulting bijection is a direct generalization of Glaisher's
classical bijection proving Euler's theorem. Moreover, in her thesis,
O'Hara showed that her bijection is computationally efficient in certain
special cases. In this talk (joint work with Igor Pak), I will present results of
both positive and negative type. First, I will analyze the complexity of
O'Hara's bijection. We present an exact formula for the number of steps of
the algorithm in certain cases. From here it follows that O'Hara's
bijection is computationally efficient in many special cases. On the other
hand, we will see that the number of steps can be (mildly) exponential in
the worst case. Second, we show that O'Hara's bijection has a rich underlying
geometry; we can view it as a map between integer points in polytopes that
preserves certain linear functionals. We present a generalization of
Andrews's result and of O'Hara's bijection in this geometric setting. Finally, by combining the geometric and complexity ideas we show that
in the finite dimensional case the map defined by O'Hara's bijection is a
solution of an integer linear programming problem. This implies that in
this case, the map defined by the bijection can be computed in polynomial
time, i.e. much more efficiently than by O'Hara's bijection.
4:10-5 pm, room 1432. NCGOA Research Training Group Seminar. Qayum Khan, Vanderbilt University. The fundamental theorem of Bass--Heller--Swan, II. In Part I, we discussed the statement and outline of proof of the fundamental theorem, as well as stated three isomorphisms in lemmas. The first isomorphism used the Hilbert syzygy theorem. In Part II, we shall review the statements and prove the other two lemmas, which use the Grothendieck devissage theorem and Higman's linearization trick, respectively. Afterwards, we shall show why the localization sequence of the polynomial ring R[x] splits. It turns out that Nil-groups appear internally in these three isomorphisms as a technique of proof. Time permitting, we may discuss why these Bass Nil-groups vanish for regular Noetherian rings. |
| Tuesday 11 |
3:20 pm, room 1425. Graduate Student Tea.
4:10-5 pm, room 1432. Noncommutative Geometry Seminar. Yves de Cornulier, Institut des Rennes, France. On asymptotic cones of polycyclic groups. I'll give an example of a polycyclic group whose asymptotic cones are abelian and non-trivial (joint with R. Tessera). 4:10-5:00 pm, room 1312. Computational Analysis Seminar. Simon Foucart, Vanderbilt University. A Survey on the Mathematics of Compressed Sensing. This talk will give an overview of some chosen topics in the theory of Compressed Sensing. Mathematically speaking, one aims at finding sparsest solutions of severely underdetermined linear systems of equations via robust and efficient algorithms. I shall especially discuss the advantages and drawbacks of algorithms based on $\ell_q$-minimization for $0 < q < 1$ compared to the classical $\ell_1$-minimization. This will be based on results --- both of positive and negative nature --- recently obtained by Chartrand et al., by Gribonval et al., and by Lai and myself. 7-8 pm, room 1206. Undergraduate Seminar in Mathematics. Dan Ramras, Vanderbilt University. A Tour through Topology. Topology studies intrinsic properties of geometric objects: those features that remain unchanged if the object is deformed continuously. A basic goal of topology, and topologists, is to distinguish geometric objects. Sometimes this is easy. We all know the difference between a donut and a sphere; one has a hole, and the other doesn't! But to distinguish more complicated, higher dimensional objects, subtler tools are needed. We'll start off by discussing Euler's theorem, which gives a topological invariant that can be computed for geometric objects built out of simple building blocks. Euler's theorem has some nice applications, like Pic's formula for the area of certain regions in the plane. We'll move on to discuss the "fundamental group," which describes loops inside a geometric object. This notion lead Poincare to make his famous conjecture about three-dimensional geometry, solved a hundred years later (in 2002) by Grigori Perelman. Free pizza! |
| Wednesday 12 | 4:10 pm, room 1310. Topology & Group Theory Seminar. Emmanuel Breuillard, Paris XI (Orsay). A strong Tits alternative and arithmetic heights on character varieties. We prove an effective uniform version of the Tits alternative on an arbitrary field and derive several new results on the structure of linear groups, mainly about their growth and number of relations. The main statement can be reformulated in terms of first order logic as the equality between seemingly unrelated algebraic varieties. This allows to reduce mod p and get new applications such as bounds on the girth of Cayley graphs of subgroups of GL(n,F_q). Proofs rely on the notion of "arithmetic spectral radius" of a finite family of matrices and key ingredients are some results from Diophantine Geometry such as theorems of Bilu and Zhang on the set of points of small height on algebraic varieties. We will also mention the Lehmer conjecture, in connection with the solvable case, which turns out to be surprisingly harder. |
| Thursday 13 | |
| Friday 14 |