Fall 2016
Triangle Lectures in Combinatorics (TLC)
Fourteenth 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 plhersh@ncsu.edu (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.
Participants:
Elie Alhajjar (George Mason U.)
Edward Allen (Wake Forest U.)
Jordan Almeter (NCSU)
Noufe Aloudah (NCSU)
Bruno Benedetti (U Miami)
Daniel Bernstein (NCSU)
Alex Chandler (NCSU)
Maria Chudnovsky (Princeton)
Helen Cleaves (NCSU)
Jane Coons (NCSU)
Mark Ellingham (Vanderbilt)
Alperen Ergur
He Guo (Georgia Tech)
Josh Hallam (Wake Forest U.)
Gabor Hetyei (UNC Charlotte)
Ben Hollering (NCSU)
Chetak Hossain (NCSU)
Jeff Lagarias (U Michigan)
David Lax (Virginia Tech)
Ricky Liu (NCSU)
Sarah Mason (Wake Forest U.)
Emily Meehan (NCSU)
Michael Mossinghoff (Davidson)
Wesley Nelson (NCSU)
David Papp (NCSU)
Gabor Pataki (UNC Chapel Hill)
Ian Philipp (UNC Chapel Hill)
Shira Polster (NCSU)
Rodney Reid
Radmila Sazdanovic (NCSU)
Georgy Scholten (NCSU)
Dan Scofield (NCSU)
Michael Singer (NCSU)
Grace Stadnyk (NCSU)
Caprice Stanley (NCSU)
Michael Strayer (UNC, Chapel Hill)
Seth Sullivant (NCSU)
Matt Superdock (Charles E. Jordan H.S.)
Valerie Taylor (NCSU)
Ryan Vinroot (College of William and Mary)
Cynthia Vinzant (NCSU)
Charles Wang (Georgia Tech)
Stephanie Webster (Wake Forest U)
Anila Yadavalli (NCSU)
Sercan Yildiz (UNC, Chapel Hill)
Josephine Yu (Georgia Tech)
Talk Titles and Abstracts:
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.)
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.
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.