2-D dynamical systems and the Road-coloring conjectureI am interested in the qualitative properties of 2-D dynamical systems of the form x(h,k)=Rx(h-1,k) + Bx(h,k-1), where R and B are n by n (entrywise) nonnegative matrices, h and k are integers with h+k nonnegative, and the x(h,k) are n by 1 vectors. The initial conditions are given by the x(h,k) for which x(h,-h)=0. These dynamical systems generalize Markov chains, and arise in modeling river flow and migratory populations. The qualitative properties of such a system can be determine by the associated 2-colored digraph D which consists of vertices 1,2,..., n, a red arc from i to j if and only if the (i,j)-entry of R is positive, and a blue are from i to j if and only if the (i,j)-entry of B is positive. Qualitative questions about the 2-D system are closely related to the (still open!) over 25 year-old road-coloring conjecture: if D is a primitive, 2-colored digraph such that each vertex is the initial vertex of a red arc and a blue arc, then there exists a word W in red and blue and a vertex v such that for each vertex w the walk that starts at w and follows arcs according to W ends at v.
Ranking problems
In many everyday instances, such as a daily list of chores, one is confronted with ordering a list according to a certain criteria. Such ordering problems also arise in science (e.g. chronologically ordering archaeological sites based on artifacts present; determining the ordering of small segments of a genome sequence; or an internet search engine ranking the hits for a given query). The goal of this line of research is to develop mathematical methods to attack such ranking problems, and to mathematically analyze known ranking methods.Algebraic Graph Theory
Graphs are used to model a wide variety of phenomena, ranging from ecological systems to river flow to the WWW network. A primary goal of algebraic graph theory is to understand the relationship between the combinatorial structure of a graph and the algebraic structure of associated matrices. For example, the eigenvalues of the Laplacian matrix of a graph are closely related to the interconnectedness of the graph. As the Laplacian can be viewed as a discrete version of the continuos Laplacian, in essence one is using discrete harmonic analysis to try to 'hear' the combinatorial properties of a graph.Arrangement problems
A wide variety of combinatorial problems concern the existence and construction of certain types of configurations. I continue to work on (t,m,s)-nets (which are point sets of the unit n-cube that are pseudo-randomly distributed), biclique partitions of graphs and extensions of the celebrated Witsenhausen-Graham-Pollak theorem, and uniform coverings of the n-cube by geodesic cycles.Qualitative Matrix Theory
The goal in this line of research is to determine properties of a matrix, a linear system, or a quadratic form, that are forced by the signs (i.e. positive, negative, zero) of the entries. This research has applications to economics, physics, and the social sciences.Orthogonal matrices
The underlying question in this line of research is: What are the combinatorial properties of orthogonal matrices? Specific examples of questions are: which sign patterns are the sign pattern of an orthogonal matrix?, for which sign patterns is the set of orthogonal matrices with given sign pattern a connected set? for which n does there exist an n by n matrix of 0s, 1s and -1s, whose rows are pairwise orthogonal and whose first row has all 1's? Hadamard's question: for which n does there exists an n by n matrix of 1s and -1s whose rows are pairwise orthogonal? Related applications are discrete wavelets, QR decomposition for sparse matrices, and statistical weighing designs.Counting Problems
Counting is an essential part of combinatorics. The permanent is a fundamental tool for counting, yet it is computational hard to compute. However, for certain matrices it is possible to convert the computation of the permanent into the easier computation of the determinant. Thus, some counting problems can be accomplished by using a determinant. Research continues on trying to convert harder counting problems into a small number of determinant calculations.