# PRIMES: Research Papers

2014 Research Papers

Tanya Khovanova and Joshua Xiong, Cookie Monster Plays Games (arXiv.org, 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 (arXiv.org, 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 *U*_{q} (*sl*_{2})
. 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 *
sl*_{2} 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 *S _{n}*, 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 Sp_{2n} on partial flag varieties GL_{2n
}/* P* and on partial flag varieties enhanced
by a vector space, C^{2n} x GL_{2n
}/* 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 GL_{2n }/* B* is projected down
to the partial flag variety GL_{2n }/* 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 (arXiv.org, 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 (BioRxiv.org, 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* (arXiv.org, 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]
(1*1
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 n^{k} \ 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 G_{i}.

We use combinatorial and algebraic methods to find the
ndepths for small posets in G_{i}. We show
that for posets of increasing size in G_{i},
new depth is strictly non-decreasing, and furthermore we
show that ndepth[G_{i}] ≥ [8i/29]
for all i. We also find that for all i,
ndepth[G_{i}] ≤ i through the
proof that ndepth[G_{i+1}] ≤ ndepth[G_{i}]
+ 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 (arXiv.org, 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__ (arXiv.org, 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 (arXiv.org, 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__ (arXiv.org, 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 S _{n} for three families of
pattern-replacement relations__ (arXiv.org, 20 April 2013)

We study a family of equivalence relations in *S _{n}*,
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

*S*. In particular, we are interested in the number of classes created in

_{c}*S*by each relation and in characterizing these classes. Imposing the condition that the partition of

_{n}*S*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

_{c}*S*beginning with 1, we both enumerate and characterize the classes in

_{c}*S*. We do the same for the partition that has two nontrivial parts, one containing all of the permutations in

_{n}*S*beginning with 1, and one containing all of the permutations in

_{c}*S*ending with 1.

_{c}

William Kuszmaul,
__Counting permutations
modulo pattern-replacement equivalences for three-letter
patterns__ (arXiv.org, 20 April 2013, published in the
Electronic Journal of Combinatorics 20:4 (2013))

We study a family of equivalence relations in *S _{n}*,
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

*S*. When the partition is of

_{c}*S*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

_{3}*S*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.

_{3}

Tanya Khovanova and Ziv Scully,
__Efficient
Calculation of Determinants of Symbolic Matrices with Many
Variables__ (arXiv.org, 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__ (arXiv.org, 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__ (arXiv.org,
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(*a*^{2}+*b*^{2}+*c*^{2}+*d*^{2})
= (*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__ (arXiv.org, 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__ (arXiv.org, 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 *D _{S}* 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

*D*? 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

_{S}*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__ (arXiv.org, 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 gl_{n},
are deformations of universal enveloping algebras of the Lie
algebras sl_{n+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_{ζ}(gl_{n}) 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_{ζ}(gl_{n}). Finally, we investigate H_{ζ}(sp_{2n}) and
extend various results from the theory of H_{ζ}(gl_{n}), such as
a generalization of Kostant's theorem.

Tanya Khovanova and Dai Yang,
__Halving Lines and
Their Underlying Graphs__ (arXiv.org, 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__ (arXiv.org, 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__ (arXiv.org, 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__ (arXiv.org, 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 *p* ≤ *n* ,
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__ (arXiv.org, 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__ (arXiv.org,
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 F* _{p}*. We
find four exact results for the number of nonzero
coefficients in special cases of

*n*and

*p*for the polynomial (1 + x + x

^{2})

*. 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 F*

^{n}*. We also relate the number of nonzero coefficients to the number of base*

_{p}*p*digits of

*n*. These results lead to questions in representation theory and combinatorics.

Xiaoyu He,
__On the
Classification of Universal Rotor-Routers__ (arXiv.org, 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__ (arXiv.org, 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 *L _{u}* onto the subspace

*u*contains a translate of the corresponding projection

^{⊥}*K*for every direction

_{u}*u*, while the volumes of

*K*and

*L*satisfy

*V*>

_{n}(K)*V*. It is subsequently shown that, if the orthogonal projection

_{n}(L)*L*onto the subspace

_{u}*u*contains a translate of

^{⊥}*K*for every direction

_{u}*u*, then the set

*(n/(n−1))L*contains a translate of

*K*. It follows that

*V*≤

_{n}(K)*(n/(n−1))*. In particular, we derive a universal constant bound

^{n}V_{n}(L)*V*≤ 2.942

_{n}(K)*V*, independent of the dimension

_{n}(L)*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:**