Triangle Lectures in Combinatorics (TLC)

Fourth meeting: November 5, 2011 at UNC Chapel Hill


Talk slides (for the computer talks):

Jesus De Loera (UC Davis), Algebraic-Geometric ideas in Discrete Optimization

Ezra Miller (Duke), Scanned Lecture Notes and slides

Speakers: Thomas Lam (Michigan), Jesus De Loera (UC Davis), Ezra Miller (Duke) and Doron Zeilberger (Rutgers)

Lecture hall for Saturday workshop: Hanes 120 (main floor). Refreshments not permitted in the classrooms. Hanes is just east of Phillips Hall and just south of Cameron Ave (not to be confused with Hanes Art Center!)

UNC Chapel Hill Campus Map: as pdf file.


Friday Afternoon Seminar Schedule:

Friday, 5:15-6:15pm, UNC-CH math seminar talk (Phillips Hall 367): Thomas Lam, Projected Richardson Varieties

Jesus De Loera -- Friday seminar talk cancelled

Friday evening: dinner (location TBA)

Saturday Workshop Schedule:

9:15am-10am, coffee, tea and bagels (third floor of Hanes)

10-11am, Jesus de Loera, Algebraic-Geometric Algorithms in Discrete Optimization

11-11:30am, cofee break

11:30am-12:30pm, Doron Zeilberger, Statistical Combinatorics

12:30-2:30pm, lunch

2:30-3:30pm, Thomas Lam, Electrical Networks and Lie Theory

3:30-4pm, cofee break

4-5pm, Ezra Miller, Binomial Irreducible Decomposition

Saturday evening: dinner (Talullas, 456 W. Franklin Street) -- please email plhersh@ncsu.edu to RSVP for dinner if you plan to attend the dinner.


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 al\ gorithm 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 w\ ith 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 schedu\ led 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 exampl\ e 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 lattic\ e 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.


Friday seminar talk:

Geometric Methods in Representation Theory Seminar Talk: Thomas Lam, Projected Richardson Varieties

Abstract: Richardson varieties are intersections of a Schubert variety with an opposite Schubert variety. I will discuss some of the remarkable geometric and combinatorial properties of the projections of Richardson varieties fr\ om the full flag variety to partial flag varieties. These projected Richardson varieties play a role in a surprising number of subjects: total positivity, Poisson geometry, Frobenius splitting, quantum cohomology, and so on.



This talk is based on joint work with Knutson and Speyer, and with He.


Directions and parking information: 2 page pdf file

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

Preregistered participants:

Geir Agnarsson, George Mason University (VA)
Ed Allen, Wake Forest (NC)
Taylor Allison, NCSU (NC)
Alyssa Armstrong, NCSU (NC)
Camillia Smith Barnes, Sweet Briar College (VA)
Jonathan Beagley, George Mason University (VA)
Melissa Bechard, Wake Forest (NC)
Prakash Belkale, UNC Chapel Hill (NC)
Christine Berkesch, Duke (NC)
Hoda Bidkhori, NCSU (NC)
Sarah Birdsong, UNC Charlotte (NC)
Shaoshi Chen, NCSU (NC)
Ruth Davidson, NCSU (NC)
Sajal Dash, UNC Chapel Hill (NC)
Jesus De Loera, UC Davis (CA)
Graham Enos, UNC Charlotte (NC)
Alex Fink, NCSU (NC)
Jennifer Gamble, NCSU (NC)
Anant Godbole, East Tennessee State University (TN)
Ian Haywood, NCSU (NC)
Allison Hedges, NCSU (NC)
Patricia Hersh, NCSU (NC)
Gabor Hetyei, UNC Charlotte (NC)
JT Hird, NCSU (NC)
Johnny Humphries (NC)
John Hutchens, NCSU (NC)
Naihuan Jing, NCSU (NC)
Garrett Johnson, NCSU (NC)
Austin Jones, NCSU (NC)
JiYoon Jung, University of Kentucky (Lexington, KY)
Nets Katz, Indiana University (Bloomington, IN)
Sangwook Kim, George Mason University (Fairfax, VA)
Yonggu Kim, visiting NCSU from Korea (NC)
Patricia Klein, NCSU (NC)
David Lax, UNC Chapel Hill (NC)
Matthew Macauley, Clemson University (Clemson, SC)
Sonja Mapes, Duke University (NC)
Sarah Mason, Wake Forest University (Winston-Salem, NC)
Leo Mihalcea, Virginia Tech (Blacksburg, VA)
Jed Mihalisin, Meredith College (Raleigh, NC)
Ezra Miller, Duke University (NC)
Kailash Misra, NCSU (NC)
Michael Mossinghoff, Davidson College (Davidson, NC)
Liz Munch, Duke University (NC)
Elizabeth Niese, Marshall University (Huntington, WV)
Asamoah Nkwanta, Morgan State University (Baltimore, MD)
Isaballa Novik, Univ. of Washington (Seattle, WA)
Matthew O'Meara, UNC Chapel Hill (NC)
Lindsay Piechnik, High Point University (High Point, NC)
Nathan Reading, NCSU (NC)
Carla Savage, NCSU (NC)
Seth Sullivant, NCSU (NC)
Ryan Vinroot, College of William and Mary (Williamsburg, VA)
Mirko Visontai, U Penn (Philadelphia, PA)
Weikun Wang, NCSU (NC)
Adam Wilkerson, NCSU (NC)

Organizing committee: Prakash Belkale (UNC Chapel Hill), Gabor Pataki (UNC Chapel Hill), Robert Proctor (UNC Chapel Hill), Scott Provan (UNC Chapel Hill) and Richard Rimanyi (UNC Chapel Hill).