PRIMES: Research Papers


2014 Research Papers


Tanya Khovanova and Joshua Xiong, Cookie Monster Plays Games (, 6 July 2014)

We research a combinatorial game based on the Cookie Monster problem called the Cookie Monster game that generalizes the games of Nim and Wythoff. We also propose several combinatorial games that are in between the Cookie Monster game and Nim. We discuss properties of P-positions of all of these games.
Each section consists of two parts. The first part is a story presented from the Cookie Monster's point of view, the second part is a more abstract discussion of the same ideas by the authors.


Tanya Khovanova and Joshua Xiong, Nim Fractals (, 23 May 2014)

We enumerate P-positions in the game of Nim in two different ways. In one series of sequences we enumerate them by the maximum number of counters in a pile. In another series of sequences we enumerate them by the total number of counters. We show that the game of Nim can be viewed as a cellular automaton, where the total number of counters divided by 2 can be considered as a generation in which P-positions are born. We prove that the three-pile Nim sequence enumerated by the total number of counters is a famous toothpick sequence based on the Ulam-Warburton cellular automaton. We introduce 10 new sequences.


2013 Research Papers


Ritesh Ragavender, Odd Dunkl Operators and nilHecke Algebras (30 May 2014)

Symmetric functions appear in many areas of mathematics and physics, including enumerative combinatorics, the representation theory of symmetric groups, statistical mechanics, and the quantum statistics of ideal gases. In the commutative (or “even”) case of these symmetric functions, Kostant and Kumar introduced a nilHecke algebra that categorifies the quantum group Uq (sl2) . This categorification helps to better understand Khovanov homology, which has important applications in studying knot polynomials and gauge theory. Recently, Ellis and Khovanov initiated the program of “oddification” as an effort to create a representation theoretic understanding of a new “odd” Khovanov homology, which often yields more powerful results than regular Khovanov homology. In this paper, we contribute to- wards the project of oddification by studying the odd Dunkl operators of Khongsap and Wang in the setting of the odd nilHecke algebra. Specifically, we show that odd divided difference operators can be used to construct odd Dunkl operators, which we use to give a representation of sl2 on the algebra of skew polynomials and evaluate the odd Dunkl Laplacian. We then investigate q-analogs of divided difference operators to introduce new algebras that are similar to the even and odd nilHecke algebras and act on q-symmetric polynomials. We describe such algebras for all previously unstudied values of q. We conclude by generalizing a diagrammatic method and developing the novel method of insertion in order to study q-symmetric polynomials from the perspective of bialgebras.


Gabriella Studt, Construction of the higher Bruhat order on the Weyl group of type B (27 May 2014)

Manin and Schechtman defined the Bruhat order on the type A Weyl group, which is closely associated to the Symmetric group Sn, as the order of all pairs of numbers in {1, 2, ..., n} . They proceeded to define a series of higher orders. Each higher order is an order on the subsets of {1, 2, ..., n} of size k, and can be computed using an inductive argument. It is also possible to define each of these higher orders explicitly, and therefore know conclusively the lexicographic orders for all k. It is thought that a closely related concept of lexicographic order exists for the Weyl group of type B, and that a similar method can be used to compute this series of higher orders. The applicability of this method is demonstrated in the paper, and we are able to determine and characterize the higher Bruhat order explicitly for certain n and k. We therefore conjecture the existence of such an order for all n>k ,as well as its accompanying properties.


Jeffrey Cai, Orbits of a fixed-point subgroup of the symplectic group on partial flag varieties of type A (24 May 2014)

In this paper we compute the orbits of the symplectic group Sp2n on partial flag varieties GL2n / P and on partial flag varieties enhanced by a vector space, C2n x GL2n / P. This extends analogous results proved by Matsuki on full flags. The general technique used in this paper is to take the orbits in the full flag case and determine which orbits remain distinct when the full flag variety GL2n / B is projected down to the partial flag variety GL2n / P.

The recent discovery of a connection between abstract algebra and the classical combinatorial Robinson-Schensted (RS) correspondence has sparked research on related algebraic structures and relationships to new combinatorial bijections, such as the Robinson- Schensted-Knuth (RSK) correspondence, the "mirabolic" RSK correspondence, and the "exotic" RS correspondence. We conjecture an exotic RSK correspondence between the or- bits described in this paper and semistandard bi-tableaux, which would yield an extension to the exotic RS correspondence found in a paper of Henderson and Trapa.


John Long, Evidence of Purifying Selection in Mammals (9 May 2014)

The Human Genome Project completed in 2003 gave us a reference genome for the human species. Before the project was completed, it was believed that the primary function of DNA was to code for protein. However, it was discovered that only 2% of the genome consists of regions that code for proteins. The remaining regions of the genome are either functional regions that regulate the coding regions or junk DNA regions that do nothing. The distinct ion between these two types of regions is not completely clear. Evidence of purifying selection, the decrease in frequency of deleterious mutations , is likely a sign that a region is functional. The goal of this project was to find evidence of purifying se lection in newly acquired regions in the human genome that are hypothesized to be functional. The mean Derived Allele Frequency of the featured regions was compared to that of control regions to determine the likelihood of selection.


Ravi Jagadeesan, A new Gal(Q/Q)-invariant of dessins d'enfants (, 30 March 2014)

