
Discrete Mathematics Day At WPISaturday, September 12, 2015Worcester Polytechnic Institute

Schedule and Abstracts:
[Hide Abstracts]
 9:009:50 am  Light Breakfast, Salisbury Labs Lounge, Main Floor
 9:5010:00 am  Welcome and Announcements
 10:0011: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. Lowdensity paritycheck (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 messagepassing 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:301:30 pm  Lunch and Discussion, Higgins House
 1:302: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:303: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 pth entrywise power of A is obtained by taking the pth power of each entry of A. Whether or not the resulting matrix is positive semidefinite is a nontrivial problem solved in 1977 by FitzGerald and Horn. As they show, all powers above a certain "critical exponent" preserve positivity, whereas smaller noninteger powers do not. Motivated by applications in statistics, we examine when poweringup 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 highdimensional statistics.Joint work with Apoorva Khare (Stanford) and Bala Rajaratnam (Stanford)
 3:304:00 pm  Coffee Break
 4:005:00 pm  Margaret Readdy, University of Kentucky
Title: qCombinatorics: A new view
Abstract: The idea of qanalogues can be traced back to Euler in the 1700's who was studying qseries, especially specializations of theta functions. Recall a qanalogue is a method to enumerate a set of objects by keeping track of its mathematical structure. For example, a combinatorial interpretation of the qanalogue of the Gaussian polynomial due to MacMahon in 1916 is given by summing over all 01 bit strings consisting of nk zeroes and k ones the statistic q to the inversion number. Setting q=1 returns to the familiar binomial coefficient. After reviewing some qanalogues, we show the classical qStirling 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 qStirling 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 qStirling 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:008:00 pm  Reception and Dinner (free to all conference participants)
Return to Discrete Math Day page at WPI.