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