Tea in POT 745 at 3:14 pm = π time

Speaker:  Mihai Ciucu, Indiana University

Title:  Cruciform regions and a conjecture of Di Francesco

Abstract:

The problem of finding formulas for the number of tilings of lattice regions goes back to the early 1900's, when MacMahon proved (in an equivalent form) that the number of lozenge tilings of a hexagon is given by an elegant product formula. In 1992, Elkies, Kuperberg, Larsen and Propp proved that the Aztec diamond (a certain natural region on the square lattice) of order n has 2^n(n+1)/2 domino tilings. A large related body of work developed motivated by a multitude of factors, including symmetries, refinements and connections with other combinatorial objects and statistical physics. It was a model from statistical physics that motivated the conjecture which inspired the regions we will discuss in this talk.

In recent work on the twenty vertex model, Di Francesco was led to a conjecture which states that the number of domino tilings of a certain family of regions on the square lattice is given by a product formula reminiscent of the one giving the number of alternating sign matrices. These regions, denoted T_n, are obtained by starting with a square of side-length 2n, cutting it in two along a diagonal by a zigzag path with step length two, and gluing to one of the resulting regions half of an Aztec diamond of order n-1. Inspired by the regions T_n, we construct a family of cruciform regions C_m,n^a,b,c,d generalizing the Aztec diamonds and we prove that their number of domino tilings is given by a simple product formula. Since (as it follows from our results) the number of domino tilings of the region T_n is a divisor of the number of tilings of the cruciform region C_2n-1,2n-1^n-1,n,n,n-2, the special case of our formula corresponding to the latter can be viewed as partial progress towards proving Di Francesco's conjecture.

As the term ``big data'' appears more and more frequently in our daily life and research activities, it changes our knowledge of how large the scale of the data can be and challenges the application of numerical analysis for performing statistical calculations on computers. In this talk, I will focus on two basic statistics problems---sampling a multivariate normal distribution and maximum likelihood estimation---and illustrate the scalability issue that many traditional numerical methods are facing. The large-scale challenge motivates us to develop linearly scalable numerical linear algebra techniques in the dense matrix setting, which is a common scenario in data analysis. I will present several recent developments on the computations of matrix functions and on the solution of a linear system of equations, where the matrices therein are large-scale, fully dense, but structured. The driving ideas of these developments are the exploration of the structures and the use of fast matrix-vector multiplications to reduce the quadratic cost in storage and cubic cost in computation for a general dense matrix. ``Big data'' provides a fresh opportunity for numerical analysts to develop algorithms with a central goal of scalability in mind. Scalable algorithms are key for convincing statisticians and practitioners to apply the powerful statistical theories on large-scale data that they currently feel uncomfortable to handle.