Discrete Mathematics Day At WPI

---

Schedule and Abstracts:

• 9:15-9:50 am -- Light Breakfast, WPI Campus Center Main Floor
• 9:50-10:00 am -- Welcome
• 10:00-10:40 am -- Gabor Sarkozy, Worcester Polytechnic Institute

Title: New coloring applications of the Regularity Lemma
Abstract: The Regularity Lemma-Blow-up 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 three-color Ramsey numbers for paths. This is joint work with Andras Gyarfas, Miklos Ruszinko and Endre Szemeredi.

• 10:40-11: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 Logan-Shepp, Vershik-Kerov, and Baik-Deift-Johansson, and extensions to involutions and matchings.

• 12:00-2:00 pm -- Lunch and Discussion Break
• 2:00-3:00 pm -- Chris Godsil, University of Waterloo

Title: Type-II 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 all-ones 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 type-II 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 type-II matrices were used by Vaughan Jones to construct so-called spin models, which provide useful invariants of links and knots. In my talk I will show how type-II 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 graph-theoretical problem.

• 3:00-3:30 pm -- Coffee Break
• 3:30-4: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:15-4: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 Jacobi-Trudi matrices yields Schur-nonnegative symmetric functions. We will discuss variations of these properties and their connection to Schubert varieties and cluster algebras.

• 5:00 pm -- Meeting Ends

---