## 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 *i*th 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 2^{n – 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∈λ}*h*_{u}^{k} with
respect to Plancherel measure, where *h*_{u} 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.