Triangle Lectures in Combinatorics (TLC)

Nineteenth meeting: Saturday, February 29, 2020
Location: UNC Charlotte
Room: Fretwell 100

Speakers: Margaret Bayer (U Kansas), Michel Goemans (MIT), Svetlana Poznanović (Clemson), Cynthia Vinzant (NCSU)

Organizing Committee: Gabor Hetyei (UNC Charlotte), Ricky Liu (NCSU), Gabor Pataki (UNC Chapel Hill)

Conference schedule

9:15-10am, coffee and light breakfast
10-11am, Margaret Bayer, Counting flags in Eulerian posets: The cd-index (slides)
11-11:30am, coffee break
11:30am-12:30pm, Michel Goemans, Semidefinite Programming Relaxation of MAXCUT: A Survey
12:30-2:30pm, lunch break (suggestions)
2:30-3:30pm, Svetlana Poznanović, Hecke insertion and maximal increasing and decreasing sequences in fillings of polyominoes (slides)
3:30-4pm, coffee break
4-5pm, Cynthia Vinzant*, Matroids, log-concavity, and expanders
6pm, informal conference dinner at Godavari

*Unfortunately, Bruce Sagan, who was originally scheduled, had to cancel due to illness.

Hotel: We have a block of rooms at Drury Inn that is available until January 27.

Parking: There is free parking on campus near Fretwell in the East Deck and Lot 5. (Campus map)

Airport: Charlotte Douglas International Airport is 20-30 minutes drive from UNC Charlotte. Taxi fare is about $30.

Registration and funding applications:
To register and/or apply for funding, please fill out this form.

We are asking that participants preregister if possible, as preregistration is very helpful for planning our coffee breaks and obtaining funding to support these meetings. We have some funding available for some participants, especially for early-career participants. Most of this is restricted to US citizens and permanent residents, and what is available to others still requires that the participants be employed at a U.S. university. You will have the opportunity to apply for funding when registering for the conference.

---

Participants:
Edward Allen (Wake Forest University)
Jordan Almeter (NCSU)
Sarah Baker (Actuarial Science Club-UNCC)
Margaret Bayer (U Kansas)
Sarah Birdsong (UNC Charlotte)
Michael Blackmon (Davidson)
Mark Bly (Coastal Carolina University)
Cash Bortner (NCSU)
Chung Chan (UNCC)
Jane Coons (NC State University)
Joseph Cummings (University of Kentucky)
Caitlin Gilman (UNC Charlotte)
Michel Goemans (MIT)
William Gustafson (University of Kentucky)
Derek Hanely (University of Kentucky)
Gabor Hetyei (UNC Charlotte)
Ben Hollering (North Carolina State University)
Joe Johnson (NCSU)
Ricky Liu (North Carolina State University)
Molly Lynch (Hollins University)
Sarah Mason (Wake Forest University)
Geoff McKenna
Walter Morris (George Mason University)
Gabor Pataki (UNC Chapel Hill)
Hannah Powell (UNCC)
Svetlana Poznanović (Clemson)
Katherine Riley (Wake Forest University)
Georgy Scholten (NCSU)
Grace Stadnyk (Furman University)
Ashley Tharp (NCSU)
Cynthia Vinzant (NCSU)
Matias von Bell (University of Kentucky)
Evan Wantland (UNC Charlotte)
Michael Weselcouch (Wake Forest University)
Kejun Zhang (UNC Charlotte)
Yuzixuan Zhu (University of North Carolina at Chapel Hill)
Yan Zhuang (Davidson College)

---

Talk titles and abstracts:

Margaret Bayer (U Kansas)

Title: Counting flags in Eulerian posets: The cd-index

The face lattices of convex polytopes and intervals in the Bruhat order of Coxeter groups are examples of Eulerian posets. The flag vector of an Eulerian poset counts the sequences of elements of specified ranks. The linear relations that hold for the flag vectors of all Eulerian posets are known, and it turns out the dimension of the flag vectors for posets of fixed rank is a number in the Fibonacci sequence. Jonathan Fine discovered that the flag vectors could be efficiently coded in a vector called the cd-index. This talk discusses the history of the cd-index, with a focus on inequalities, connections with other combinatorial parameters and relations to algebraic structures.

Michel Goemans (MIT)

Title: Semidefinite Programming Relaxation of MAXCUT: A Survey

I will discuss the semidefinite programming relaxation of the maximum cut problem in graphs and the random hyperplane rounding scheme, proposed together with David Williamson over 25 years ago. The talk will cover several extreme classes of instances involving geometry and spectral graph theory, their connections to inapproximability and social choice theory, and a novel, alternate rounding scheme.

Svetlana Poznanović (Clemson)

Title: Hecke insertion and maximal increasing and decreasing sequences in fillings of polyominoes

In this talk we will give a proof that the number of 01-fillings of a given stack polyomino (a polyomino with justified rows whose lengths form a unimodal sequence) with at most one 1 per column which do not contain a fixed-size northeast chain and a fixed-size southeast chain, depends only on the set of row lengths of the polyomino. The proof is via a bijection between fillings of stack polyominoes which differ only in the position of one row and uses Hecke insertion and jeu de taquin for increasing tableaux. We will also survey how this work relates to other results about chains in fillings of polyominoes as well as graphs and set partitions and discuss some possible and impossible extensions.

Cynthia Vinzant (NCSU)

Title: Matroids, log-concavity, and expanders

Matroids are combinatorial objects that model various types of independence. They appear several fields mathematics, including graph theory, combinatorial optimization, and algebraic geometry. In this talk, I will introduce the theory of matroids along with the closely related class of polynomials called strongly log-concave polynomials. Strong log-concavity is a functional property of a real multivariate polynomial that translates to useful conditions on its coefficients. Discrete probability distributions defined by these coefficients inherit several of these nice properties. I will discuss the beautiful real and combinatorial geometry underlying these polynomials and describe applications to random walks on the faces of simplicial complexes. Consequences include proofs of Mason's conjecture that the sequence of numbers of independent sets of a matroid is ultra log-concave and the Mihail-Vazirani conjecture that the basis exchange graph of a matroid has expansion at least one. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.