# Triangle Lectures in Combinatorics at UNC

Event

These are a new series of combinatorial workshops, held once per semester, each on a Saturday. They will rotate among the universities in the Research Triangle. We hope to have participants from numerous colleges and universities within a few hours drive, and perhaps from even farther away. These workshops are funded by the National Science Foundation, in particular enabling us to bring in four exciting speakers to give one hour talks each time. **TLC steering committee:** Patricia Hersh (NCSU), Ezra Miller (Duke), Scott Provan (UNC Chapel Hill), and Nathan Reading (NCSU)

**Upcoming Fall 2011 meeting:** November 5, 2011 at UNC Chapel Hill**Speakers:**Thomas Lam (Michigan), Jesus De Loera (UC Davis), Ezra Miller (Duke) and Doron Zeilberger (Rutgers)**To preregister:** send email to Patricia Hersh, plhersh@ncsu.edu (there is no registration fee)**Lecture hall:** Hanes 120**Talk titles and abstracts:**

Speaker: Jesus A. De Loera, Univ. of California, Davis

Title: Algebraic-Geometric Algorithms in Discrete Optimization

Abstract: It is common knowledge that the understanding of the combinatorial geometry of convex bodies has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebraic-combinatorial geometry in optimization appears even greater.

In the past 5 years two beautiful geometric algorithms on polyhedral have been used to prove unexpected new results on the computation of integer programs (both linearly *and* non-linearly constrained). The first is Barvinok's algorithm for polytopes, the second is Graver's bases method on polyhedral cones. I will describe these two algorithms and explain why we can now prove theorems that were beyond our reach before, mostly about integer optimization with non- linear objectives. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results.

This a nice story collecting results contained in several papers joint work with various subsets of the following people: R. Hemmecke, M. Koeppe, S. Onn, U. Rothblum, and R. Weismantel. Our monograph with the same title is scheduled to be published by SIAM-MOS series next year.

Speaker: Thomas Lam, University of Michigan

Title: Electrical Networks and Lie Theory

Abstract: Electrical networks consisting only of resistors are modeled in combinatorics by undirected weighted graphs, where the weight of an edge is the resistance of a resistor. Some basic questions one asks are: (1) to compute the electrical properties of the network: for example what current flows through when certain voltages are applied at particular vertices, (2) when two electrical networks have identical electrical properties: for example two resistors in series or in parallel can be replaced by a single resistor, (3) to what extent an electrical network can be reconstructed if its electrical properties are known.

In this talk we will discuss these problems in a combinatorial and algebraic context. In particular, I'll explain how certain simple combinatorial operations on electrical networks give rise to a Lie group action on the space of electrical networks, allowing one to apply ideas from Lie theory and representation theory.

This talk is based on joint work with Pavlo Pylyavskyy.

Speaker: Ezra Miller, Duke University

Title: Binomial Irreducible Decomposition

Abstract: Monomial irreducible decomposition combinatorially expresses the (exponents on the) monomials outside of a monomial ideal as a union of box-shaped sets of lattice points. Binomial irreducible decomposition aims for a similar outcome when the input is a binomial ideal, but its existence has until now remained open. This talk is about equivalence relations and partial orders on commutative monoids, explicitly described in terms of lattice points, as in the monomial case. The resulting combinatorics, along with a modicum of abelian group character theory, yields binomial irreducible decomposition. This is joint work with Thomas Kahle.

Speaker: Doron Zeilberger, Rutgers University

Title: Statistical Combinatorics

Abstract: A large part of traditional "continuous" probability and statistics can be redone (and improved!) using purely combinatorial arguments plus a computer algebra system. **Suggested hotels:**

Chapel Hill University Inn Hotel - Chapel Hill, North Carolina (NC)

1301 N. Fordham Blvd, Chapel Hill

Reservations: 1-888-452-5765; Contact: 919-929-2171

Rate: $89.50 for a room with one king or 2 double beds

Days Inn Chapel Hill, 1312 North Fordham Blvd, Chapel Hill, NC 27514

Phone: 919-929-3090

Rate: $71.40 for room with king or 2 double beds**Parking info:** UNC Chapel Hill visitor parking info web site**Preregistered participants (so far):** Ed Allen, Wake Forest (NC)

Prakash Belkale, UNC Chapel Hill (NC)

Christine Berkesch, Duke (NC)

Sarah Birdsong, UNC Charlotte (NC)

Shaoshi Chen, NCSU (NC)

Jesus De Loera, UC Davis (CA)

Graham Enos, UNC Charlotte (NC)

Alex Fink, NCSU (NC)

Anant Godbole, East Tennessee State University (TN)

Patricia Hersh, NCSU (NC)

Gabor Hetyei, UNC Charlotte (NC)

