Triangle Lectures in Combinatorics (TLC)

These are a series of combinatorial workshops, held once per semester, each on a Saturday. The series began with its first meeting in spring 2010. They rotate among the universities in and around the Research Triangle. Participants come from numerous colleges and universities within a few hours drive, and some from even farther away. These workshops are funded by the National Science Foundation and the National Security Agency, in particular enabling us to bring in four exciting speakers to give one hour talks each time as well as funding travel expenses for participants.

TLC steering committee: Patricia Hersh (NCSU), Ezra Miller (Duke), Gabor Pataki (UNC Chapel Hill), Nathan Reading(NCSU), Seth Sullivant (NCSU), and Cynthia Vinzant (NCSU).

Upcoming meeting: Saturday November 19, 2016, 9:15am - 5pm
Location: North Carolina State University, Raleigh
Lecture Hall: SAS Room 2203

Speakers: Bruno Benedetti (U. Miami), Maria Chudnovsky (Princeton), Jeffery Lagarias (U. Michigan), Josephine Yu (Georgia Tech),

Preregistration: please send email to (Patricia Hersh) to preregister. This is very helpful in our planning how much coffee, etc. to have at coffee breaks and for our obtaining funding to support these meetings.

Participant Travel Expense Reimbursement: we have some funding available for some participants, especially for early-career participants. Most of this is restricted to U.S. citizens, and what is available to others still requires that the participants be employed at a U.S. university. To request funding please fill out the form here.

Local organizing committee: Ricky Liu (NCSU), Seth Sullivant (NCSU), and Cynthia Vinzant (NCSU)

Saturday Triangle Lectures in Combinatorics Schedule:

9:15-10am, coffee and small breakfast
10-11am, Maria Chudnovsky, Coloring graphs without long induced paths
11-11:30am, coffee break
11:30am-12:30pm, Bruno Benedetti, Diameter and connectivity of polytope graphs
12:30-2:30pm, lunch break
2:30-3:30pm, Josephine Yu, Some Applications of Polyhedral Combinatorics
3:30-4pm, coffee break
4-5pm, Jeff Lagarias, Polynomial Splitting Measures and Cohomology of the Pure Braid Group
5:30pm, somewhat informal conference dinner at David's Dumpling and Noodle Bar, a short walk from SAS Hall.

Practical details:

Parking: You may park right outside SAS Hall for free. Here is a map of the campus. 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 upper right of the map, and the parking lot is near the intersection of Stinson Drive and Boney Dr. A good back-up option for parking is the Coliseum Parking Deck.

The room: SAS Room 2203 is up one flight of stairs and to the left when you enter from the parking lot. If you enter from the courtyard side, it is to the right on the same floor.

Hotel recommendations: within short walk of the math department are several hotels, including the Doubletree by Hilton Raleigh - Brownstone (919-828-0811) and Aloft Raleigh (919-828-9900). About 1.5 miles away in downtown Raleigh (also walkable, but somewhat long walk) is the Clarion Raleigh Hotel (919-832-0501). Those with cars might also consider hotels farther away such as Holiday Inn Express (919-854-0001) 3741 Thistledown Drive (near Centennial Campus) as well as various hotel choices on Wake Town Drive, which is near numerous good restaurants; some such hotels (all right next to each other on Wake Towne Drive) are Marriott Courtyard (919-821-3400), Hampton Inn (919-828-1813), or Extended Stay America (919-829-7271).

Airport: Raleigh-Durham International Airport is 20-30 minutes drive from NCSU. Taxi fare is about $30.

Preregistered Participants (so far):