We study the action of $\operatorname{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ on the category of Belyi functions (finite, \'{e}tale covers of $\mathbb{P}^1_{\overline{\mathbb{Q}}}\setminus \{0,1,\infty\}$). We describe a new combinatorial $\operatorname{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$-invariant for a certain class of Belyi functions. As a corollary, we obtain that for all $k < 2^{\sqrt{\frac{2}{3}}}$ and all positive integers $N$, there is an $n \le N$ such that the set of degree $n$ Belyi functions of a particular rational Nielsen class must split into at least $\Omega\left(k^{\sqrt{N}}\right)$ Galois orbits. In addition, we define a new version of the Grothendieck-Teichm\"{u}ller group $\widehat{GT}$ into which $\operatorname{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ embeds.


Andrey Grinshpun, Raj Raina, and Rik Sengupta, Minimum degrees of minimal Ramsey graphs (28 March 2014)

For graphs $F$ and $H$, we say $F$ is \textit{Ramsey for $H$} if every $2$-coloring of the edges of $F$ contains a monochromatic copy of $H$. The graph $F$ is \textit{Ramsey $H$-minimal} if there is no proper subgraph $F'$ of $F$ so that $F'$ is Ramsey for $H$. Burr, Erd\H os, and Lov\' asz defined $s(H)$ to be the minimum degree of $F$ over all Ramsey $H$-minimal graphs $F$. Define $H_{t,d}$ to be a graph on $t+1$ vertices consisting of a complete graph on $t$ vertices and one additional vertex of degree $d$. We show that $s(H_{t,d})=d^2$ for all values $1<d\le t$; it was previously known that $s(H_{t,1})=t-1$, so it is surprising that $s(H_{t,2})=4$ is much smaller.

We also make some further progress on some sparser graphs. Fox and Lin observed that $s(H)\ge 2\delta(H)-1$ for all graphs $H$, where $\delta(H)$ is the minimum degree of $H$; a graph $H$ with $s(H)=2\delta(H)-1$ is called \textit{Ramsey simple}. Szab\'o, Zumstein, and Z\"urcher were the first to ask which graphs are Ramsey simple, and conjectured that all bipartite graphs without isolated vertices are. Fox, Grinshpun, Liebenau, Person, and Szab\'o further conjectured that all triangle-free graphs without isolated vertices are Ramsey simple. We show that $d$-regular $3$-connected triangle-free graphs, with one extra technical constraint, are Ramsey simple.


Boryana Doyle, Geoffrey Fudenberg, Maxim Imakaev, and Leonid Mirny, Chromatin loops as modulators of enhancer-promoter interactions in their vicinity (, 26 February 2014)

The classic model of eukaryotic gene expression requires direct spatial contact between a distal enhancer and a proximal promoter. However, recent chromosome conformation capture studies (e.g. Hi-C) show that enhancer and promoters are embedded in a complex network of cell-type specific looping interactions. Here we investigate whether, and to what extent, looping interactions between elements in the vicinity of an enhancer-promoter pair can influence the frequency of enhancer-promoter contacts. Our polymer simulations show that a chromatin loop formed by elements flanking either an enhancer or a promoter suppresses enhancer-promoter interactions, working as a topological insulator. A loop formed by elements located in the region between an enhancer and a promoter, on the contrary, facilitates their interactions. We find that these two consequences of chromatin loops have different genomic extents, with facilitation being a local effect and insulation persisting over a large range of genomic distances. Overall, our results show that looping interactions which do not directly involve an enhancer-promoter contact can nevertheless significantly modulate their interactions. This illustrates the intricate effects that local chromatin organization can have on gene expression.


William Kuszmaul, A New Approach to Enumerating Statistics Modulo n (, 16 February 2014)

We find a new approach to computing the remainder of a polynomial modulo $x^n-1$; such a computation is called modular enumeration. Given a polynomial with coefficients from a commutative $\mathbb{Q}$-algebra, our first main result constructs the remainder simply from the coefficients of residues of the polynomial modulo $\Phi_d(x)$ for each $d\mid n$. Since such residues can often be found to have nice values, this simplifies a number of modular enumeration problems; indeed in some cases, such residues are already known while the related modular enumeration problem has remained unsolved. We list six such cases which our technique makes easy to solve. Our second main result is a formula for the unique polynomial $a$ such that $a \equiv f \mod \Phi_n(x)$ and $a\equiv 0 \mod x^d-1$ for each proper divisor $d$ of $n$.

We find a formula for remainders of $q$-multinomial coefficients and for remainders of $q$-Catalan numbers modulo $q^n-1$, reducing each problem to a finite number of cases for any fixed $n$. In the prior case, we solve an open problem posed by Hartke and Radcliffe. In considering $q$-Catalan numbers modulo $q^n-1$, we discover a cyclic group operation on certain lattice paths which behaves predictably with regard to major index. We also make progress on a problem in modular enumeration on subset sums posed by Kitchloo and Pachter.


Ajay Saini, Predictive Modeling of Opinion and Connectivity Dynamics in Social Networks (26 January 2014)

Social networks have been extensively studied in recent years with the aim of understanding how the connectivity of different societies and their subgroups influences the spread of innovations and opinions through human networks. Using data collected from real-world social networks, researchers are able to gain a better understanding of the dynamics of such networks and subsequently model the changes that occur in these networks over time. In our work, we use data from the Social Evolution dataset of the MIT Human Dynamics Lab to develop a data-driven model capable of predicting the trends and long term changes observed in a real- world social network. We demonstrate the effectiveness of the model by predicting changes in both opinion spread and connectivity that reflect the changes observed in our dataset. After validating the model, we use it to understand how different types of social networks behave over time by varying the conditions governing the change of opinions and connectivity. We conclude with a study of opinion propagation under different conditions in which we use the structure and opinion distribution of various networks to identify sets of agents capable of propagating their opinion throughout an entire network. Our results demonstrate the effectiveness of the proposed modeling approach in predicting the future state of social networks and provide further insight into the dynamics of interactions between agents in real-world social networks.


Rohil Prasad, Investigating GCD in Z[√2] (11 January 2014)

We attempt to optimize the time needed to calculate greatest common divisors in the Euclidean domain Z[√2].





Jin-Woo Bryan Oh, Towards Generalizing Thrackles to Arbitrary Graphs (1 January 2014)

In the 1950s, John Conway came up with the notion of thrackles, graphs with embeddings in which no edge crosses itself, but every pair of distinct edges intersects each other exactly once. He conjectured that |E(G)| ≤ |V(G)| for any thrackle G, a question unsolved to this day. In this paper, we discuss some of the known properties of thrackles and contribute a few new ones.

Only a few sparse graphs can be thrackles, and so it is of interest to find an analogous notion that applies to denser graphs as well. In this paper we introduce a generalized version of thrackles called near-thrackles, and prove some of their properties. We also discuss a large number of conjectures about them which seem very obvious but nonetheless are hard to prove. In the final section, we introduce thrackleability, a number between 0 and 1 that turns out to be an accurate measure of how far away a graph is from being a thrackle..


Junho Won, Lower bounds for the Crossing Number of the Cartesian Product of a Vertex-transitive Graph with a Cycle (1 January 2014)

The minimum number of crossings for all drawings of a given graph $G$ on a plane is called its crossing number, denoted $cr(G)$. Exact crossing numbers are known only for a few families of graphs, and even the crossing number of a complete graph $K_m$ is not known for all $m$. Wenping et al. showed that $cr(K_m\Box C_n)\geqslant n\cdot cr(K_{m+2})$ for $n\geqslant 4$ and $m\geqslant 4$. We adopt their method to find a lower bound for $cr(G\Box C_n)$ where $G$ is a vertex-transitive graph of degree at least 3. We also suggest some particular vertex-transitive graphs of interest, and give two corollaries that give lower bounds for $cr(G\Box C_n)$ in terms of $n$, $cr(G)$, the number of vertices of $G$, and the degree of $G$, which improve on Wenping et al.'s result.


Ying Gao, On an Extension of Stanley Depth for Refinement-Ordered Posets (30 December 2013)

The concept of Stanley depth was originally defined for graded modules over commutative rings in 1982 by Richard P. Stanley. However, in 2009 Herzog, Vladiou, and Zheng found a property, ndepth, of posets analogous to the Stanley depths of certain modules, which provides an important link between combinatorics and commutative algebra. Due to this link, there arises the question of what this ndepth is for certain classes of posets.

Because ndepth was only recently defined, much remains to be discovered about it. In 2009, Biro, Howard, Keller, Trotter and Young found a lower bound for the ndepth of the poset of nonempty subsets of {1; 2; ...; n} ordered by inclusion. In 2010, Wang calculated the ndepth of the product of chains nk \ 0. However, ndepth has yet to be studied in relation to many other commonly found classes of posets. We chose to research the properties of the ndepths of one such well-known class of posets - the posets which consist of non-empty partitions of sets ordered by refinement, which we denote as Gi.

We use combinatorial and algebraic methods to find the ndepths for small posets in Gi. We show that for posets of increasing size in Gi, new depth is strictly non-decreasing, and furthermore we show that ndepth[Gi] ≥ [8i/29] for all i. We also find that for all i, ndepth[Gi] ≤ i through the proof that ndepth[Gi+1] ≤ ndepth[Gi] + 1.


Nihal Gowravaram, Enumeration of Subclasses of (2+2)-free Partially Ordered Sets (26 December 2013)

We investigate avoidance in (2+2)-free partially ordered sets, posets that do not contain any induced subposet isomorphic to the union of two disjoint chains of length two. In particular, we are interested in enumerating the number of partially ordered sets of size N avoiding both 2+2 and some other poset α. For any α of size 3, the results are already well-known. However, out of the 15 such α of size 4, only 2 were previously known. Through the course of this paper, we explicitly enumerate 7 other such α of size 4. Also, we consider the avoidance of three posets simultaneously, 2+2 along with some pair (α,β); it turns out that this enumeration is often clean, and has sometimes surprising results. Furthermore, we turn to the question of Wilf-equivalences in (2+2)-free posets. We show such an equivalence between the Y-shaped and chain posets of size 4 via a direct bijection, and in fact, we extend this to show a Wilf-equivalence between the general chain poset and a general Y-shaped poset of the same size. In this paper, while our focus is on enumeration, we also seek to develop an understanding of the structures of the posets in the subclasses we are studying.


Steven Homberg, Finding Enrichments of Functional Annotations for Disease- Associated Single-Nucleotide Polymorphisms (10 November 2013)

Computational analysis of SNP-disease associations from GWAS as well as functional annotations of the genome enables the calculation of a SNP set's enrichment for a disease. These statistical enrichments can be and are calculated with a variety of statistical techniques, but there is no standard statistical method for calculating enrichments. Several entirely different tests are used by different investigators in the field. These tests can also be conducted with several variations in parameters which also lack a standard. In our investigation, we develop a computational tool for conducting various enrichment calculations and, using breast cancer-associated SNPs from a GWAS catalog as a foreground against all GWAS SNPs as a background, test the tool and analyze the relative performance of the various tests. The computational tool will soon be released to the scientific community as a part of the Bioconductor package. Our analysis shows that, for R2 threshold in LD block construction, values around 0.8-0.9 are preferable to those with more lax and more strict thresholds respectively. We find that block-matching tests yield better results than peak-shifting tests. Finally, we find that, in block-matching tests, block tallying using binary scoring, noting whether or not a block has an annotation only, yields the most meaningful results, while weighting LD r2 threshold has no influence.


Kavish Gandhi, Noah Golowich, and László Miklós Lovász, Degree of Regularity of Linear Homogeneous Equations (, 27 Sept 2013)

We define a linear homogeneous equation to be strongly r-regular if, when a finite number of inequalities is added to the equation, the system of the equation and inequalities is still r-regular. In this paper, we derive a constraint on the coefficients of a linear homogeneous equation that gives a sufficient condition for the equation to be strongly r-regular. In 2009, Alexeev and Tsimerman introduced a family of equations, each of which is (n-1)-regular but not n-regular, verifying a conjecture of Rado from 1933. We show that these equations are actually strongly (n-1)-regular as a corollary of our results.


Leigh Marie Braswell and Tanya Khovanova, On the Cookie Monster Problem (, 23 Sept 2013)

The Cookie Monster Problem supposes that the Cookie Monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number of a set is the minimum number of moves the Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for jars containing cookies in the Fibonacci, Tribonacci, n-nacci, and Super-n-nacci sequences. We also construct sequences of k jars such that their Cookie Monster numbers are asymptotically rk, where r is any real number between 0 and 1 inclusive.


Vahid Fazel-Rezai, Equivalence Classes of Permutations Modulo Replacements Between 123 and Two-Integer Patterns (, 18 Sept 2013), published in The Electronic Journal of Combinatorics 21:2 (2014)

We explore a new type of replacement of patterns in permutations, suggested by James Propp, that does not preserve the length of permutations. In particular, we focus on replacements between 123 and a pattern of two integer elements. We apply these replacements in the classical sense; that is, the elements being replaced need not be adjacent in position or value. Given each replacement, the set of all permutations is partitioned into equivalence classes consisting of permutations reachable from one another through a series of bi-directional replacements. We break the eighteen replacements of interest into four categories by the structure of their classes and fully characterize all of their classes.


Leigh Marie Braswell and Tanya Khovanova, Cookie Monster Devours Naccis (, 18 May 2013), published in the College Mathematics Journal 45:2 (2014)

In 2002, Cookie Monster appeared in The Inquisitive Problem Solver. The hungry monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for Fibonacci, Tribonacci and other nacci sequences.


2012 Research Papers


William Kuszmaul and Ziling Zhou, Equivalence classes in Sn for three families of pattern-replacement relations (, 20 April 2013)

We study a family of equivalence relations in Sn, the group of permutations on n letters, created in a manner similar to that of the Knuth relation and the forgotten relation. For our purposes, two permutations are in the same equivalence class if one can be reached from the other through a series of pattern-replacements using patterns whose order permutations are in the same part of a predetermined partition of Sc. In particular, we are interested in the number of classes created in Sn by each relation and in characterizing these classes. Imposing the condition that the partition of Sc has one nontrivial part containing the cyclic shifts of a single permutation, we find enumerations for the number of nontrivial classes. When the permutation is the identity, we are able to compare the sizes of these classes and connect parts of the problem to Young tableaux and Catalan lattice paths. Imposing the condition that the partition has one nontrivial part containing all of the permutations in Sc beginning with 1, we both enumerate and characterize the classes in Sn. We do the same for the partition that has two nontrivial parts, one containing all of the permutations in Sc beginning with 1, and one containing all of the permutations in Sc ending with 1.


William Kuszmaul, Counting permutations modulo pattern-replacement equivalences for three-letter patterns (, 20 April 2013, published in the Electronic Journal of Combinatorics 20:4 (2013))

We study a family of equivalence relations in Sn, the group of permutations on n letters, created in a manner similar to that of the Knuth relation and the forgotten relation. For our purposes, two permutations are in the same equivalence class if one can be reached from the other through a series of pattern-replacements using patterns whose order permutations are in the same part of a predetermined partition of Sc. When the partition is of S3 and has one nontrivial part of size greater than two, we provide formulas for the number of classes created in all unresolved cases. When the partition is of S3 and has two nontrivial parts, each of size two (as do the Knuth and forgotten relations), we enumerate the classes for 13 of the 14 unresolved cases. In two of these cases, enumerations arise which are the same as those yielded by the Knuth and forgotten relations. The reasons for this phenomenon are still largely a mystery.


Tanya Khovanova and Ziv Scully, Efficient Calculation of Determinants of Symbolic Matrices with Many Variables (, 13 April 2013)

Efficient matrix determinant calculations have been studied since the 19th century. Computers expand the range of determinants that are practically calculable to include matrices with symbolic entries. However, the fastest determinant algorithms for numerical matrices are often not the fastest for symbolic matrices with many variables. We compare the performance of two algorithms, fraction-free Gaussian elimination and minor expansion, on symbolic matrices with many variables. We show that, under a simplified theoretical model, minor expansion is faster in most situations. We then propose optimizations for minor expansion and demonstrate their effectiveness with empirical data.


Michael Zanger-Tishler and Saarik Kalia, On the Winning and Losing Parameters of Schmidt's Game (8 April 2013)

First introduced by Wolfgang Schmidt, the (α, β)-game and its modifications have been shown to be a powerful tool in Diophantine approximation, metric number theory, and dynamical systems. However, natural questions about the winning-losing parameters of most sets have not been studied thoroughly even after more than 40 years. There are a few results in the literature showing that some non-trivial points and small regions are winning or losing, but complete pictures remain largely unknown. Our main goal in this paper is to provide as much detail as possible about the global pictures of winning-losing parameters for some interesting families of sets.


Sheela Devadas and Steven Sam, Representations of Cherednik algebras of G (m, r, n) in positive characteristic (, 3 April 2013; forthcoming in Journal of Commutative Algebra)

We study lowest-weight irreducible representations of rational Cherednik algebras attached to the complex reflection groups G(m, r, n) in characteristic p. Our approach is mostly from the perspective of commutative algebra. By studying the kernel of the contravariant bilinear form on Verma modules, we obtain formulas for Hilbert series of irreducible representations in a number of cases, and present conjectures in other cases. We observe that the form of the Hilbert series of the irreducible representations and the generators of the kernel tend to be determined by the value of n modulo p, and are related to special classes of subspace arrangements. Perhaps the most novel (conjectural) discovery from the commutative algebra perspective is that the kernel can be given the structure of a "matrix regular sequence" in some instances, which we prove in some small cases.


Christina Chen and Nan Li, Apollonian Equilateral Triangles (, 1 March 2013)

Given an equilateral triangle with a the square of its side length and a point in its plane with b, c, d the squares of the distances from the point to the vertices of the triangle, it can be computed that a, b, c, d satisfy 3(a2+b2+c2+d2) = (a+b+c+d)2. This paper derives properties of quadruples of nonnegative integers (a; b; c; d), called triangle quadruples, satisfying this equation. It is easy to verify that the operation generating (a; b; c; a+b+c-d) from (a; b; c; d) preserves this feature and that it and analogous ones for the other elements can be represented by four matrices. We examine in detail the triangle group, the group with these operations as generators, and completely classify the orbits of quadruples with respect to the triangle group action. We also compute the number of triangle quadruples generated after a certain number of operations and approximate the number of quadruples bounded by characteristics such as the maximal element. Finally, we prove that the triangle group is a hyperbolic Coxeter group and derive information about the elements of triangle quadruples by invoking Lie groups. We also generalize the problem to higher dimensions.


Dhroova Aiylam, Modified Stern-Brocot sequences (, 29 January 2013)

We present the classical Stern-Brocot tree and provide a new proof of the fact that every rational number between 0 and 1 appears in the tree. We then generalize the Stern-Brocot tree to allow for arbitrary choice of starting terms, and prove that in all cases the tree maintains the property that every rational number between the two starting terms appears exactly once.


Nihal Gowravaram and Ravi Jagadeesan, Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (, 28 January 2013)

We investigate pattern avoidance in alternating permutations and generalizations thereof. First, we study pattern avoidance in an alternating analogue of Young diagrams. In particular, we extend Babson-West's notion of shape-Wilf equivalence to apply to alternating permutations and so generalize results of Backelin-West-Xin and Ouchterlony to alternating permutations. Second, we study pattern avoidance in the more general context of permutations with restricted ascents and descents. We consider a question of Lewis regarding permutations that are the reading words of thickened staircase Young tableaux, that is, permutations that have (k - 1) ascents followed by a descent, followed by (k - 1) ascents, et cetera. We determine the relative sizes of the sets of pattern-avoiding (k - 1)-ascent permutations in terms of the forbidden pattern. Furthermore, we give inequalities in the sizes of sets of pattern-avoiding permutations in this context that arise from further extensions of shape-equivalence type enumerations.


Rohil Prasad and Jonathan Tidor, Optimal Results in Staged Self-Assembly of Wang Tiles (22 January 2013)

The subject of self-assembly deals with the spontaneous creation of ordered systems from simple units and is most often applied in the field of nanotechnology. The self-assembly model of Winfree describes the assembly of Wang tiles, simulating assembly in real-world systems. We use an extension of this model, known as the staged self-assembly model introduced by Demaine et al. that allows for discrete steps to be implemented and permits more diverse constructions. Under this model, we resolve the problem of constructing segments, creating a method to produce them optimally. Generalizing this construction to squares gives a new flexible method for their construction. Changing a parameter of the model, we explore much simpler constructions of complex monotone shapes. Finally, we present an optimal method to build most arbitrary shapes.


Aaron Klein, On Rank Functions of Graphs (6 January 2013)

We study rank functions (also known as graph homomorphisms onto Z), ways of imposing graded poset structures on graphs. We rst look at a variation on rank functions called discrete Lipschitz functions. We relate the number of Lipschitz functions of a graph G to the number of rank functions of both G and G X E. We then find generating functions that enable us to compute the number of rank or Lipschitz functions of a given graph. We look at a subset of graphs called squarely generated graphs, which are graphs whose cycle space has a basis consisting only of 4-cycles. We show that the number of rank functions of such a graph is proportional to the number of 3-colorings of the same graph, thereby connecting rank functions to the Potts model of statistical mechanics. Lastly, we look at some asymptotics of rank and Lipschitz functions for various types of graphs.


Andrew Xia, Integrated Gene Expression Probabilistic Models for Cancer Staging (1 January 2013)

The current system for classifying cancer patients' stages was introduced more than one hundred years ago. With the modern advance in technology, many parts of the system have been outdated. Because the current staging system emphasizes surgical procedures that could be harmful to patients, there has been a movement to develop a new Taxonomy, using molecular signatures to potentially avoid surgical testing. This project explores the issues of the current classification system and also looking for a potentially better way to classify cancer patients’ stages. Computerization has made a vast amount of cancer data available online. However, a significant portion of the data is incomplete; some crucial information is missing. It is logical to attempt to develop a system of recovering missing cancer data. Successful completion of this research saves costs and increases efficiency in cancer research and curing. Using various methods, we have shown that cancer stages cannot be simply extrapolated with incomplete data. Furthermore, a new approach of using RNA Sequencing data is studied. RNA Sequencing can potentially become a cost-efficient way to determine a cancer patient’s stage. We have obtained promising results of using RNA sequencing data in breast cancer staging.


Surya Bhupatiraju, On the Complexity of the Marginal Satisfiability Problem (18 November 2012)

The marginal satisfiability problem (MSP) asks: Given desired marginal distributions DS for every subset S of c variable indices from {1, . . . , n}, does there exist a distribution D over n-tuples of values in {1, . . . , m} with those S-marginals DS? Previous authors have studied MSP in fixed dimensions, and have classified the complexity up to certain upper bounds. However, when using general dimensions, it is known that the size of distributions grows exponentially, making brute force algorithms impractical. This presents an incentive to study more general, tractable variants, which in turn may shed light on the original problem's structure. Thus, our work seeks to explore MSP and its variants for arbitrary dimension, and pinpoint its complexity more precisely. We solve MSP for n = 2 and completely characterize the complexity of three closely related variants of MSP. In particular, we detail novel greedy and stochastic algorithms that handle exponentially-sized data structures in polynomial time, as well as generate accurate representative samples of these structures in polynomial time. These algorithms are also unique in that they represent possible protocols in data compression for communication purposes. Finally, we posit conjectures related to more generalized MSP variants, as well as the original MSP.


Fengning Ding and Aleksander Tsymbaliuk, Representations of Infinitesimal Cherednik Algebras (, 17 October 2012, published in Representation Theory 17 (2013))

Infinitesimal Cherednik algebras, first introduced by Etingof, Gan, and Ginzburg (2005), are continuous analogues of rational Cherednik algebras, and in the case of gln, are deformations of universal enveloping algebras of the Lie algebras sln+1. Despite these connections, infinitesimal Cherednik algebras are not widely-studied, and basic questions of intrinsic algebraic and representation theoretical nature remain open. In the first half of this paper, we construct the complete center of Hζ(gln) for the case of n = 2 and give one particular generator of the center, the Casimir operator, for general n. We find the action of this Casimir operator on the highest weight modules to prove the formula for the Shapovalov determinant, providing a criterion for the irreducibility of Verma modules. We classify all irreducible finite dimensional representations and compute their characters. In the second half, we investigate Poisson-analogues of the infinitesimal Cherednik algebras and use them to gain insight on the center of Hζ(gln). Finally, we investigate Hζ(sp2n) and extend various results from the theory of Hζ(gln), such as a generalization of Kostant's theorem.


Tanya Khovanova and Dai Yang, Halving Lines and Their Underlying Graphs (, 17 October 2012)

In this paper we study underlying graphs corresponding to a set of halving lines. We establish many properties of such graphs. In addition, we tighten the upper bound for the number of halving lines.


2011 Research Papers


Carl Lian, Representations of Cherednik Algebras Associated to Complex Reflection Groups in Positive Characteristic (, 1 July 2012)

We consider irreducible lowest-weight representations of Cherednik algebras associated to certain classes of complex reflection groups in characteristic p. In particular, we study maximal submodules of Verma modules associated to these algebras. Various results and conjectures are presented concerning generators of these maximal submodules, which are found by computing singular polynomials of Dunkl operators. This work represents progress toward the general problem of determining Hilbert series of irreducible lowest-weight representations of arbitrary Cherednik algebras in characteristic p.


Aaron Klein, Joel Brewster Lewis, and Alejandro Morales, Counting matrices over finite fields with support on skew Young and Rothe diagrams (, 26 March 2012; published in the Journal of Algebraic Combinatorics, May 2013)

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries these numbers of matrices are not polynomials in q (Stembridge 98); however, when the set of entries is a Young diagram, the numbers, up to a power of q-1, are polynomials with nonnegative coefficients (Haglund 98). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund's result to complements of skew Young diagrams, and we apply this result to the case when the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.


Surya Bhupatiraju, Pavel Etingof, David Jordan, William Kuszmaul, and Jason Li, Lower central series of a free associative algebra over the integers and finite fields (, 8 March 2012, published in the Journal of Algebra, December 2012)

Consider the free algebra A_n generated over Q by n generators x_1, ..., x_n. Interesting objects attached to A = A_n are members of its lower central series, L_i = L_i(A), defined inductively by L_1 = A, L_{i+1} = [A,L_{i}], and their associated graded components B_i = B_i(A) defined as B_i=L_i/L_{i+1}. These quotients B_i, for i at least 2, as well as the reduced quotient \bar{B}_1=A/(L_2+A L_3), exhibit a rich geometric structure, as shown by Feigin and Shoikhet and later authors (Dobrovolska-Kim-Ma, Dobrovolska-Etingof, Arbesfeld-Jordan, Bapat-Jordan).
We study the same problem over the integers Z and finite fields F_p. New phenomena arise, namely, torsion in B_i over Z, and jumps in dimension over F_p. We describe the torsion in the reduced quotient RB_1 and B_2 geometrically in terms of the De Rham cohomology of Z^n. As a corollary we obtain a complete description of \bar{B}_1(A_n(Z)) and \bar{B}_1(A_n(F_p)), as well as of B_2(A_n(Z[1/2])) and B_2(A_n(F_p)), p>2. We also give theoretical and experimental results for B_i with i>2, formulating a number of conjectures and questions based on them. Finally, we discuss the supercase, when some of the generators are odd (fermionic) and some are even (bosonic), and provide some theoretical results and experimental data in this case.

David Jordan and Masahiro Namiki, Determinant formulas for the reflection equation algebra (19 Feb 2012)

In this note, we report on work in progress to explicitly describe generators of the center of the reflection equation algebra associated to the quantum GL(N) R-matrix. In particular, we conjecture a formula for the quantum determinant, and for the quadratic central element, both of which involve the excedance statistic on the symmetric group. Current efforts are directed at proving these formulas, and at finding formulas for the remaining central elements.


Ziv Scully, Yan Zhang, and Damien Jiang, Total chip numbers and motors in the parallel chip-firing game (12 Feb 2012)

The parallel chip-firing game is an automaton on graphs in which vertices "fire" chips to their neighbors when they have enough chips to do so. In this work we first characterize positions that repeat every 2 turns. Using this we determine the eventual periods of games on trees given only the total number of chips. We introduce the concepts of motorized parallel chip-firing games and motor vertices, study the effects of motors connected to a tree, and show that some motorized games can be simulated by ordinary games. We end by proving the equivalence of two conjectures: one restricts the firing pattern of a single vertex over a period; the other restricts the set of vertices that fire at a single time step. These conjectures, if shown to be true, would greatly simplify the study of the parallel chip- ring game.


Sheela Devadas, Lowest-weight representations of Cherednik algebras in positive characteristic (29 Jan 2012)

We study lowest-weight irreducible representations of rational Cherednik algebras attached to the complex reflection groups G(m, r, n) in characteristic p, focusing specifically on the case pn , which is more complicated than the case p > n. The goal of our work is to calculate characters (and in particular Hilbert series) of these representations. By studying the kernel of the contravariant bilinear form on Verma modules, we proved formulas for Hilbert series of irreducible modules in a number of cases, and also obtained a lot of computer data which suggests a number of conjectures. Specifically, we find that the shape and form of the Hilbert series of the irreducible representations and the generators of the kernel tend to be determined by the value of n modulo p .


Christina Chen, Maximizing Volume Ratios for Shadow Covering by Tetrahedra (, 9 Jan 2012)

Define a body A to be able to hide behind a body B if the orthogonal projection of B contains a translation of the corresponding orthogonal projection of A in every direction. In two dimensions, it is easy to observe that there exist two objects such that one can hide behind another and have a larger area than the other. It was recently shown that similar examples exist in higher dimensions as well. However, the highest possible volume ratio for such bodies is still undetermined. We investigated two three-dimensional examples, one involving a tetrahedron and a ball and the other involving a tetrahedron and an inverted tetrahedron. We calculate the highest volume ratio known up to this date, 1.16, which is generated by our second example.


Yongyi Chen, Pavel Etingof, David Jordan, and Michael Zhang, Poisson traces in positive characteristic (, 29 Dec 2011)

We study Poisson traces of the structure algebra A of an affine Poisson variety X defined over a field of characteristic p. According to arXiv:0908.3868v4, the dual space HP_0(A) to the space of Poisson traces arises as the space of coinvariants associated to a certain D-module M(X) on X. If X has finitely many symplectic leaves and the ground field has characteristic zero, then M(X) is holonomic, and thus HP_0(A) is finite dimensional. However, in characteristic p, the dimension of HP_0(A) is typically infinite. Our main results are complete computations of HP_0(A) for sufficiently large p when X is 1) a quasi-homogeneous isolated surface singularity in the three-dimensional space, 2) a quotient singularity V/G, for a symplectic vector space V by a finite subgroup G in Sp(V), and 3) a symmetric power of a symplectic vector space or a Kleinian singularity. In each case, there is a finite nonnegative grading, and we compute explicitly the Hilbert series. The proofs are based on the theory of D-modules in positive characteristic.


