
Discrete Mathematics Day At WPISaturday, September 10, 2005Worcester Polytechnic Institute

Schedule and Abstracts:
 9:159:50 am  Light Breakfast, WPI Campus Center Main Floor
 9:5010:00 am  Welcome
 10:0010:40 am  Gabor Sarkozy, Worcester Polytechnic Institute
Title: New coloring applications of the Regularity Lemma
Abstract: The Regularity LemmaBlowup Lemma method has been quite successful for extremal graph theoretical problems. In this talk we present new applications of the method for certain graph coloring problems. Among other results by proving an old conjecture of Faudree and Schelp we determine the exact threecolor Ramsey numbers for paths. This is joint work with Andras Gyarfas, Miklos Ruszinko and Endre Szemeredi. 10:4011:00 am  Coffee Break
 11:00 am  noon  Richard Stanley, Massachusetts Institute of Technology
Title: Increasing and Decreasing Subsequences
Abstract: The talk will be a survey of some recent work on increasing and decreasing subsequences of permutations and related objects. Topics will include the enumeration of permutations with longest increasing and decreasing subsequences of specified lengths, connections with the RSK algorithm, asymptotic and probabilistic results of LoganShepp, VershikKerov, and BaikDeiftJohansson, and extensions to involutions and matchings. 12:002:00 pm  Lunch and Discussion Break
 2:003:00 pm  Chris Godsil, University of Waterloo
Title: TypeII Matrices
Abstract: If A and B are mx n complex matrices, their Schur product A ° B is the entrywise product of A and B, that is, it is the mxn matrix with
(A ° B)_{i,j} = A_{i,j} B_{i,j}.
The allones matrix J is the identity for this product. If no entry of A is zero, there is a unique matrix A^{()} such that
A ° A^{()} =J;
we call A^{()} the Schur inverse of A. If A is vxv, we say that A is a typeII matrix if
A A^{()T} =v I
(where A^{()T} is the transpose of A^{()}). Hence if A is type II, then A^{1}=(1/v) A^{()T}, which is easily computed, and so these matrices might be viewed as a gift to students in linear algebra courses. However the real reason we are interested in them is that certain typeII matrices were used by Vaughan Jones to construct socalled spin models, which provide useful invariants of links and knots. In my talk I will show how typeII matrices arise in connection with a number of interesting combinatorial and geometric problems, and hence are comparatively common. I will also develop some of their theory, which leads to the surprising conclusion that finding new spin models is a graphtheoretical problem. 3:003:30 pm  Coffee Break
 3:304:10 pm  Nancy Eaton, University of Rhode Island
Title: Graphs representable by Caterpillars
Abstract: We say a graph G is representable by a host tree T with tolerance t if there exists an assignment, { S_{u} : u ε V(G) }, of subtrees of T to the vertices of G such that  V(S_{u}) ∩ V(S_{v})  ≠ Ø ↔ {u,v} ε E(G). Graphs representable by paths have been characterized by Lekkerkerker and Boland. In this talk, we present a Lekkerkerker and Boland type characterization of graphs representable by caterpillars under certain conditions on the maximum degree of the caterpillar and tolerance of the representation. This is joint work with Glenn Faubert. 4:154:55 pm  Mark Skandera, Haverford College
Title:On the nonnegativity properties of the dual canonical basis
Abstract: Lusztig showed that all polynomials p(x_{1,1}, . . . ,x_{n,n}) in the dual canonical basis satisfy p(A) ≥ 0 for every totally nonnegative matrix A = (a_{i,j}). It is also possible to show that the evaluation of these polynomials at JacobiTrudi matrices yields Schurnonnegative symmetric functions. We will discuss variations of these properties and their connection to Schubert varieties and cluster algebras. 5:00 pm  Meeting Ends
Return to Discrete Math Day page at WPI.