Mathematics
Seminar



Rocky Mountain Algebraic Combinatorics Seminar
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 Av(π_{1},π_{2},...) to denote the pattern
class consisting of all permutations avoiding π_{1},π_{2},... Thus, for
instance:
 Av(21) consists of all increasing permutations 12...n, n ∈ N;
 Av(321) consists of all permutations with no descending subsequences of length 3;
 Av(231) consists of all permutations that can be sorted by a stack.
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 GluesingLuerssen,
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
