# Discrete Mathematics and Computer Science Day at Albany

## Saturday, March 18, 2006

#### Schedule and Abstracts:

• 9:15-9:50 am -- Light Breakfast
• 9:50-10:00 am -- Welcome
• 10:00-10:40 am -- Alexandre Tchernev, University at Albany
• Title: Matroids and the study of multigraded modules
Abstract: In recent work the speaker used the theory of matroids to provide an explicit combinatorial construction of free resolutions for multigraded modules. In this talk we will discuss some aspects of this construction, and the interesting combinatorial problems that arise when one tries to use it in the study of the homological properties of multigraded modules.
• 10:40-11:00 am -- Coffee Break
• 11:00 am - noon -- Bruce Sagan, Michigan State University
• Title: Counting Permutations by Congruence Class of Major Index (joint work with Helene Barcelo and Sheila Sundaram)
Abstract: Let S_n be the symmetric group of all permutations of {1,2,...,n}. A permutation pi = a_1 a_2 ... a_n in S_n (written in one-line form) has major index maj pi = sum_{a_i>a_{i+1}} i, i.e., maj pi is the sum of all the indices i where pi has a descent. The major index is an important statistic in combinatorics and has many interesting properties. Now fix two positive integers k, l which are relatively prime (have no common factors) and are at most n. Let m_n^{k,l} be the k-by-l matrix whose (i,j) entry is the cardinality of the set {pi in S_n : maj pi = i (mod k) and maj pi^{-1} = j (mod l)}. Surprisingly, this matrix has all its entries equal! We will outline a combinatorial proof of this theorem and other related results.
• 12:00-2:00 pm -- Lunch and Discussion Break
• 2:00-3:00 pm -- Diane L. Souvaine, Tufts University
• Title: Computational Geometry and Depth-Based Statistics
Abstract: The statistical concept of "data depth" assigns a numeric value to a point, corresponding to its centrality either relative to F, a probability distribution in R^d, or relative to a given data cloud. We show how computational geometry (a subfield of algorithmic design that is concerned with the design and analysis of algorithms for solving geometric problems) has contributed to the study of statistical data-depth methods and produced fresh insights and new algorithms.
• 3:00-3:30 pm -- Coffee Break
• 3:30-4:10 pm -- Anders S. Buch, Rutgers University
• Title: Eigenvalues of Hermitian matrices with positive sum of bounded rank
Abstract: A classical question in linear algebra asks when three weakly decreasing n-tuples of real numbers can be the eigenvalues of three Hermitian matrices with sum zero. Klyachko has proved that this is the case if and only if the n-tuples satisfy a list of linear inequalities. These inequalities are defined in terms of non-vanishing Littlewood-Richardson coefficients, and have been studied with a mixture of combinatorial and geometric methods. I will present necessary and sufficient inequalities for the possible eigenvalues of three Hermitian matrices with positive semidefinite sum of bounded rank, which extends work of Friedland and Fulton.
• 4:15-4:55 pm -- Caroline J. Klivans, University of Chicago
• Title: Generalized Degree Sequences (joint work with Uri Peled and Amitava Bhattacharya)
Abstract: Degree sequences of graphs have been thoroughly studied. For example, there are many simple characterizations of when an integer sequence is the degree sequence of a graph and of graphs with "extremal" degree sequences. Notions of generalized degree sequences for higher dimensional simplicial complexes are not as well investigated. I will talk about work in progress on understanding these degree sequences and those classes of complexes which exhibit analogous extremal behavior.
• 5:00 pm -- Meeting Ends