Discrete Mathematics Day At WPI

---

Schedule and Abstracts:

[Hide Abstracts]

• 9:00-9:50 am -- Light Breakfast, Salisbury Labs Lounge, Main Floor
• 9:50-10:00 am -- Welcome and Announcements
• 10:00-11:00 am -- Gretchen Matthews, Clemson University

Title: Analyzing codes defined by sparse matrices
Abstract: A linear code is often represented as the null space of a matrix; equivalently, it may be represented as a bipartite graph, called a Tanner graph. The performance of the code when coupled with an iterative decoding algorithm depends on its graphical representation. Low-density parity-check (LDPC) codes, which are defined by sparse graphs, have received much attention over the past decade due to the fact that they are capacity acheiving when paired with iterative message-passing decoding algorithms. One drawback of these decoding algorithms is that they may produce noncodeword outputs, loosely called pseudocodewords. In this talk, we discuss combinatorial and algebraic tools for studying pseudocodewords.

• 11:15 am - 12:15 pm -- Sara Billey, University of Washington

Title: On the enumeration of tanglegrams and tangled chains
Abstract: Tanglegrams are a special class of graphs appearing in applications concerning cospeciation and coevolution in biology and computer science. They are formed by identifying the leaves of two rooted binary trees. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched vertices, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This includes a new formula for the number of binary trees with n leaves. We also give a conjecture for the expected number of cherries in a large randomly chosen binary tree and an extension of this conjecture to other types of trees.

• 12:30-1:30 pm -- Lunch and Discussion, Higgins House
• 1:30-2:30 pm -- Steve Butler, Iowa State University

Title: An introduction to the normalized Laplacian matrix
Abstract: Spectral graph theory looks at the interplay between the structure of graphs and the eigenvalues associated with some particular matrix. Different matrices give different information, so it is important to understand how the different matrices behave, and which matrix to use for which types of problems. We will give an introduction to one of the lesser known matrices, the normalized Laplacian matrix, which has ties to the probability transition matrix of a random walk. This matrix is useful in many settings, particularly for graphs which are not regular, but also has some strange quirks which will be discussed (including not being able to give the number of edges in a graph).

• 2:30-3:30 pm -- Dominique Guillot, Stanford University/University of Delaware

Title: Critical exponents of graphs
Abstract: Given a positive semidefinite matrix A and a real number p, the p-th entrywise power of A is obtained by taking the p-th power of each entry of A. Whether or not the resulting matrix is positive semidefinite is a non-trivial problem solved in 1977 by FitzGerald and Horn. As they show, all powers above a certain "critical exponent" preserve positivity, whereas smaller non-integer powers do not. Motivated by applications in statistics, we examine when powering-up matrices having a given structure of zeros preserves positivity. The structure of zeros is naturally encoded by an undirected graph. We thus examine how the structure of the graph influences the set of powers that preserve positivity. I will discuss the history of the problem, present new results that characterize the powers preserving positivity for decomposable graphs, and discuss extensions and applications to high-dimensional statistics.

Joint work with Apoorva Khare (Stanford) and Bala Rajaratnam (Stanford)

• 3:30-4:00 pm -- Coffee Break
• 4:00-5:00 pm -- Margaret Readdy, University of Kentucky

Title: q-Combinatorics: A new view
Abstract: The idea of q-analogues can be traced back to Euler in the 1700's who was studying q-series, especially specializations of theta functions. Recall a q-analogue is a method to enumerate a set of objects by keeping track of its mathematical structure. For example, a combinatorial interpretation of the q-analogue of the Gaussian polynomial due to MacMahon in 1916 is given by summing over all 0-1 bit strings consisting of n-k zeroes and k ones the statistic q to the inversion number. Setting q=1 returns to the familiar binomial coefficient. After reviewing some q-analogues, we show the classical q-Stirling number of the second kind can be expressed more compactly as a polynomial in q and 1 + q. We then extend this enumerative result via a decomposition of a new poset whose rank generating function is the q-Stirling number S_q[n,k]. We call this poset the Stirling poset of the second kind. This poset supports an algebraic complex and a basis for integer homology is determined. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind will also be presented, as well as a new proof of orthogonality of the (q,t)-Stirling numbers of the first and second kind.

This is joint work with Yue Cai.

• 6:00-8:00 pm -- Reception and Dinner (free to all conference participants)

---