Saarik Kalia, The Generalizations of the Golden Ratio: Their Powers, Continued Fractions, and Convergents (23 Dec 2011)

The relationship between the golden ratio and continued fractions is commonly known about throughout the mathematical world: the convergents of the continued fraction are the ratios of consecutive Fibonacci numbers. The continued fractions for the powers of the golden ratio also exhibit an interesting relationship with the Lucas numbers. In this paper, we study the silver means and introduce the bronze means, which are generalizations of the golden ratio. We correspondingly introduce the silver and bronze Fibonacci and Lucas numbers, and we prove the relationship between the convergents of the continued fractions of the powers of the silver and bronze means and the silver and bronze Fibonacci and Lucas numbers. We further generalize this to the Lucas constants, a two-parameter generalization of the golden ratio.


Caroline Ellison, The Number of Nonzero Coefficients of Powers of a Polynomial over a Finite Field (15 Nov 2011)

Coefficients of polynomials over finite fields often encode information that can be applied in various areas of science; for instance, computer science and representation theory. The purpose of this project is to investigate these coefficients over the finite field Fp. We find four exact results for the number of nonzero coefficients in special cases of n and p for the polynomial (1 + x + x2)n. More importantly, we use Amdeberhan and Stanley's matrices to find what we conjecture to be an approximation for the sum of the number of nonzero coefficients of P(x)n over Fp. We also relate the number of nonzero coefficients to the number of base p digits of n. These results lead to questions in representation theory and combinatorics.


