Darren Rhea's HomepageJust another WordPress siteSkip to contentHomeAbout MeChris Hillar, Lionel Levine, FPSAC
Posted on August 20, 2010 by dlr2986
We presented our paper at FPSAC and had a great time.  I met many interesting people, for instance the unreasonably tall 6′ 9″  Benjamin Matschke of TU Berlin, who was nice enough to prove for me that Borsuk-Ulam implies the Ham Sandwich Theorem.  Benjamin is studying topological methods in combinatorics.  There is something called the Kneser graph: the vertices are all subsets of 1 thru n of size k, and two vertices are connected by an edge if they do not intersect.  Lovasz proved in 1978 that the chromatic number of the Kneser graph is n-2k+2 so long as n>=2k-1, using Borsuk-Ulam.  Talk about weird.  see the book  Using the Borsuk-Ulam Theorem.
I also met John Novak, who will be at MSRI this fall for random matrices.  John informed me of this awesome free book,  An Introduction to Random Matrices, by Greg Anderson, Alice Guionnet and O. Zeitouni.    We were supposed to give John a ride to Berkeley so that he could meet his landlord, and of course Lionel and I wanted to get him there on time, but Chris wanted to dilly-dally, so we wound up being late and John’s landlord was super-pissed.  When she (the landlord) suggested she wanted to whip John with a whip (seriously!), I made Chris take the blame and began kicking him for her.
Posted in Uncategorized
|
1 Comment
FPSAC’10 — Formal Power Series and Algebraic Combinatorics
Posted on July 30, 2010 by dlr2986
I am going to fly to San Francisco on Sunday for FPSAC’10 — Formal Power Series and Algebraic Combinatorics.  We (Chris Hillar, Lionel Levine, Darren Rhea) are presenting a poster on a certain type of multiplicative group G.  At its most basic level, G has unique nth root extraction, so for any B you can solve X^n =B for X uniquely, yet there is are A and B in G such that the equation XAX^3AX=B has no solution X.  The group’s construction is kind of complicated, and we would love a better, more natural example of a unique root extraction group that does not have XAX^3AX=B solvable, but we haven’t found one yet.
Posted in Uncategorized
|
Leave a comment
Garrett Birkhoff 1946, the Doubly Stochastic Matrices are the Convex Hull of the Permutation Matrices, and His Father’s Birkhoff Ergodic Theorem
Posted on July 29, 2010 by dlr2986
I came upon this interesting 1946 theorem of Garrett Birkhoff while reading Leon Mirsky’s proof of von Neumann’s trace inequality:  the set of all doubly stochastic matrices is the convex hull of the permutation matrices.   You can use a greedy algorithm of sorts: to write a given doubly stochastic matrix as a convex combination of permutation matrices, just keep subtracting positive multiples of permutation matrices in order to zero out an entry while preserving the nonnegativity of all entries until you can’t anymore.  Of course these su