JT Hird, NCSU (NC)

John Hutchens, NCSU (NC)

Thomas Lam, Michigan (MI)

Sonja Mapes, Duke (NC)

Ezra Miller, Duke (NC)

Michael Mossinghoff, Davidson College (NC)

Chris O'Neill, Duke (NC)

Elizabeth Niese, Marshall University (WV)

Daniel Orr, UNC Chapel Hill (NC)

Gabor Pataki, UNC Chapel Hill (NC)

Lindsay Piechnik, High Point University (NC)

Bob Proctor, UNC Chapel Hill (NC)

Scott Provan, UNC Chapel Hill (NC)

Nathan Reading, NCSU (NC)

Richard Rimanyi, UNC Chapel Hill (NC)

Jack Snoeyink, UNC Chapel Hill (NC)

Seth Sullivant, NCSU (NC)

Doron Zeilberger, Rutgers (NJ)**Organizing committee:** Prakash Belkale, Gabor Pataki, Bob Proctor, Scott Provan, Richard Rimanyi

**Recent meeting:** April 9, 2011 at NCSU, SAS Hall Room 1102, Raleigh, NC**Talk slides (for the two computer talks):**

Vic Reiner (University of Minnesota), P-partitions revisited

Stephanie van Willigenburg (UBC), Quasisymmetric refinements of Schur functions**Schedule:**

9:15-10am, coffee, tea and bagels (just outside SAS 1102)

10-11am, John Stembridge (University of Michigan), ``A finiteness theorem for W-graphs''

11-11:30am, coffee break

11:30am-12:30pm, Prakash Belkale (UNC Chapel Hill), ``Combinatorial questions related to the Hermitian eigenvalue problem''

2:30-3:30pm, Stephanie van Willigenburg (UBC), ``Quasisymmetric refinements of Schur functions''

3:30-4pm, coffee break

4-5pm, Vic Reiner (University of Minnesota), ``P-partitions revisited''

Evening: dinner and games night (boggle, scrabble, etc.)**Parking:** You may park right outside SAS Hall for free. Here is a map of the campus with parking lots marked. On Saturdays, you can park anywhere on campus that is not specifically marked as being restricted (e.g. handicap spots are still off limits). We are hopeful that you won't need any lot except the one by SAS Hall. SAS Hall is at the right of the map, just left of the compass, and its parking lot is a large one shaded red on the map. A back-up option for parking is the coliseum parking deck. **The room:** SAS Hall 1102 is the room immediately to your right when you enter from the parking lot. If you enter from the courtyard side, go down the long stairway or the elevators.**Hotel recommendations:** within short walk of the math department are three hotels: Holiday Inn Brownstone (800-331-7919), Velvet Cloak Inn (919-828-0333) and Cameron Park Inn Bed and Breakfast (919-835-2171). Those with cars might also consider hotels farther away such as various choices on Wake Town Drive, which is near numerous good restaurants; some such hotels (all right next to each other) are Marriott Courtyard (919-821-3400), Hampton Inn (919-828-1813), or Extended Stay America (919-829-7271). **Talk titles and abstracts:**

Prakash Belkale, ``Combinatorial questions related to the Hermitian eigenvalue problem.''

I will first review the ``classical" work on the Hermitian eigenvalue problem which characterizes the possible eigenvalues of a sum of Hermitian matrices in terms of the eigenvalues of the summands. By the work of many authors, this problem is related to two other important problems in geometry and representation theory: Schubert calculus of grassmannians (related to the famous combinatorial Littlewood-Richardson rule) and the invariant theory of GL(n). I will discuss some of the combinatorial questions that arise when we generalize to the case of arbitrary groups (such as the symplectic and orthogonal groups), and to maps between groups.

Vic Reiner, ``P-partitions revisited'' (joint work with Valentin Feray)

Counting the linear extensions of a general partially ordered set (poset) is hard. We'll explain a new product formula which works for a certain class of posets, generalizing a formula for forest posets due to Knuth, and its q-generalization by Bjorner and Wachs.

We'll also explain how this formula arises naturally when one re-examines Stanley's P-partitions from the perspective of convex cones and their affine semigroup rings.

John Stembridge, ``A finiteness theorem for W-graphs''

Given a Coxeter group W, a W-graph is a combinatorial structure that encodes a W-module, or more generally, a module for the associated Iwahori-Hecke algebra. Of special interest are the W-graphs that encode the action of the Hecke algebra on its Kazhdan-Lusztig basis, as well as the action on individual cells. Knowing the W-graph allows easy computation of the Kazhdan-Lusztig polynomials.