Xiaoyu He, On the Classification of Universal Rotor-Routers (, 6 Nov 2011)

The combinatorial theory of rotor-routers has connections with problems of statistical mechanics, graph theory, chaos theory, and computer science. A rotor-router network defines a deterministic walk on a digraph G in which a particle walks from a source vertex until it reaches one of several target vertices. Motivated by recent results due to Giacaglia et al., we study rotor-router networks in which all non-target vertices have the same type. A rotor type r is universal if every hitting sequence can be achieved by a homogeneous rotor-router network consisting entirely of rotors of type r. We give a conjecture that completely classifies universal rotor types. Then, this problem is simplified by a theorem we call the Reduction Theorem that allows us to consider only two-state rotors. A rotor-router network called the compressor, because it tends to shorten rotor periods, is introduced along with an associated algorithm that determines the universality of almost all rotors. New rotor classes, including boppy rotors, balanced rotors, and BURD rotors, are defined to study this algorithm rigorously. Using the compressor the universality of new rotor classes is proved, and empirical computer results are presented to support our conclusions. Prior to these results, less than 100 of the roughly 260,000 possible two-state rotor types of length up to 17 were known to be universal, while the compressor algorithm proves the universality of all but 272 of these rotor types.


Yongyi Chen and Michael Zhang, On zeroth Poisson homology in positive characteristic (30 Sept 2011)

