UIUC Dept. of Mathematics Seminar Calendar

     January 2006          February 2006            March 2006     
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
  1  2  3  4  5  6  7             1  2  3  4             1  2  3  4
  8  9 10 11 12 13 14    5  6  7  8  9 10 11    5  6  7  8  9 10 11
 15 16 17 18 19 20 21   12 13 14 15 16 17 18   12 13 14 15 16 17 18
 22 23 24 25 26 27 28   19 20 21 22 23 24 25   19 20 21 22 23 24 25
 29 30 31               26 27 28               26 27 28 29 30 31

Monday, February 13, 2006

1:00 pm in 341 Altgeld Hall,Monday, February 13, 2006

Mathematics Colloquium - Special Lecture 2005-06

Isomorphisms and Morita equivalencies of Poisson manifolds

Olga Radko (UCLA)

Abstract: According to the splitting theorem of A. Weinstein, a Poisson structure induces a (singular) foliation on the underlying manifold, making the global classification of Poisson structures extremely difficult. Locally, in dimension 2, there is a hierarchy of Poisson structures related to Arnold's classification of singularities. We present a complete global classification of several types of Poisson structures corresponding to the first few elements in the local hierarchy. In analogy with algebras, P. Xu called two Poisson manifolds Morita equivalent if there is a symplectic manifold playing the role of an invertible bimodule. This also associates to every Poisson manifold an invariant, called its Picard group. We show that for a certain type of structures, this group is isomorphic to a particular mapping class group of the underlying manifold. Host: Ely Kerman

Submitted by seminar

3:00 pm in 3405 Siebel Center,Monday, February 13, 2006

Applied/Interdisciplinary Mathematics Seminar

Algorithms for equitable coloring and packing of graphs

A. Kostochka (UIUC Math)

Abstract: An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. A $d$-degenerate graph is a graph $G$ in which every induced subgraph has a vertex with degree at most $d$. It is well known that trees are 1-degenerate, outerplanar graphs are 2-degenerate, and planar graphs are 5-degenerate. Our first result shows that every $d$-degenerate graph can be equitably partitioned into three $(d-1)$-degenerate graphs. Then we show that every $n$-vertex $d$-degenerate graph $G$ with $\Delta (G)\leq n/15$ can be equitably $k$-colored for any $k \ge 16d$. The proof of this bound is constructive and implies an $O(d)$-factor approximation algorithm for equitable coloring with fewest colors any $n$-vertex $d$-degenerate graph $G$ with $\Delta (G)\leq n/15$. We then extend this to an $O(d)$-factor approximation algorithm for equitable coloring of any $d$-degenerate graph. Among the implications of this result is the first $O(1)$-factor approximation algorithm for equitable coloring planar graphs with minimum number of colors. These results have applications in improved Chernoff-Hoeffding bounds for sums of random variables with limited dependence and to partitioning problems such as MAX $p$-SECTION.

Submitted by ghrist

4:00 pm in 245 Altgeld Hall,Monday, February 13, 2006

Mathematics Colloquium - Special Lecture 2005-06

Free Entropy Dimension for Groups

Dimitri Shlyakhtenko (UCLA)

Abstract: Free entropy dimension is a quantity defined by Voiculescu in his free probability theory, and is a function of the "non-commutative law" of an n-tuple of random variables. Its definition is analogous to a certain quantity in classical probability theory (computed using Gaussian convolution and entropy) measuring a kind of Minkowski dimension of the support of a measure representing a classical law. In the non-commutative world, many objects (such as a choice of generators of a group) determine a non-commutative law. Jointly with I. Mineyev (and building up on some past work and some joint work with A. Connes) we were able to compute this quantity for sets of generators of discrete groups; the result, surprisingly, involves the L² cohomology of the group. In this talk, I hope to give you an exposition of the interplay between these various subjects.