Mathematics Dept.
  Events
Ethan White
UBC
Tue 23 Oct 2018, 4:00pm
Discrete Math Seminar
ESB 4127
The Triangle-Free Process
ESB 4127
Tue 23 Oct 2018, 4:00pm-5:00pm

Abstract

This is the first part of a two part exposition on the triangle-process. The triangle-free process begins on an empty graph and adds edges at random, provided no triangle is created with the existing edges. One of the original motivations for the process came from Ramsey Theory. Spencer conjectured that the maximum size of an independent set in a graph resulting from the process should be relatively small, and so the triangle-free process would provide constructions for lower bounds on the Ramsey number R(3,t). Recently, Bohman and Keevash obtained new estimates on independence number of such graphs, which gives a lower bound on R(3,t) within a factor of 4+o(1) of the best know upper bound. 

In this first part we will introduce random graph processes with an emphasis on the triangle-free process and the odd-cycle-free process.



hide
University of Southern California
Tue 6 Nov 2018, 4:00pm
Discrete Math Seminar
ESB 4127
Inversions for reduced words
ESB 4127
Tue 6 Nov 2018, 4:00pm-5:00pm

Abstract

The number of inversions of a permutation is an important statistic that arises in many contexts, including as the minimum number of simple transpositions needed to express the permutation and, equivalently, as the rank function for weak Bruhat order on the symmetric group. In this talk, I’ll describe an analogous statistic on the reduced expressions for a given permutation that turns the Coxeter graph for a permutation into a ranked poset with unique maximal element. This statistic simplifies greatly when shifting our paradigm from reduced expressions to balanced tableaux, and I’ll use this simplification to give an elementary proof computing the diameter of the Coxeter graph for the long permutation.
 
This talk is elementary and assumes no background other than passing familiarity with the symmetric group. 
hide
Purdue University
Tue 20 Nov 2018, 4:00pm
Discrete Math Seminar
ESB 4127
TBD
ESB 4127
Tue 20 Nov 2018, 4:00pm-5:00pm

Abstract

 
hide