Triangle Lectures in Combinatorics

Saturday, November 16, 2019

Lecture Hall: SAS Hall, Room 1102

North Carolina State University

Raleigh, North Carolina

The Triangle Lectures in Combinatorics (TLC) is a series of combinatorial workshops held each semester on a Saturday in the Research Triangle region of North Carolina, funded by the National Science Foundation.  The workshop just under two weeks from now, the 18th installment of the Triangle Lectures in Combinatorics, will be hosted by North Carolina State University in Raleigh, North Carolina on Saturday, November 16, 2019.  It will include four invited talks as well as coffee breaks and ample time for informal discussions throughout the day.

Conference schedule:
9:15-10am, bagels and coffee
10-11am, Georgia Benkart, McKay Quivers in Cooperation with Schur-Weyl Duality
11-11:30am, coffee break
11:30am-12:30pm, Javier Peña, Hoffman constants for systems of linear inequalities
12:30-2:30pm, lunch break
2:30-3:30pm, Margaret Readdy, Geometric proofs of some combinatorial identities of Morel
3:30-4pm, coffee break
4-5pm, Alexander Yong, Complexity, combinatorial positivity, and Newton polytopes
6pm, informal dinner at David’s Dumplings and Noodle Bar

Talk titles and abstracts are posted at the conference web site (https://wp.math.ncsu.edu/tlc/) and also appear near the end of this email.

Pre-registration and conference dinner sign-up: To pre-register, please send email to Patricia Hersh at plhersh@ncsu.edu letting her know you plan to attend or else fill out the pre-registration form at the conference web site.

We are asking that participants pre-register right away if at all possible if they may attend, if they have not done so already, since pre-registration is very helpful for planning the coffee breaks (including how much coffee, how many bagels, etc., to provide) and also for obtaining funding to support these meetings.

Separate from pre-registration, if you plan to attend the conference dinner it would be very helpful if you could email Gabor Pataki (gabor@unc.edu) in advance letting him know this so he can give the restaurant a head count.

Practical information:  See the conference website (https://wp.math.ncsu.edu/tlc/) where some practical information (such as hotel and parking information) is posted.  The nearest airport, for those flying, is the Raleigh-Durham Airport (RDU).

Titles and abstracts for the talks:

Georgia Benkart (University of Wisconsin-Madison)

Title: McKay Quivers in Cooperation with Schur-Weyl Duality

The well-known McKay Correspondence is a bijection between the finite subgroups G of SU2 and the simply-laced affine Dynkin diagrams. McKay’s insight was that the quivers determined by tensoring the simple G-modules with the G-module V = ℂ2 exactly correspond to the affine Dynkin diagrams of types A, D, E. McKay quivers are related to Auslander-Reiten quivers in the representation theory of finite-dimensional algebras and to a host of other topics such as singularity theory and orbifolds. This talk will focus on connecting McKay quivers to Schur-Weyl duality. For any finite group G (or finite-dimensional Hopf algebra) and any finite- dimensional G-module V, this combined theory provides results on the tensor product module V⊗kand its G-invariants, and on the centralizer algebra EndG(V⊗k), which often has a nice diagrammatic realization and a rich combinatorics. There are applications to chip-firing dynamics and Markov chains.

Javier Peña (Carnegie Mellon University)

Title: Hoffman constants for systems of linear inequalities

Abstract: A classical result of Hoffman (1952) shows that the distance from a point u to a non-empty polyhedron defined by the system of inequalities Ax ≤ b can be bounded above in terms of the “error” or “residual” (Au-b)+ = max(0,Au-b). More precisely, the distance from u to the nonempty polyhedron {x: Ax ≤ b} is bounded above by H(A)*|(Au-b)+| for some Hoffman constant H(A) that depends only on the matrix A. This type of “error bound” plays a fundamental role in mathematical programming.

This talk will give a new and constructive proof of existence and characterization of the Hoffman constant H(A). We will discuss our developments in the following more general “relative” context. Suppose R is a “reference” polyhedron representing some easy-to-satisfy constraints such as box constraints. Then the distance from a point u ∈ R to the nonempty polyhedron {x ∈ R: Ax ≤ b} is bounded above by H(A|R)*|(Au-b)+| for some “relative Hoffman constant” H(A|R).

Our results readily yield a novel combinatorial algorithm to compute Hoffman constants. The latter is a timely but notoriously difficult and largely unexplored computational problem.

Margaret Readdy (University of Kentucky)

Title: Geometric proofs of some combinatorial identities of Morel

Using the algebraic and geometric combinatorics of the permutahedron, we give proofs of combinatorial identities which arise in the technical heart of Morel’s computation of the intersection cohomology of Shimura varieties. No prior background will be assumed.

This is joint work with Richard Ehrenborg and Sophie Morel.

Alexander Yong (U. Illinois at Urbana-Champaign)

The Nonvanishing Problem asks if a coefficient of a polynomial is nonzero. Many families of polynomials in algebraic combinatorics admit combinatorial counting rules and simultaneously enjoy having saturated Newton polytopes (SNP). Thereby, in amenable cases, Nonvanishing is in the complexity class of problems with “good characterizations”. This suggests a new algebraic combinatorics viewpoint on complexity theory.

This talk discusses the case of Schubert polynomials. These form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. We give a tableau criterion for Nonvanishing, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the n x n grid, together with a theorem of A. Fink, K. Meszaros and A. St. Dizier, which proved a conjecture of C. Monical, N. Tokcan and the speaker.

This is joint with Anshul Adve (U. California, Los Angeles, USA) and Colleen Robichaux (U. Illinois at Urbana-Champaign, USA).

We would appreciate if you could forward this announcement to others you know who may be interested in participating.    Thanks very much.

We hope you will be able to attend!

Fall 2019 TLC Organizing committee: Patricia Hersh (NCSU, Chair), Gabor Hetyei (UNC Charlotte), Kailash Misra (NCSU), and Gabor Pataki (UNC Chapel Hill)