Jordan Almeter (NCSU)
Bruno Benedetti (U Miami)
Maria Chudnovsky (Princeton)
Mark Ellingham (Vanderbilt)
He Guo (Georgia Tech)
Kendrick Hardison (Francis Marion U)
Patricia Hersh (NCSU)
Chetak Hossain (NCSU)
Jeff Lagarias (U Michigan)
Ricky Liu (NCSU)
Sarah Mason (Wake Forest U.)
Michael Mossinghoff (Davidson)
David Papp (NCSU)
Felix Reidl (NCSU)
Georgy Scholten (NCSU)
Michael Singer (NCSU)
Grace Stadnyk (NCSU)
Michael Strayer (UNC, Chapel Hill)
Seth Sullivant (NCSU)
Matt Superdock (Charles E. Jordan H.S.)
Ryan Vinroot (College of William and Mary)
Cynthia Vinzant (NCSU)
Charles Wang (Georgia Tech)
Russ Woodroofe (Mississippi State U)
Sercan Yildiz (UNC, Chapel Hill)
Josephine Yu (Georgia Tech)

Talk Titles and Abstracts:

Bruno Benedetti (U. Miami)

Title: Diameter and connectivity of polytope graphs

Abstract:A standard result in discrete geometry is Balinski's theorem, "the graph of every convex d-dimensional polytope is d-connected". But given a d-dimensional polytope with n facets, how many edges do we have to walk along (at most), if we want to go from a vertex to another? Hirsch's old conjecture that the answer be "at most n-d" was disproved by Santos in 2010. I will sketch two recent positive results:

1. The Hirsch conjecture holds for all flag polytopes. The proof uses ideas from differential geometry. (Joint work with K. Adiprasito.)

2. The notion of dual graph naturally lifts to projective varieties, where a broader version of Balinski's theorem still holds. This explain certain regularity phenomena of arrangements of lines in smooth surfaces. (This is ongoing joint work with M. Varbaro, B. Bolognese, M. Di Marca.)

Maria Chudnovsky (Princeton)

Title: Coloring graphs without long induced paths

Abstract: It is an open question whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices. Over the last few years progress has been made on this question for small values of t, and also on its approximate version. In this talk we will survey what has been done so far, and discuss the most recent polynomial time algorithm that, given a 3-colorable graph with no induced t-vertex path, constructs a coloring with at most max(5, t-2) colors. This result can also be stated as a polynomial time algorithm that given a graph G with no induced path of length t either determines that G is not 3-colorable, or outputs a coloring with at most max(5, t-2) colors. This approximation result is joint work with Oliver Schaudt, Sophie Spirkl, Maya Stein, and Mingxian Zhong.

Jeffrey C. Lagarias (U. Michigan)

Title: Polynomial Splitting Measures and Cohomology of the Pure Braid Group

Abstract: This talk starts with a number theory problem concerning splitting probabilities for factorizations of monic degree-n polynomials over p-adic fields, conditioned on having square-free factorization type. In work with Ben L. Weiss (U. Maine-Orono) we showed these probabilities viewed as a function of p (for fixed splitting type) interpolate as rational functions of z, which are Laurent polynomials. Identifying splitting types with conjugacy classes of the symmetric group Sn allows these probabilities to be viewed as class functions on Sn. The speaker later studied the case p=1, the "field with one element", observing the measure values have an interesting multiplicative arithmetical structure, and (after rescaling) discoved them to be the character of an interesting virtual representation of Sn having small support. Subsequent work with Trevor Hyde (U. Michigan) showed the individual Laurent coefficients when rescaled are characters of (virtual) representations of the symmetric group Sn, arising from part of the cohomology of the pure braid group, viewed as an Sn-module. We discuss some consequences of this identification.

Josephine Yu (Georgia Tech)

Title: Some Applications of Polyhedral Combinatorics

Abstract:We will discuss two different applications of polyhedral geometry --- for finding the competitive equilibrium in the product-mix auctions of indivisible goods, and for learning Bayesian networks from observational data. The combinatorial ingredients include triangulations, unimodular systems, permutohedra, submodular functions, and ideas from tropical geometry and discrete convex analysis.

Past meetings:

Thirteenth meeting: Saturday February 27, 2016 at UNC Greensboro
Speakers: Penny Haxell (U. Waterloo), Jeff Kahn (Rutgers), Greta Panova (U. Penn), Peter Winkler (Dartmouth).
Organizing Committee: Clifford Smyth, chair (UNC Greensboro), David Galvin (Notre Dame), and Patricia Hersh (NCSU).
More information

