Scott Neville

Preprint here.  Joint work with Sergey Fomin.   See also my follow-up preprint here.

Slightly extended abstract:

A cyclically ordered quiver is a quiver endowed with an additional structure of a cyclic ordering of its vertices - one might imagine drawing the vertices of the quiver on the unit circle. This structure, which naturally arises in many important applications, gives rise to new powerful mutation (semi) invariants. The invariants we find are truly mutation invariants when the cyclic ordering is 'totally proper,' we describe several families of quivers with totally proper cyclic orderings. 

For quivers coming from divides, the most natural cyclic ordering leads to the Alexander polynomial of the associated knot. 

I resolved an important conjecture from this paper in the follow-up. I showed that all acyclic quivers are totally proper, and thus we have new necessary conditions for a quiver to be mutation equivalent to an acyclic one. This relies heavily on a construction by Ahmet Seven, available here.

Preprint here.  Joint work with Sergey Fomin. See also my follow-up preprint here, joint with Tucker Ervin. You can play with an example online here (try mutating at 310212101201)

Slightly extended abstract:
A mutation cycle is a cycle in a graph whose vertices are labeled by the quivers in a given mutation class and whose edges correspond to single mutations. For any fixed $n \geq 4$, we describe arbitrarily long mutation cycles involving n-vertex quivers. Each of these mutation cycles allows for an arbitrary choice of n choose 2 positive integer parameters, which can be recovered from any quiver on the cycle. None of the mutation cycles we construct can be paved by short mutation cycles, so that some quiver on our mutation cycle of length M only lies on mutation cycles of length at least M-n. In particular, this proves there are arbitrarily large cycles without shortcuts.

Note that this also includes a proof that many exchange graphs are trees (see section 9), and examples of several kinds of mutation cycle beyond the main construction in Theorem 1.1 (see section 10). 

In the follow-up paper:
We give a simple proof and generalized construction for long mutation cycles in terms of triangular extensions of quivers with reddening sequences. These cycles also have many free parameters, and (under more strict conditions) do not have 'pavings'.

This paper also collects several examples of reddening sequences from the literature, and some results on the reddening sequences of small quivers.

Preprint here.  Joint work with Arjun Krishnan, and Sevak Mkrtchyan.

Slightly extended abstract:

In the directed polymer model, we have two different kinds of randomness being played against each other. First, we have the environment, consisting of random weights on the points in a lattice, which we resample independently after each time step. Second, a random walk, which has some preferred distribution of next 'steps' on the lattice. The model produces a distribution on the possible resulting walks from the origin, where the walk is biased by the random environment based on a parameter (the temperature). 

In dimension 1, the directed polymer model is in the celebrated KPZ universality class, and for all positive temperatures, a typical polymer path shows non-Brownian KPZ scaling behavior. In dimensions 3 or larger, it is a classical fact that the polymer has two phases: Brownian behavior at high temperature, and non-Brownian behavior at low temperature. We consider the response of the polymer to an external field or tilt, and show that at fixed temperature, the polymer has Brownian behavior for some fields and non-Brownian behavior for others. In other words, the external field can \emph{induce} the phase transition in the directed polymer model.

Paper here.  Joint work with Suresh Venkatasubramanian, Danielle Ensign, and Arnab Paul.

Slightly extended abstract:

Neural networks often outperform intentionally designed programs for many 'real world' tasks. A natural question is if we can use a trained neural network to find a more classical algorithm in reasonable time. One theory was that neural networks work by extracting and removing invariants of the data. This begs a computational question: what are some transformations of the input data which do not change a neural networks output. We show this is generally infeasible, in the sense that determining if a neural network is invariant to some permutation of the inputs is NP-hard (even under loose definitions of invariant). 

Actual title: An m-ary partition generalization of a past Putnam problem

Paper here. Published in the  Australasian Journal of Combinatorics Vol 72 with Timothy Flowers and James Sellers

Slightly extended abstract:
The 1983 Putnam competition included a problem which asked about the number of partitions with only 2^k parts (binary partitions) with each part used at most 3 (=2^2-1) times. We generalize this to m-ary partitions (so parts m^k) with each part used at most m^j -1 times. Generating functions are very up to this task, and reveal a cute symmetry. One can interchange the roles of k and j. We give a bijection to explain this symmetry, based on a classical transposition argument for partitions with bounded sizes vs bounded number of parts.

Story: Timothy Flowers gave a short talk on the problem and generating function results at an AMS mathfest. I thought the problem fun, and found a bijection to explain their results over lunch.

I enjoy combinatorics, theoretical machine learning, and algorithmic questions of all kinds. I enjoy working across disciplines, having had projects in pure mathematics, computer science, machine learning, and anthropology.

See my previous projects page for a sampling of what I've done.

Some problems I've really enjoyed thinking about (some have solutions in the literature, but that makes them no less fun):

Suppose we take three n-sided dice each a different color, say R,G, and B, and roll all at once. We then sort them from least to greatest (reroll if there are any ties). If the dice are fair and identical, we get the uniform distribution of orderings. But if some of the dice are biased we could get many other distributions on S_3. Question: what does this set of distributions look like? (Thanks to Moon Duchin for sharing this one)

Consider a graph G on n-vertices. Pick two distinct edges e, f. Let T(G) be a spanning tree of G, chosen uniformly at random from all spanning trees. It is a (tricky) theorem that P(e in T(G) and f in T(G)) < P(e in T(G)) P(f in T(G)). This is called decreasing associativity. Now replace T(G) everywhere with F(G), where F(G) is a uniformly chosen forest (so no longer necessarily spanning nor connected). Is the claim still true?

Given a grid graph, say n x m, label each edge as 'valley' or 'mountain'. Find an algorithm to decide if the whole graph can be folded into a single 1x1 pile with creases only along edges, and all respecting the mountain/valley labelings (see here).