Abstracts of Talks
Marcelo Aguiar, Texas A&M University
Monoidal Categories, Joyal's Species, and Combinatorial Hopf Algebras
The category of species constitutes a good framework for the study of certain algebraic structures associated to combinatorial objects. One of the advantages of the notion of species is its simplicity: roughly, a species is a family of vector spaces, one space for each finite set. We will define species and concentrate on the notion of "bimonoid" in the category of species, illustrating it with a couple of examples of a combinatorial nature. We will briefly discuss how to construct bialgebras out of bimonoids in species, emphasizing the analogy with classical constructions in algebraic topology and quantum groups. This is joint work with Swapneel Mahajan.
Drew Armstrong, University of Minnesota
The Sorting Order on a Coxeter Group
Let (W, S) be a Coxeter system and let ω ∈ S* be any finite or infinite sequence in the generators. Each element of W that occurs as a subword of ω has a lexicographically first reduced occurrence in ω — called its ω-sorted word — and the inclusion order on these sorted words is called the ω-sorting order.
The sorting order has some remarkable properties — it is strictly between the right weak order and the Bruhat order on W; it is graded by the usual Coxeter length; it is a supersolvable join-distributive lattice; and it is a maximal lattice in the sense that the addition of any collection of Bruhat covers results in a nonlattice. Moreover, sorting orders are the only way we know to put a lattice structure on the elements of an infinite Coxeter group.
Alexander Barvinok, University of Michigan, Ann Arbor
An Asymptotic Estimate for the Number of Contingency Tables
We present an asymptotic estimate for the number of m x n non-negative integer matrices with prescribed row and column sums. As a corollary, we show that if an m-vector R of row sums and an n-vector C of column sums are sufficiently non-uniform, then in the finite probability space of m x n non-negative integer matrices with the total sum N of entries, the event consisting of the matrices with the row sums R and the event consisting of the matrices with the column sums C are (strongly) positively correlated, instead of being (almost) independent, as our intuition suggests.
Louis Billera, Cornell University
Mistakes I Didn't Make
Anders Björner, KTH
Mixed Connectivity, Polytope Boundaries, and Matroid Basis Graphs
A pure poset P is (k, t)-rigid if P \ F is topologically t-connected, pure and of the same length as P, for every filter F ⊂ P generated by at most k – 1 elements. Our main result is a theorem showing how (k, t)-rigid posets naturally arise.
Applying this to face lattices one gets a concept of a regular CW-complex being (k, t)-connected, namely if removal of any set of at most k – 1 cells (and all cells containing them) leaves a topologically t- connected subcomplex of the same dimension. Note that we quantify over cells of all dimensions. This is because just removing vertices gives a weaker concept in dimensions ≥ 2.
We present some applications to
- Polytope boundaries and manifolds (generalizations of the Balinski, Barnette and Fløystad theorems)
- Finite Coxeter groups (Coxeter relations avoiding forbidden elements)
- Matroid basis graphs (connectivity results)
Francesco Brenti, University of Rome
Kazhdan-Lusztig Polynomials and the Complete cd-Index
Kazhdan-Lusztig polynomials are polynomials in one variable with integer coefficients, indexed by pairs of elements of any Coxeter group. They were first defined by Kazhdan and Lusztig [Invent. Math. 53 (1979), 165–184], and have proven to be of fundamental importance in several areas of mathematics, including representation theory and the geometry of Schubert varieties.
Our purpose in this talk is to show that one can associate to any pair of elements u,v in any Coxeter group a noncommutative polynomial in c and d, which we call the complete cd-index of u,v, and that the Kazhdan-Lusztig polynomial of u,v can be computed in a simple, combinatorial and explicit way from this polynomial. We give a formula for the coefficients of the complete cd-index of any two elements of any Coxeter group, explain its relation to the usual cd-index, and conjecture that these coefficients are always nonnegative.
This is joint work with Lou Billera.
Kristin Camenga, Houghton College
Relations on Solid Angles of Low-Dimensional Polytopes
The ith angle sum of a polytope counts the sum of the solid angles at i-dimensional faces of a polytope. We define the γ-vector of a polytope as a linear combination of the angle sums in a manner analogous to the h-vector as a linear combination of the f-vector. This gives a simplified formulation of the Perles relations, the angle-analog of the Dehn-Sommerville relations on simplicial polytopes. We also prove results about the nature of the gamma-vector, showing the entries of the gamma-vectors are non-decreasing for low-dimensional simplices and non-negative for certain classes of low-dimensional polytopes.
Camenga Lecture Notes (PDF)
Richard Ehrenborg, University of Kentucky
Toric Arrangements
We extend the classical Billera-Ehrenborg-Readdy map between the intersection lattice and face lattice of a central hyperplane arrangement to toric hyperplane arrangements. For toric arrangements, we also generalize Zaslavsky's fundamental results on the number of regions.
Joint work with Margaret Readdy and Michael Slone.
Gábor Hetyei, University of North Carolina, Charlotte
Links We Almost Missed Between Delannoy Numbers and Legendre Polynomials
It has been known for over half a century that the central Delannoy numbers may be obtained by substituting 3 into the Legendre polynomials, but until recently this fact was considered a "coincidence". In this talk we outline three possible explanations. The first leads to a join operation on balanced simplicial complexes that preserves the Cohen-Macaulay property. The second leads to triangulations of a symmetric variant of the root polytopes introduced by Gelfand, Graev, and Postnikov. The third involves lattice path enumeration.
Hetyei Lecture Notes (PDF)
Sam Hsiao, Bard College
The Cone of Flag f-Vectors of Nonpure Posets
Building on Billera and Hetyei's classification of linear inequalities for flag f-vectors of graded posets, we show that the closure of the cone of flag f-vectors of finite nonpure bounded posets (i.e., posets that have a 0 and a 1 but that are not necessarily graded) of rank n is a simplicial cone of dimension 2n – 1. We discuss how the extreme rays of these simplicial cones give rise to a new basis of quasisymmetric functions with nonnegative multiplicative structure constants.
This is joint work with Lauren Rose, Rachel Stahl, and Ezra Winston.
Carly Klivans, University of Chicago
Cubical Complexes and a Cellular Matrix Tree Theorem
We generalize the definition and enumeration of spanning trees to the setting of an arbitrary CW-complex. We prove a cellular version of the Matrix Tree-Theorem that counts spanning trees, weighted by the squares of the orders of their top-dimensional integral homology groups, in terms of the Laplacian.
In the case of cubical complexes we generalize known results for graphical spanning trees of the hypercube. In particular we show that arbitrary skeleta of hypercubes are Laplacian integral and give formulas for their eigenvalues and number of cellular spanning trees.
This is joint work with Art Duval and Jeremy Martin.
Kathryn Nyman, Loyola University Chicago
Two-Batch Liar Games on a General Bounded Channel
We imagine an extension of the 2-person Re'nyi-Ulam liar game in which Carole thinks of a number between 1 and n, and Paul tries to determine this number. Carole is allowed to lie in response to Paul's questions up to k times and according to a channel of allowable lie strings. We look at a two-batch strategy of packings and coverings, and find bounds on n for which Paul can win the game.
This is joint work with Robert Ellis.
Nyman Lecture Notes (PDF)
Shmuel Onn, Technion
Nonlinear Discrete Optimization
We develop an algorithmic theory of nonlinear optimization over sets of integer points presented by inequalities or by oracles. Using a combination of geometric and algebraic ideas, involving objects that include zonotopes and Graver bases, we provide polynomial-time algorithms for nonlinear optimization over broad classes of integer programs in variable dimension. I will overview this work, joint with many colleagues over the last few years, and discuss some of its many applications, to high-dimensional tables, congestion-avoiding transportation, privacy in data bases, error correcting codes, matroids, matchings, networks, and more.
I will conclude by introducing a new graph invariant — the Graver complexity of a graph — that controls the computational complexity of nonlinear integer programming. Of particular importance is the Graver complexity of the complete 3 by m bipartite graph, that, quite intriguingly, is as yet unknown for all m greater than 3.
Onn Lecture Notes (PDF)
Margaret Readdy, University of Kentucky
The Möbius Function of Partitions with Restricted Block Sizes
We study filters in the partition lattice formed by restricting to partitions by type. The Möbius function is determined in terms of the easier-to-compute descent set statistics on permutations and the Möbius function of filters in the lattice of integer compositions. When the underlying integer partition is a knapsack partition, the Möbius function on integer compositions is determined by a topological argument. In this proof the permutahedron makes a cameo appearance.
This is joint work with Richard Ehrenborg.
Richard Stanley, MIT
Partition Statistics with Respect to Plancherel Measure
The Plancherel measure P on the set of all partitions of a positive integer n is defined by P(λ) = (fλ)2/n!, where fλ is the number of standard Young tableaux of shape λ. Recent work of Guoniu Han suggests investigating such questions as the average value of Σu∈λhuk with respect to Plancherel measure, where hu is the hook length of the square u of (the Young diagram of) λ. We will discuss some results and conjectures in this area.
Catherine Stenson, Juniata College
Line Shelling Zonotopes of Polytopes
Let P be a polytope with the origin in its interior. The line shellings of P generated by lines through the origin correspond to the vertices of a zonotope. We will describe the construction of this line shelling zonotope and discuss some of its properties.
Stenson Lecture Notes (PDF)
Hugh Thomas, University of New Brunswick
Oriented Interval Greedoids
Interval greedoids are a class of greedoids including both matroids and antimatroids (convex geometries). I will discuss an axiomatization of covectors for interval greedoids. If the underlying greedoid is a matroid, the definition gives the covectors of an oriented matroid. If the underlying greedoid is an antimatroid, we recover the set of faces of the sphere associated to a convex geometry by Billera, Hsiao, and Provan. We show that any oriented interval greedoid defines a CW-sphere, and that it satisfies enumerative results which had previously been proved separately in the matroid and antimatroid cases. This is joint work with Franco Saliola.
Stephanie van Willigenburg, University of British Columbia
Quasisymmetric Schur Functions
In this talk we introduce a new basis for quasisymmetric functions, which is obtained from a specialization of nonsymmetric Macdonald polynomials to Demazure atoms. We call this basis the basis of quasisymmetric Schur functions since the elements partition Schur functions in a natural way. Furthermore, we shall show how these quasisymmetric Schur functions exhibit a Pieri rule for quasisymmetric functions that naturally generalizes the Pieri rule for symmetric functions. This is joint work with Jim Haglund, Kurt Luoto, and Sarah Mason.