Previously we isolated a few basic features common to the W-graphs in Kazhdan-Lusztig theory and used these to define the class of "admissible" W-graphs. What makes this class remarkable is that it is amenable to combinatorial analysis and (we hope) classification theorems. In this talk, we will explain a surprisingly simple (but non-constructive) proof that for each finite Coxeter group W, there are only finitely many admissible W-cells (i.e., strongly connected W-graphs). We also plan to report on the feasibility of constructing the Kazhdan-Lusztig W-graph without first computing Kazhdan-Lusztig polynomials.

Stephanie van Willigenberg, ``Quasisymmetric refinements of Schur functions''

Schur functions were introduced early in the last century with respect to representation theory, and since then have become important functions in other areas such as combinatorics and algebraic geometry. They have a beautiful combinatorial description in terms of diagrams, which allows many of their properties to be determined. In this talk we introduce quasisymmetric Schur (QS) functions, which partition Schur functions in a natural way. Furthermore, we show how these QS functions also refine many well known combinatorial Schur function properties. Extending the definition of QS functions, we define skew QS functions, which likewise partition skew Schur functions. We observe how these functions arise in the study of other algebras such as NCQSym and the algebra of Poirier-Reutenauer. This is joint work with Christine Bessenrodt, Jim Haglund, Kurt Luoto and Sarah Mason. **List of pre-registered participants:**

Ed Allen, Wake Forest University (NC)

Moa Apagodu, Virginia Commonwealth University (VA)

Alyssa Armstrong, NCSU (NC)

Sami Assaf, MIT (MA)

Eugenia Bakunova, NCSU (NC)

Erin Bancroft, NCSU (NC)

Cammie Smith Barnes, Sweet Briar College (VA)

Prakash Belkale, UNC Chapel Hill (NC)

Hoda Bidkhori, NCSU (NC)

Sarah Birdsong, UNC Charlotte (NC)

Abigail Bishop, NCSU (NC)

Emily Braley, UNC Chapel Hill (NC)

Ruth Davidson, NCSU (NC)

Graham Enos, UNC Charlotte (NC)

Alex Fink, NCSU (NC)

Jim Haglund, University of Pennsylvania (PA)

Allison Hedges, NCSU (NC)

Patricia Hersh, NCSU (NC)

Gabor Hetyei, UNC Charlotte (NC)

Bill Hightower, High Point University (NC)

J.T. Hird, NCSU (NC)

John Hutchens, NCSU (NC)

Austin Jones, Wake Forest University (NC)

Min Kang, NCSU (NC)

John Konvalina, NCSU (NC)

Sonja Mapes, Duke (NC)

Sarah Mason, Wake Forest University (NC)

Jed Mihalisin, Meredith College (NC)

Ezra Miller, Duke (NC)

Kailash Misra, NCSU (NC)

Walter Morris, George Mason University (VA)

Elizabeth Munch, Duke (NC)

Elizabeth Niese, Virginia Tech (VA)

Chris O'Neill, Duke (NC)

Daniel Orr, UNC Chapel Hill (NC)

Gabor Pataki, UNC Chapel Hill (NC)

Robert Proctor, UNC Chapel Hill (NC)

Nathan Reading, NCSU (NC)

Victor Reiner, Minnesota (MN)

Carla Savage, NCSU (NC)

Mike Schuster, NCSU (NC)

Anne Shiu, Duke (NC)

Michael Singer, NCSU (NC)

Rohit Sivaprasad, NCSU (NC)

Richard Stanley, MIT (MA)

John Stembridge, Michigan (MI)

Ernie Stitzinger, NCSU (NC)

Seth Sullivant, NCSU (NC)

Dewey Taylor, Virginia Commonwealth University (VA)

Chris Thunes, NCSU (NC)

Stephanie van Willigenburg, UBC (BC)

Ryan Vinroot, College of William and Mary (VA)

Gopal Viswanathan, NCSU (NC)

Kangkang Wang, Duke (NC)

Matt Willis, UNC Chapel Hill (NC)

Hangjun Xu, Duke (NC)**Organizing committee:** Hoda Bidkhori (NCSU), Alex Fink (NCSU), Patricia Hersh (NCSU), Carla Savage (NCSU).

**Past meetings:****Second meeting:** September 25, 2010 at Duke**Speakers:** Alexander Barvinok (University of Michigan), Anne Shiu (Duke), Sami Assaf (MIT), Persi Diaconis (Stanford).**Organizing committee:** Patricia Hersh (NCSU), Sonja Mapes (Duke), Ezra Miller (Duke).**More information****First meeting:** February 6, 2010 at NC State**Speakers:** Carla Savage (NCSU), Bernd Sturmfels (UC Berkeley), Ed Swartz (Cornell), Laszlo Szekely (University of South Carolina).**Organizing committee:** Patricia Hersh (NCSU), Ezra Miller (Duke), Scott Provan (UNC) Nathan Reading (NCSU). **More information**