Source author record

Steve Butler

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT Discrete Mathematics math.HO

Catalog footprint

Research overview

17works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Complements of coalescing sets

We consider matrices of the form $qD+A$ , with $D$ being the diagonal matrix of degrees, $A$ being the adjacency matrix, and $q$ a fixed value. Given a graph $H$ and $B\subseteq V(G)$ , which we call a coalescent pair $(H,B)$ , we derive a formula for the characteristic polynomial where a copy of same rooted graph $G$ is attached by the root to \emph{each} vertex of $B$ . Moreover, we establish if $(H_1,B_1)$ and $(H_2,B_2)$ are two coalescent pairs which are cospectral for any possible rooted graph $G$ , then $(H_1,V(H_1)\setminus B_1)$ and $(H_2,V(H_2)\setminus B_2)$ will also always be cospectral for any possible rooted graph $G$ .

preprint2020arXiv

Hadamard diagonalizable graphs of order at most 36

If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $\pm1$ , then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$ , $K_{n/2,n/2}$ , $2K_{n/2}$ , and $nK_1$ , and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.

preprint2016arXiv

Rainbow arithmetic progressions

In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$ , the expression $aw([n],k)$ denotes the smallest number of colors with which the integers $\{1,\ldots,n\}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$ . We establish that $aw([n],3)=Θ(\log n)$ and $aw([n],k)=n^{1-o(1)}$ for $k\geq 4$ . For positive integers $n$ and $k$ , the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$ . In this setting, arithmetic progressions can "wrap around," and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$ , depending on the divisibility of $n$ . As shown in [Jungić et al., \textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$ . We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$ . However, for $k\geq 4$ , the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$ .

preprint2015arXiv

A cospectral family of graphs for the normalized Laplacian found by toggling

We give a construction of a family of (weighted) graphs that are pairwise cospectral with respect to the normalized Laplacian matrix, or equivalently probability transition matrix. This construction can be used to form pairs of cospectral graphs with differing number of edges, including situations where one graph is a subgraph of the other. The method used to demonstrate cospectrality is by showing the characteristic polynomials are equal.

preprint2015arXiv

Counting prime juggling patterns

Juggling patterns can be described by a closed walk in a (directed) state graph, where each vertex (or state) is a landing pattern for the balls and directed edges connect states that can occur consecutively. The number of such patterns of length $n$ is well known, but a long-standing problem is to count the number of prime juggling patterns (those juggling patterns corresponding to cycles in the state graph). For the case of $b=2$ balls we give an expression for the number of prime juggling patterns of length $n$ by establishing a connection with partitions of $n$ into distinct parts. From this we show the number of two-ball prime juggling patterns of length $n$ is $(γ-o(1))2^n$ where $γ=1.32963879259...$ . For larger $b$ we show there are at least $b^{n-1}$ prime cycles of length $n$ .

preprint2015arXiv

Juggling card sequences

Juggling patterns can be described by a sequence of cards which keep track of the relative order of the balls at each step. This interpretation has many algebraic and combinatorial properties, with connections to Stirling numbers, Dyck paths, Narayana numbers, boson normal ordering, arc-labeled digraphs, and more. Some of these connections are investigated with a particular focus on enumerating juggling patterns satisfying certain ordering constraints, including where the number of crossings is fixed.

preprint2015arXiv

Partition and sum is fast

We consider the following "partition and sum" operation on a natural number: Treating the number as a long string of digits insert several plus signs in between some of the digits and carry out the indicated sum. This results in a smaller number and repeated application can always reduce the number to a single digit. We show that surprisingly few iterations of this operation are needed to get down to a single digit.

preprint2014arXiv

The mathematics of the flip and horseshoe shuffles

We consider new types of perfect shuffles wherein a deck is split in half, one half of the deck is "reversed", and then the cards are interlaced. Flip shuffles are when the reversal comes from flipping the half over so that we also need to account for face-up/face-down configurations while horseshoe shuffles are when the order of the cards are reversed but all cards still face the same direction. We show that these shuffles are closely related to faro shuffling and determine the order of the associated shuffling groups.

preprint2014arXiv

Using twins and scaling to construct cospectral graphs for the normalized Laplacian

The spectrum of the normalized Laplacian matrix cannot determine the number of edges in a graph, however finding constructions of cospectral graphs with differing number of edges has been elusive. In this paper we use basic properties of twins and scaling to show how to construct such graphs. We also give examples of families of graphs which are cospectral with a subgraph for the normalized Laplacian matrix.

preprint2012arXiv

A construction of cospectral graphs for the normalized Laplacian

We give a method to construct cospectral graphs for the normalized Laplacian by a local modification in some graphs with special structure. Namely, under some simple assumptions, we can replace a small bipartite graph with a cospectral mate without changing the spectrum of the entire graph. We also consider a related result for swapping out biregular bipartite graphs for the matrix $A+tD$ . We produce (exponentially) large families of non-bipartite, non-regular graphs which are mutually cospectral, and also give an example of a graph which is cospectral with its complement but is not self-complementary.

preprint2012arXiv

Unrolling residues to avoid progressions

We consider the problem of coloring $[n]={1,2,...,n}$ with $r$ colors to minimize the number of monochromatic $k$ term arithmetic progressions (or $k$ -APs for short). We show how to extend colorings of $\mathbb{Z}_m$ which avoid nontrivial $k$ -APs to colorings of $[n]$ by an unrolling process. In particular, by using residues to color $\mathbb{Z}_m$ we produce the best known colorings for minimizing the number of monochromatic $k$ -APs for coloring with $r$ colors for several small values of $r$ and $k$ .

preprint2012arXiv

Zero forcing for inertia sets

Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few "unforced" moves as possible. This leads to a parameter known as the zero forcing number which can be used to give an upper bound for the maximum nullity of a matrix associated with the graph. We introduce a new variation on the zero forcing game which can be used to give an upper bound for the maximum nullity of a matrix associated with a graph that has $q$ negative eigenvalues. This gives some limits to the number of positive eigenvalues that such a graph can have and so can be used to form lower bounds for the inertia set of a graph.

preprint2010arXiv

Hypercube orientations with only two in-degrees

We consider the problem of orienting the edges of the $n$ -dimensional hypercube so only two different in-degrees $a$ and $b$ occur. We show that this can be done, for two specified in-degrees, if and only if an obvious necessary condition holds. Namely, there exist non-negative integers $s$ and $t$ so that $s+t=2^n$ and $as+bt=n2^{n-1}$ . This is connected to a question arising from constructing a strategy for a "hat puzzle."

preprint2010arXiv

Origami rings

Motivated by a question in origami, we consider sets of points in the complex plane constructed in the following way. Let $L_α(p)$ be the line in the complex plane through $p$ with angle $α$ (with respect to the real axis). Given a fixed collection $U$ of angles, let $\RU$ be the points that can be obtained by starting with $0$ and $1$ , and then recursively adding intersection points of the form $L_α(p) \cap L_β(q)$ , where $p, q$ have been constructed already, and $α, β$ are distinct angles in $U$ . Our main result is that if $U$ is a group with at least three elements, then $\RU$ is a subring of the complex plane, i.e., it is closed under complex addition and multiplication. This enables us to answer a specific question about origami folds: if $n \ge 3$ and the allowable angles are the $n$ equally spaced angles $kπ/n$ , $0 \le k < n$ , then $\RU$ is the ring $\Z[ζ_n]$ if $n$ is prime, and the ring $\Z[1/n,ζ_{n}]$ if $n$ is not prime, where $ζ_n := \exp(2πi/n)$ is a primitive $n$ -th root of unity.

preprint2010arXiv

Shuffling with ordered cards

We consider a problem of shuffling a deck of cards with ordered labels. Namely we split the deck of N=k^tq cards (where t>=1 is maximal) into k equally sized stacks and then take the top card off of each stack and sort them by the order of their labels and add them to the shuffled stack. We show how to find stacks of cards invariant and periodic under the shuffling. We also show when gcd(q,k)=1 the possible periods of this shuffling are all divisors of order_k(N-q).

preprint2010arXiv

Subdivision by bisectors is dense in the space of all triangles

Starting with any nondegenerate triangle we can use a well defined interior point of the triangle to subdivide it into six smaller triangles. We can repeat this process with each new triangle, and continue doing so over and over. We show that starting with any arbitrary triangle, the resulting set of triangles formed by this process contains triangles arbitrarily close (up to similarity) any given triangle when the point that we use to subdivide is the incenter. We also show that the smallest angle in a "typical" triangle after repeated subdivision for many generations does not have the smallest angle going to zero.

preprint2010arXiv

The art of juggling with two balls or A proof for a modular condition of Lucas numbers

In this short note we look at the problem of counting juggling patterns with one ball or two balls with a throw at every occurrence. We will do this for both traditional juggling and for spherical juggling. In the latter case we will show a connection to the "associated Mersenne numbers" (A001350) and so as a result will be able to recover a proof that the $p$ th Lucas number is congruent to 1 modulo p when p is a prime.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Steve Butler

Research overview

Is this your work?

17 publications

Complements of coalescing sets

Hadamard diagonalizable graphs of order at most 36

Rainbow arithmetic progressions

A cospectral family of graphs for the normalized Laplacian found by toggling

Counting prime juggling patterns

Juggling card sequences

Partition and sum is fast

The mathematics of the flip and horseshoe shuffles

Using twins and scaling to construct cospectral graphs for the normalized Laplacian

A construction of cospectral graphs for the normalized Laplacian

Unrolling residues to avoid progressions

Zero forcing for inertia sets

Hypercube orientations with only two in-degrees

Origami rings

Shuffling with ordered cards

Subdivision by bisectors is dense in the space of all triangles

The art of juggling with two balls or A proof for a modular condition of Lucas numbers

See the researcher in context

Building this map preview