Mathematics & Statistics Department

What is the minimum number of vertices needed to triangulate a surface of a bagel, i.e. represent it as a union of triangles where every two triangles must either be disjoint or intersect along a vertex or a common edge? What if we also require our triangulation to have a certain symmetry? What about higher-dimensional analogs of this question? More specifically, what is the minimum number of vertices needed to triangulate Sⁱ x S^j --- the product of two spheres? To triangulate it in a way that the resulting simplicial complex is ``centrally symmetric"? While the first question is still open (at least when i and j are sufficiently large), the second question turns out to have a surprisingly simple solution for all values of i and j. In this talk we will discuss this answer and the combinatorial construction that achieves it.

This is joint work with Steve Klee.

Reed mathematics majors discuss their summer research.

I. Pattern Avoidance in Permutations on Partially Ordered Sets, Sam Hopkins

Abstract: We extend the concept of pattern avoidance in permutations on a totally ordered set to pattern avoidance in permutations on partially ordered sets. The number of permutations on P that avoid the pattern a is denoted \(Av_P(a)\). We extend a proof of Simion and Schmidt to show that \(Av_P(123) <= Av_P(132)\) for any poset P, and we exactly classify the posets for which equality holds. We also give asymptotically close bounds on the number of permutations on the Boolean lattice that avoid the pattern \(\{1\}\{1,2\}\{2\}\).

II. Density Structure of Graphs with Applications to Random Graph Models, Eddie Maldonado

Abstract: How can we analyze the structure of graphs in relation to their dense subgraphs? We present an algorithm for orienting an undirected graph and a corresponding decomposition on directed graphs that gives certain information about the location of the densest subgraph of a given graph. We discuss conjectures and further work with regards to the properties and application of this decomposition, and use it to motivate a random graph model that appears to mimic the structure of certain real-world networks better than existing models.

III. The Hilbert-Kunz Function, Marcus Robinson

I. Coverings of the Integers, Kelsey Houston-Edwards and Laura Lyman

Abstract: Our research explores two distinct types of coverings of the integers. First, we look at incongruent disjoint restricted covering systems (or simply, IRDCS) and their properties. We focus on an interesting example, called the ``9-6-3 construction." The second type of covering is inspired by Erdös' minimum modulus problem: Given any natural number \(c\), can one construct a covering of the integers using only moduli greater than \(c\)?

II. Searching for combinations of transcription factors associated with differential gene expression in cichlids, Wyatt Alt

III. Numerical Semigroups and the Frobenius Number, Mikhail Lepilov

The classical Robinson-Schensted algorithm establishes a bijection between permutations in the symmetric group \(\mathfrak{S}_n\) and ordered pairs of same-shape standard Young tableaux of size \(n\).  This map has proven particularly well-suited to certain questions in the representation theory of both \(\mathfrak{S}_n\) and the semisimple Lie groups of type \(A\).  For instance, Kazhdan-Lusztig cells as well as the primitive spectra of semisimple Lie algebras can be readily described in terms of images of this correspondence.

Other sometimes more elementary representation-theoretic information requires more work to extract from standard Young tableaux.  For instance, in independent work, Reifegerste and Sjöstrand developed a method for reading the value of the sign representation of a permutation in \(\mathfrak{S}_n\).  In this talk, we extend this result to the imprimitive complex reflection groups \(G(r,p,n)\) via  a generalized Robinson-Schensted algorithm.

Our increasing understanding of the complexity and richness of biological systems presents an opportunity for a new synthesis that uses principles of computer science to decode biological signals in massive data sets. Using this strategy, we can ask the question: how do genomes change over evolutionary time? Is the state of a genome defined by large numbers of infinitesimally small changes occurring over ages, or, are there large, disruptive changes that in short periods of time erect barriers to recombination and facilitate speciation? I will address this question at several different time scales, examining the effects of a whole genome duplication in teleost fish over millions of years as well as the discovery of large structural variation affecting phenotypic evolution in stickleback fish over thousands of years and in some cases even in mere decades. I will highlight several major computational systems and algorithms, including the Synteny Database and Stacks, erected to address these questions. Finally, I will discuss future plans for an informatics system that tracks objects within genome assemblies to identify and retain variation known to exist across individuals and populations.

Mice are one of the most common model organisms used in biomedical research. They are highly-social creatures that make complicated ultrasonic vocalizations. Understanding these vocalizations better will be a boon for researchers, especially those who study mental diseases, since it will allow them to better identify a mouse's affective state. However, current techniques to identify andextract mouse vocalizations are labor-intensive, requiring a large amount of human time (and money), and slowing the pace of research. We shortcut this process by using hidden Markov models: both to distinguish bona fide calls from background noise, and to follow the frequency of a call over time. We have found that our method offers an improvement on previous automated methods.

The comparison of biological sequences lies at the heart of computational molecular biology. Most often, these comparisons aim to (1) recognize the signal of shared evolutionary history (homology search), (2) recover the tree-like structure of that history (phylogeny inference), or (3) identify conserved blocks among homologous sequences (sequence alignment). I will describe work on all three, with an emphasis on homology search. In particular, I will discuss the probabilistic underpinnings of homology search, and the benefits of addressing homology search with profile hidden Markov models (HMMs), especially as relates to DNA-DNA search with the program nhmmer. I will also present an application of nhmmer to the annotation of repetitive DNA using a database of transposable element family profile HMMs, called Dfam.

We consider the problem of detecting clusters of non-infectious and rare diseases. Cluster detection is the routine surveillance over a large expanse of small administrative regions to identify individual hot-spots of elevated residual spatial risk without any preconceptions about their locations.  A class of cluster detection procedures known as moving-window methods superimpose a large number of circular regions onto the study area.  For each of these circles, the significance of the observed data are determined with respect to the hypothesis of no unmeasured risk inside the circle, as compared to outside the circle.  We propose a Bayesian model that incorporates prior knowledge while accounting for multiple clusters.  All posterior probabilities are estimated using Markov chain Monte Carlo and identify individual areas with high posterior probability of being in a cluster.  After defining the model, applications of the model to epidemiological datasets will be presented.