Rocky Mountain Algebraic Combinatorics Seminar

Upcoming Seminars Schedule

On classes of permutations avoiding 231 or 321

Nik Ruskuc
University of St Andrews, UK

Let S denote the set of all finite permutations, considered as rearrangements of {1,...,n}, n=1,2,3,... Pattern involvement is a partial order on S. Of particular interest are downward closed sets under this ordering, usually called pattern classes. Such classes can be defined by specifying minimal forbidden permutations; we write Av12,...) to denote the pattern class consisting of all permutations avoiding π12,... Thus, for instance:

In this talk I will discuss the subclasses contained in Av(321) and Av(231). I will set the scene by outlining some superficial similarities: e.g. they are both enumerated by the Catalan numbers. Then I will point out some radical differences: e.g. Av(231) is well quasi ordered (it has no infinite antichains), while Av(321) is not. Most of the talk will be devoted to an explication of some less obvious, but deeper, similarities between the subclasses, to do with their enumeration sequences. The new results concerning the subclasses of Av(321) are a joint work with M. Albert, R. Brignall and V. Vatter.


Combinatorial Polytopes in Algebraic and Geometric Complexity Theory

Joshua Grochow
University of Colorado, Boulder

Beginning in the 1960s with the rise of efficient algorithms for Linear Programming, polytopes have played an important role in computational complexity. The past 5 years have witnessed a surge of lower bound methods for and based on polytopes. In addition to discussing some of this history and the more general role of polytopes in complexity, we'll discuss two recent results: (1) (joint with K. Mulmuley and Y. Qiao) a use of polytopes in helping understand the geometric complexity theory approach to VP vs VNP (an algebraic analogue of P vs NP) and (2) how lower bounds on the extension complexity of polytopes imply monotone algebraic circuit lower bounds.


Weber 223
4–6 pm
Friday, March 2, 2018
(Refreshments in Weber 117, 3:30–4 pm)
Colorado State University

This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly. Anyone interested is welcome to join us at a local restaurant for dinner after the talks.

PDF version

Previous Seminars:

February 16, 2018
Hamidreza Chitsaz, Mark Lewis
February 2, 2018
James B. Wilson, Anton Betten
November 10, 2017
Michael Kinyon, Petr Vojt\v{e}chovsk\'y
October 20, 2017
Eric Moorhouse, William DeMeo
October 6, 2017
Spencer Gerhardt, Joshua Grochow
September 22, 2017
Amanda Schaeffer Fry, Henry Kvinge
September 8, 2017
Peter Mayr, James B. Wilson
May 5, 2017
Ferdinand Ihringer, Gavin King
April 21, 2017
Vladimir D. Tonchev, Morgan Rodgers
April 7, 2017
Jason Williford, Anton Betten
March 24, 2017
Isabella Novik, Peter Brooksbank
March 3, 2017
Jintai Ding, Curtis Bennett
February 17, 2017
Fatma Karaoglu, Eric Moorhouse
February 3, 2017
Tim Penttila, James B. Wilson
December 2, 2016
Jim Fowler, Andrew Kelley
November 11, 2016
Joseph Gersch, Joshua Maglione
October 28, 2016
John MacLaren Walsh, Henry Adams
October 14, 2016
JM Landsberg, James B. Wilson
September 30, 2016
Alexander Hulpke, Oscar Levin
September 16, 2016
Delaram Kahrobaei, Amit Patel
June 23, 2016
Jason Cantarella, Michal Adamaszek
April 29, 2016
Nick Loehr, Jason Williford
April 15, 2016
Alexander Hulpke, Klaus Lux
April 1, 2016
Eamonn O'Brien, Izabella Stuhl
February 19, 2015
James Wilson, Anton Betten
December 4, 2015
Maria Monks Gillespie, Dane Flannery
November 13, 2015
Richard Green, Tim Penttila
October 23, 2015
Christina Boucher, Sylvia Hobart
October 9, 2015
Josh Maglione, Ghodratollah Aalipour
September 25, 2015
Ross McConnell, Henry Adams
September 11, 2015
James B. Wilson, Tim Penttila
May 8, 2015
Amanda Schaeffer Fry, Peter Brooksbank
April 24, 2015
Heide Gluesing-Luerssen, Phil DeOrsey
March 6, 2015
Felice Manganiello, Eric Moorhouse
February 20, 2015
Anton Dzhamay, Anton Betten
February 6, 2015
Alexander Hulpke, Morgan Rodgers
December 5, 2014
Stefaan De Winter, Gretchen Matthews
November 14, 2014
Greg Coxson, Tom Dorsey
October 31, 2014
Octavio Paez Osuna, Sylvia Hobart
October 10, 2014
Takunari Miyazaki, Eric Moorhouse
September 26, 2014
Elissa Ross, Anton Betten
September 12, 2014
Petr Vojtěchovský, Alexander Hulpke
May 9, 2014
Philip DeOrsey, Tim Penttila
April 25, 2014
William J Martin, Jason Williford
April 11, 2014
Victor Pambuccian, George Shakan
March 7, 2014
Nathan Lindzey, Jens Harlander
February 21, 2014
Ross McConnell, Anton Betten
November 22, 2013
Justin Hughes, Josh Maglione

Department of Mathematics
Fort Collins, Colorado 80523