Twelfth meeting: Saturday October 3, 2015 at Duke
Speakers: Yuliy Baryshnikov (UIUC), Susan Holmes (Stanford), Dana Randall (Georgia Tech), and John Shareshian (Washington University in St. Louis).
Organizing Committee: Sayan Mukherjee, chair (Duke), John Harer (Duke), Patricia Hersh (NCSU), and Mauro Maggioni (Duke)
More information

Eleventh meeting: February 21, 2015 at NCSU
Speakers: Matthew Baker (Georgia Tech), Henry Cohn (Microsoft New England), Lionel Levine (Cornell), and Anne Schilling (UC Davis).
Organizing Committee: Ricky Liu (NCSU), Seth Sullivant (NCSU), and Cynthia Vinzant (NCSU)
More information

Tenth meeting: October 4, 2014, at High Point University
Speakers: Richard Ehrenborg (Kentucky), Robert Ghrist (Penn), Luis Serrano (U Quebec a Montreal), and Rekha Thomas (U. Washington).
Organizing Committee: Lindsay Piechnik (chair, High Point), Ed Allen (Wake Forest), Sarah Mason (Wake Forest), Seth Sullivant (NCSU), and Laurie Zack (High Point)
More information

Ninth meeting: February 22, 2014 at UNC-Chapel Hill.
Speakers: Shankar Bhamidi (UNC-Chapel Hill), Anders Buch (Rutgers), Pablo Parrilo (MIT), Eva Tardos (Cornell)
Organizing committee: Gabor Pataki (UNC-Chapel Hill), Lindsay Piechnik (High Point University), Scott Provan (UNC-Chapel Hill), Richard Rimanyi (UNC-Chapel Hill), Jack Snoeyink (UNC-Chapel Hill)
More information

Eighth meeting: September 21, 2013 at NCSU.
Speakers: George Andrews (Penn State), Matt Beck (San Francisco State University), Robin Pemantle (University of Pennsylvania), and Victoria Powers (Emory University)
Organizing committee: Michael Singer (NCSU), Carla Savage (NCSU), and Seth Sullivant (NCSU)
More information

Seventh meeting: February 9, 2013 at Wake Forest University.
Speakers: Louis Billera (Cornell), Rod Canfield (University of Georgia), Matthew Kahle (Ohio State University), Michelle Wachs (University of Miami)
Organizing committee: Sarah Mason (chair, Wake Forest University), Ed Allen (Wake Forest University), Alex Fink (NCSU), Patricia Hersh (NCSU)
More information

Sixth meeting: September 22, 2012 at NCSU.
Speakers: Allen Knutson (Cornell), Vin de Silva (Pomona College), Richard Stanley (MIT), Lauren Williams (UC Berkeley).
Organizing committee: Alex Fink (NCSU), Patricia Hersh (NCSU), Carla Savage (NCSU).
More information

Fifth meeting: February 11, 2012 at Duke University.
Speakers: Alex Fink (NCSU), Sergey Fomin (Michigan), Nets Katz (Indiana University), Isabella Novik (University of Washington).
Organizing Committee: Christine Berkesch (Duke), Sonja Mapes (Duke), Ezra Miller (Duke).
More information

Fourth meeting: November 5, 2011 at UNC Chapel Hill.
Speakers: Thomas Lam (Michigan), Jesus De Loera (UC Davis), Ezra Miller (Duke), Doron Zeilberger (Rutgers)
Organizing committee: Prakash Belkale (UNC Chapel Hill), Gabor Pataki (UNC Chapel Hill), Robert Proctor (UNC Chapel Hill), Scott Provan (UNC Chapel Hill), Richard Rimanyi (UNC Chapel Hill).
More information

Third meeting: April 9, 2011 at NCSU.
Speakers: Prakash Belkale (UNC Chapel Hill), Vic Reiner (University of Minnesota), John Stembridge (University of Michigan), Stephanie van Willigenburg (UBC).
Organizing committee: Hoda Bidkhori (NCSU), Alex Fink (NCSU), Patricia Hersh (NCSU), Carla Savage (NCSU).
More information

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 NCSU.
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