Triangle Lectures in Combinatorics (TLC)

Ninth meeting: February 22, 2014

Location: UNC Chapel Hill

Lecture Hall: Sitterson Hall 014 MAP

Speakers: Shankar Bhamidi (UNC-Chapel Hill), Anders Buch (Rutgers), Pablo Parrilo (MIT), Eva Tardos (Cornell)

Preregistration: please send email to Patricia Hersh (plhersh@ncsu.edu) 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.

Friday Seminar Talks Preceding TLC:

2-3pm, Gabor Hetyei, ``Bernoulli type games and enumeration by kernel positions'', NCSU Algebra and Combinatorics Seminar, SAS 4201
4-5pm, Anders Buch, ``Quantum K-Theory'', UNC Chapel Hill Geometric Methods in Representation Theory Seminar, Phillipps Hall 367

Saturday Triangle Lectures in Combinatorics Schedule:

9:15-10am, coffee and bagels
10-11am, Shankar Bhamidi, Limited choice and randomness in the evolution of networks
11-11:30am, coffee break
11:30am-12:30pm, Eva Tardos, Auctions as games, learning, and the price of anarchy
12:30-2:30pm, lunch break
2:30-3:30pm, Anders Buch, Mutations of puzzles and equivariant cohomology of two-step flag varieties
3:30-4pm, coffee break
4-5pm, Pablo Parrilo, Convex sets, conic matrix factorizations and rank lower bounds
6pm, somewhat informal conference dinner at Talulla's Turkish Restaurant on Franklin Street in Chapel Hill.

Registration for conference dinner: Please send an email message to Gabor Pataki, gabor@unc.edu, if you plan to attend the dinner to help him collect a head count in advance.

Suggested hotels and parking information:

Preregistered participants:

Justin Allman, UNC Chapel Hill
Alessandro Arlotto, Duke
Spencer Backman, Georgia Tech
Daniel Bernstein, NCSU
Shankar Bhamidi, UNC Chapel Hill
Zane Blanton, UNC Chapel Hill
Daniel Brake, NCSU
Timothee Bryan, NCSU
Anders Buch, Rutgers
Noah Daleo, NCSU
Lola Davidson, U. Kentucky
Ruth Davidson, NCSU
Anahita Davoudi, University of Central Florida
Elizabeth Gross, NCSU
Ruth Haas, Smith College
Alex Happ, U. Kentucky
Jonathan Hauenstein, NCSU
Patricia Hersh, NCSU
Gabor Hetyei, UNC Charlotte
William Hill, NCSU Computer Science
Wesley Hough, U. Kentucky
Peter Humphries, North Carolina Central University
Garrett Johnson, The Catholic University of America
Stefanos Kechagias, UNC Chapel Hill
Mustafa Khandwawala, UNC Chapel Hill
Christopher Kirkland, NCSU
Florian Kohl, U. Kentucky
Darla Kremer
David Lax, UNC Chapel Hill
Alan Liddell, NCSU
Colby Long, NCSU
Shu Lu, UNC Chapel Hill
Emily Meehan, NCSU
Ezra Miller, Duke
Michael Mossinghoff, Davidson College
Sarah Nelson, U. Kentucky
Van Vinh Nguyen, Duke
Michael O'Brien, NCSU
Augustine O'Keefe, U. Kentucky
Chris O'Neill, Duke
Daniel Orr, Virginia Tech
Pablo Parrilo, MIT
Gabor Pataki, UNC Chapel Hill
Sasa Pekec, Duke
Lindsay Piechnik, High Point University
Bob Proctor, UNC Chapel Hill
Scott Provan, UNC Chapel Hill
Nathan Reading, NCSU
Richard Rimanyi, UNC Chapel Hill
Radmila Sazdanovic, NCSU
Jenny Shi, UNC Chapel Hill
Michael Singer, NCSU
Sean Skwerer, UNC Chapel Hill
Jack Snoeyink, UNC Chapel Hill
Matthew Stamps, KTH, Sweden
Shaler Stidham, Jr., UNC Chapel Hill
Blair Sullivan, NCSU
Seth Sullivant, NCSU
Eva Tardos, Cornell
Clifford Taylor, U. Kentucky
Hayato Ushijima-Mwesigwa, Clemson
Tzvetalin Vassilev, Nipissing University (Ontario, Canada) and Durham
Jia (Jasmine) Wan, Randolph College
Xuan Wang, UNC Chapel Hill
James Wilson, UNC Chapel Hill
Dongqing Yu, UNC Chapel Hill
Haojin Zhai, UNC Chapel Hill


Talk titles and abstracts (received so far):


Shankar Bhamidi, UNC Chapel Hill

Title: Limited choice and randomness in the evolution of networks.

Abstract: The last few years have seen an explosion in network models describing the evolution of real world networks. In the context of math probability, one aspect which has seen an intense focus is the interplay between randomness and limited choice in the evolution of networks, ranging from the description of the emergence of the giant component, the new phenomenon of ``explosive percolation'' and power of two choices. I will describe ongoing work in understanding such dynamic network models, their connections to classical constructs such as the standard multiplicative coalescent and local weak convergence of random trees.


Anders Buch, Rutgers

Title: Mutations of puzzles and equivariant cohomology of two-step flag varieties

Abstract: I will speak about a mutation algorithm for puzzles that is a three-direction analogue of the classical jeu de taquin algorithm for semistandard tableaux. The main application of this algorithm is a proof of a conjectured formula for the equivariant Schubert structure constants of two-step flag varieties. This formula is positive in the sense of Graham and it generalizes both Knutson and Tao's equivariant puzzle rule for Grassmannians and the cohomological puzzle rule for two-step flag varieties. Thanks to the equivariant version of the `quantum equals classical' theorem, my formula also specializes to a Littlewood-Richardson rule for the equivariant quantum cohomology of Grassmannians.


Pablo Parrilo, MIT

Title: Convex sets, conic matrix factorizations and rank lower bounds

Abstract: In optimization one often represents convex sets in terms of convex cones. Such representations or 'lifts' of a convex set are especially useful if the cone admits efficient algorithms for linear optimization over its affine slices, as in the classical cases of linear and semidefinite programming. Despite the fact that these techniques are widely used, there are many aspects (particularly, existence and efficiency) that are still poorly understood. In this talk we discuss the relationship between conic representations of convex sets, and a special "conic" factorization of an operator associated to the convex set, generalizing earlier results of Yannakakis on polyhedral lifts of polytopes and nonnegative factorizations. When the cones live in a family, our results lead to the definition of the rank of a convex set with respect to this family (e.g., psd rank of a convex set), as well as techniques for lower bounding these ranks. We will provide a gentle introduction to these techniques, emphasizing geometric intuition, open questions as well as recent results. Based on joint work with Joao Gouveia, Hamza Fawzi, James Saunderson and Rekha Thomas.


Eva Tardos, Cornell

Title: Auctions as Games, Learning, and the Price of Anarchy

Abstract: Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by classical examples in game theory, such as the prisoner dilemma. Over the last decade, computer scientists and game theorists have developed good understanding how to quantify the impact of strategic user behavior on overall performance in many different environments, including selfish traffic routing.

In this talk, we will consider online auctions from this perspective. The Internet provides an environment running millions of auctions, an environment where simplicity is more important than perfect efficiency, and where the systems used do not satisfy the usual standards of mechanism design. We'll consider such auctions as games, and we show how to provide robust guarantees for their performance even when players participate in multiple auctions, have valuations that are complex functions of multiple outcomes, and are using learning strategies to deal with an uncertain environment. The talk will assume no previous background in game theory or auctions.


Conference 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)