Nan Li

Office: 2-333

Email: nan AT math.mit.edu

I am a fifth-year PhD student in the mathematics department at MIT under the supervision of Richard Stanley. My research interest is algebraic combinatorics and discrete geometry.

Papers and preprints

1. Flashcard games, with Joel Brewster Lewis, arXiv:1210.2419.
We study a certain family of discrete dynamical processes introduced by Novikoff, Kleinberg and Strogatz that we call flashcard games. We prove a number of results on the evolution of these games, an in particular we settle a conjecture of NKS on the frequency with which a given card appears. We introduce a number of generalizations and variations that we believe are of interest, and provide a large number of open questions and problems.
pdf
2. Unimodular equivalence of order and chain polytopes, with Takayuki Hibi, arXiv:1208.4029.
The problem when the order polytope and the chain polytope of a finite partially ordered set are unimodularly equivalent will be solved.
pdf
3. An Eulerian permutation statistic and generalizations, with Travis Hance, arXiv:1208.3063.
Recently, Li studied an Eulerian statistic (called cover) in the context of convex polytopes, and proved an equal joint distribution of (cover; des) with (des; exc). In this paper, we present several direct bijective proofs that cover is Eulerian, and examine its generalizations and their Mahonian partners. We also present a quasi-symmetric function proof (suggested by Michelle Wachs) of the above equal joint distribution.
pdf
4. Chain polytopes and algebras with straightening laws, with Takayuki Hibi, arXiv:1207.2538.
We show that the toric ring of the chain polytope of a finite partially ordered set is an algebra with straightening laws on a finite distributive lattice. Thus in particular every chain polytope possesses a regular unimodular triangulation arising from a flag complex. Moreover, the problem when the order polytope and the chain polytope of a finite partially ordered set are combinatorially (or unimodularly) equivalent will be studied.
pdf
5. A canonical expansion of the product of two Stanley symmetric functions, DMTCS proc. FPSAC 2012, Nagoya, Japan, arXiv:1208.2859.
We study the problem of expanding the product of two Stanley symmetric functions F_w F_u into Stanley symmetric functions in some natural way. Our approach is to consider a Stanley symmetric function as a stabilized Schubert polynomial, and study the behavior of the expansion of $\s_{1^n\times w}\cdot\s_{1^n\times u}$ into Schubert polynomials, as n increases. We prove that this expansion stabilizes and thus we get a natural expansion for the product of two Stanley symmetric functions. In the case when one permutation is Grassmannian, we have a better understanding of this stability.
pdf, Extended Abstract
6. Separating hyperplanes of edge polytopes, with Takayuki Hibi and Yan X Zhang, arXiv:1112.5047, Journal of Combinatorial Theory, Series A, 120 (2013), 218-231.
Let G be a finite connected simple graph with d vertices and let P_G in d dimensional space be the edge polytope of G. We call P_G decomposable if P_G decomposes into integral polytopes P_G+ and P_G- via a hyperplane, and we give an algorithm which determines the decomposability of an edge polytope. We prove that when P_G is decomposable, P_G is normal if and only if both P_G+ and P_G- are normal. We also study toric ideals of P_G, P_G+ and P_G-.
pdf
7. Ehrhart $h^*$-vectors of hypersimplices, arXiv:1104.5292, to appear in Discrete and Computational Geometry.
We prove a conjecture by Stanley which says that the coefficient of t^s in the h-polynomial is the number of permutations with n-1 letters, k-1 excedances and s descents. We have two proofs: first by a generating function method and second by a shellable triangulation.
pdf, Slides
8. External zonotopal algebra, with Amos Ron, arXiv:1104.2072.
We provide a general, unified, framework for external zonotopal algebra. The approach is critically based on employing simultaneously the two dual algebraic constructs and invokes the underlying matroidal and geometric structures in an essential way. This general theory makes zonotopal algebra an applicable tool for a larger class of polytopes.
pdf, Slides.
9. Hermite forms with a given δ-vector, with Takayuki Hibi, Akihiro Higashitani, Journal of Combinatorial Theory, Series A. 119 (2012) 1158-1173.
By means of Hermite normal forms of square matrices, we study the problem of classifying the possible integral simplices with a given δ-vector with volume no larger than 4. In consequence, following the previous work of characterizing the δ-vectors with volume less than 4, we classify the possible δ-vectors with volume 4, and show that each possible δ-vectors can be obtained by simplices.
pdf
10. Generalized Ehrhart polynomial, with Sheng Chen and Steven V Sam, Trans. Amer. Math. Soc. 364 (2012), 551-569.
Let P be a polytope with rational vertices. A classical theorem of Ehrhart states that the number of lattice points in the dilations P(n) = nP is a quasi-polynomial in n. We generalize this theorem by allowing the vertices of P(n) to be arbitrary rational functions in n. In this case we prove that the number of lattice points in P(n) is a quasi-polynomial for n sufficiently large. Our work was motivated by a conjecture of Ehrhart on the number of solutions to parametrized linear Diophantine equations whose coefficients are polynomials in n, and we explain how these two problems are related.
pdf, Slides, Extended Abstract
11. On Popoviciu type formulas for generalized restricted partition function, with Sheng Chen, arXiv:0709.3571.
This paper presents Popoviciu type formulas for the generalized restricted partition function for two and three variables. The formula implies that the function is an integer-valued quasi-polynomial. The main result is proved by a reciprocity law for a class of fractional part sums and the theory of generalized Euclidean division.
pdf.