A Poisson algebra is a commutative algebra with a Lie bracket {,} satisfying the Leibniz rule. An important invariant of a Poisson algebra A is its zeroth Poisson homology HP_0(A)=A/A,A}. It characterizes densities on the phase space invariant under all Hamiltonian flows. Also, the dimension of HP_0(A) gives an upper bound for the number of irreducible representations of any quantization of A. We study HP_0(A) when A is the algebra of functions on an isolated quasihomogeneous surface singularity. Over C, it's known that HP_0(A) is the Jacobi ring of the singularity whose dimension is the Milnor number. We generalize this to characteristic p. In this case, HP_0(A) is a finite (although not finite dimensional) module over A^p. We give its conjectural Hilbert series for Kleinian singularities and for cones of smooth projective curves, and prove the conjecture in several cases. (The conjecture has now been proved in general in our follow-up paper with P. Etingof and D. Jordan.)


Christina Chen, Tanya Khovanova, and Daniel A. Klain, Volume bounds for shadow covering (, 8 Sep 2011, published in Transactions of the American Mathematical Society 366 (2014))

For n ≥ 2 a construction is given for a large family of compact convex sets K and L in n-dimensional Euclidean space such that the orthogonal projection Lu onto the subspace u contains a translate of the corresponding projection Ku for every direction u, while the volumes of K and L satisfy Vn(K) > Vn(L). It is subsequently shown that, if the orthogonal projection Lu onto the subspace u contains a translate of Ku for every direction u, then the set (n/(n−1))L contains a translate of K. It follows that Vn(K)(n/(n−1))n Vn(L). In particular, we derive a universal constant bound Vn(K) ≤ 2.942 Vn(L), independent of the dimension n of the ambient space. Related results are obtained for projections onto subspaces of some fixed intermediate co-dimension. Open questions and conjectures are also posed.


Email us: