Rutgers University (New Brunswick) Piscataway New Jersey 08854-8019 Department of Mathematics-Hill Center e-mail: zeilberg@math.rutgers.edu

(732) 445–1326 (voice) (732) 445–5530 (Fax)

Oct. 17, 2005

NSF Postdoctoral Research Fellowship

National Science Foundation

Arlington, VA

Dear Committee,

This is a letter of recommendation on behalf of my doctoral student Vince VATTER who is applying for an NSF Postdoctoral Research Fellowship (MSPRF).

I already knew of Vince’s work before he came to Rutgers. My good friend Bruce Sagan told me to watch out for his brilliant student, who did undergraduate research under him and already had one accepted article and two in preparation, a record that would most likely suffice for a Ph.D.! I had a chance to review that first paper in my capacity as Editor of Adv. Appl. Math. This paper is a really significant contribution to permutation enumeration. Their work is now covered in detail in Miklós Bóna’s recent book “Combinatorics of Permutations,” the definitive monograph in the field.

Vince is currently a fourth-year Ph.D. candidate, and although he has yet to complete all the formalities to graduate (his defense is scheduled for November, 2005), he has begun a one-year postdoc at the University of St. Andrews, where he continues to do first-class research. I can safely say that he is the best Ph.D. student that I have ever guided (so far I have graduated twelve students, and have five current students). I have also interacted with many graduate students in my many courses, and would definitely rank him in the top 5 percent of all students I have known, if not higher.

Vince is almost unique in combining deep theoretical insight with uncanny computeralgebra wizardry. That will make him ideally suited to pursue his proposed research with Richard Stanley.

Vince’s research output is truly amazing, in both quantity and quality. So far he has ten finished papers (seven published or accepted, and three under consideration).

Vince has shown considerable breadth in his research already. He has written on graph theory (“Maximal independent sets in graphs with at most r cycles,” with Goh Chee Ying, Koh, Khee Meng, and Bruce Sagan, and “Maximal and maximum independent sets in graphs with at most r cycles, with Bruce Sagan, both accepted for J. Graph Theory), on packing densities of permutations (“Pattern frequency sequences an internal zeros,” with Miklós Bóna and Bruce Sagan and “Bounding quantities related to the packing density of 1(ℓ + 1)ℓ ⋯ 2 with Martin Hildebrand and Bruce Sagan, both published in Adv. Appl. Math.), on the partial well-order theory of the permutation containment order (“Profile classes and partial well-order for permutations,” with Maximillian Murphy, published in the Elec. J. Comb.), and on Möbius functions (“The Möbius function of the composition poset,” with Bruce Sagan and still under consideration).

But Vince’s work that is closest to my heart is his work on automated combinatorics. Vince began with a problem that no one thought could have a nice answer. He took a human approach to the counting of restricted permutations (known as generating trees) and asked when they need only finitely many labels. Amazingly, he was able to prove necessary and sufficient conditions for when this happens, and, more amazingly, he developed a Maple package, FINLABEL, which can find – in a completely automatic and yet rigorous way – generating functions for such classes. His FINLABEL package, which accompanies his beautiful paper “Finitely labeled generating trees for restricted permutations,” (J. Symb. Comp., accepted), can reprove hundreds of results (and several entire papers) that had previously been obtained my hand. This work is truly a fundamental breakthrough in the field of restricted permutations, and has already inspired follow-up work by others (see “The insertion encoding of permutations,” by Albert, Linton, and Ruškuc, Elec. J. Comb., 12(1), R47).

Vince then took up an approach of my own. I had developed the notion of ‘enumeration schemes’ to count more families of restricted permutations, but was disappointed that my technique had a success rate of only about 10%. By making highly ingenious conceptual improvements, Vince extended my notion of enumeration scheme to include many more cases. His Maple package WILFPLUS indeed is a major enhancement of my previous package WILF, and his paper “Enumeration schemes for restricted permutations” (under consideration) is another major theoretical advance in the field.

Of course, these techniques for automated combinatorics apply to more than simply restricted permutations. Recently Vince, Shalosh B. Ekhad, and I used similar ideas to settle an irresistible conjecture of Nick Loehr and Greg Warrington that a certain easy-to-describe set of lattice paths are enumerated by 10^{n} in our paper “A proof of the Loehr-Warrington amazing TEN to the power n conjecture” (under consideration). Our resulting Maple package, TEN, was able to prove their conjecture in 30 seconds. Since then, Loehr, Warrington and Bruce Sagan found a computer-free proof for a generalization, while Jonas Sjöstrand gave a beautiful bijective proof for an even broader conjecture. But the main point of our paper was to develop and illustrate a methodology of completely computergenerated research, which should extend to many other cases where the answers are not so beautiful, and hence where it is very unlikely that there exist nice human proofs.

On top of his fantastic research, Vince is also a very gifted teacher and speaker. Quite a few times he has presented excellent seminar talks.

Vince is a warm and enthusiastic person, as well as patient and compassionate, all qualities that would make him very compatible with Richard Stanley, the sponsoring scientist.

To sum up, Vince is an extremely promising young mathematician and a gifted teacher. I recommend him most highly.

If you have any further questions, I will be glad to answer them. My phone numbers are (609)921-7873 (home), and (732)445-1326 (office).

Sincerely,

Doron Zeilberger, Ph.D.

Board of Governors Prof. of Math