Research Talks

1. Slicing polytopes, TAMU Algebra and Combinatorics Seminar, Nov 16, 2012 at Texas A\&M University.
2. Slicing polytopes, the UC Berkeley Combinatorics Seminar, Nov. 5, 2012 at UC berkeley.
3. Slicing polytopes, 2012 Shanghai Conference on Algebraic Combinatorics, August 17 -22, 2012 at Shanghai Jiao Tong University, Shanghai, China.
4. A canonical expansion of the product of two Stanley symmetric functions (poster), 24nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC'12), July 30 - August 3, 2012 at Nagoya University, Nagoya, Japan.
5. Slicing polytopes, Workshop on convex polytopes, July 23 - 27, 2012 at Kyoto University, Kyoto, Japan.
6. Combinatorial aspects of the hypersimplex, MIT Combinatorics seminar, Dec 2, 2011.
7. Combinatorial aspects of the hypersimplex, Dartmouth Combinatorics seminar, Nov 3, 2011.
8. External zonotopal algebra, special session on algebraic and geometric aspects of matroids, AMS fall southeastern section meeting, Wake Forest University, Winston-Salem, NC, Sep 24-25, 2011. Session Program.
9. H-polynomial of the half-open hypersimplex, special session on algebraic and geometric combinatorics, AMS spring southeastern section meeting, Georgia southern university, Statesboro, GA, March 12-13, 2011. Session Program.
10. Generalized Ehrhart polynomial, Dartmouth Combinatorics seminar, Dec 2, 2010.
11. Generalized Ehrhart polynomial, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC'10), Aug 2-6, 2010.
12. Generalized Ehrhart polynomial, Combinatorics seminar, mathematics department of East China Normal University, June 15, 2010.

Expository Talks

1. Introduction to cluster algebra, cluster algebras and categorification seminar, Sep 29, 2011. Lecture notes.
Cluster algebra is a class of commutative ring, introduced in 2000 by Fomin and Zelevinsky, originally to study Lusztig's dual canonical basis and total positivity. After that, connections have been made to many other fields, including coordinate rings of Grassmannians, quiver representations, Teichmuller theory, invariant theory, tropical calculus, combinatorics, etc. In this introduction, we will start from the example of pentagon recurrence. Then give the definition of cluster algebra and state the Laurent phenomenon and the positivity conjecture. We will then explain the example of triangulation of an n-gon (coordinate ring of Gr(2,n)). Finally, the connection with quiver mutations will be mentioned. This introduction is based on Lauren Williams' 1st lecture in a summer school on cluster algebras at MSRI this August.
2. Schubert polynomials and balanced tableaux, pure math graduate student seminar (PumaGrass), Nov 5, 2010.
Schubert polynomials were introduced by Lascoux and Schutzenberger in 1982 as a combinatorial tool to study some problems in algebraic geometry about Schubert cycles. They are polynomials in n variables, indexed by permutations, and give a convenient basis of the polynomial ring regarded as a free module of dimension n! on the ring of symmetric polynomials. In this talk, we will present some nice combinatorial results related with Schubert polynomials and balanced tableaux, which is a kind of filling of Young diagrams where each hook (argh!) is "balanced". Most definitions and bijections will be introduced via simple, concrete examples.
3. Markov bases: a glimpse of algebraic statistics, the simple person's applied math seminar (SPAMS) Nov 4, 2010.
Algebraic statistics is a relatively new subject which uses algebraic geometry, commutative algebra and combinatorics to study problems in statistics. One of the first such connections is represented by Markov bases, introduced by Diaconis and Sturmfels in a paper on contingency table analysis. In this talk, we will define Markov bases and show how to construct them and how they are related to Grobner bases. We will start with the motivating example of testing independence of contingency tables and finish with a description of the Markov bases of this model. No background in statistics or algebraic geometry is required.

Last updated Dec 1, 2012.