| E-mail address butler@math.ucla.edu Office MS 6236 Office Hours By appointment |
More videos available on YouTube |
Mathematical interests Combinatorics, Graph theory, discrete geometry Nonmathematical interests 
,juggling, tai chi, unicycling |
PAPERS |
|
|---|---|
| Origami rings | We determine the set of points in the complex plane that can iteratively be constructed starting with 0 and 1 and taking lines with slopes 360/n and intersection of lines. (Written with Joe Buhler, Warwick de Launey and Ron Graham.) |
| Computing inertia sets using atoms | For a given graph we associate a zero/nonzero (symmetric) matrix pattern by letting an off-diagonal entry be nonzero if and only if the corresponding edge is in the graph. We then consider the number of possible positive and negative eigenvalues that is possible for a matrix with this pattern. In particular, we are able to do this for all graphs up through seven vertices by breaking it into smaller simpler graphs, atoms, which are 3-connected graphs which are not joins. (Written with Wayne Barrett, Tracy Hall, John Sinkovic, Wasin So, Colin Starr and Amy Yielding.) |
| A note on marking lines in [k]n | For each line in [k]n we designate (or mark) a single point on that line. We consider the problem of whether it is possible to mark the lines in such a way so that each point gets marked either a or b times for some fixed values a and b. For n at most 5 we show that the necessary conditions for such a marking to occur are also sufficient. (Written with Ron Graham.) |
| Constructing cospectral graphs for the normalized Laplacian | We give a method to construct cospectral graphs for the normalized Laplacian by swapping edges between vertices in some special graphs. We also are able to show how to construct arbitrarily large families of mutually cospectral graphs for the normalized Laplacian which are not bipartite or regular. (Written with Jason Grout.) |
| Constructing points through folding and intersection | Starting with the two points (0,0) and (1,0) we consider what set of points can be constructed via the following two operations. Folding: through an existing point form a new line with an angle of 180i/n degrees for some i. Intersecting: take the intersection of two existing lines. In particular, we determine all such points for n=3,4,5,6,8,10,12,24 and show how to efficiently construct them. (Written with Erik Demaine, Ron Graham and Tomohiro Tachi.) |
| Hypercube orientations with only two in-degrees | We show that it is possible to orient the edges of the n-cube so that only the in-degrees a and b occur if and only if there are non-negative integers s and t so that s+t=2n and as+bt=n2n-1. This is connected to a question arising from constructing strategies for a type of hat game. (Written with Joe Buhler, Ron Graham and Eric Tressler.) |
| Subdivision by bisectors is dense in the space of all triangles | Starting with a triangle we subdivide it into six smaller triangles by using the angle bisectors. When we iterate this process and look at all triangles that we formed the resulting set is dense in the space of all triangles (regardless of what triangle we began with). A similar result is known for medians, but unlike medians most of the triangles do not become degenerate. (Written with Ron Graham.) |
| Shuffling with ordered cards | We consider a problem of shuffling a deck of cards with ordered labels. Namely we split the deck of N=ktq cards (where t>0 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 orderk(N-q). (Written with Ron Graham.)
Journal of Combinatorics 1 (2010), 121-139. |
| An interstice relationship for flowers with four petals | We show that for a circle "surrounded" by four circles, that if we draw the four resulting orthogonal circles they satisfy one of two relationships. We give a geometric as well as algebraic proof of this fact, and as an application introduce G-packings. (Written with Ron Graham, Gerhard Guettler and Colin Mallows.)
Preprint. |
| A note on nested sums | We consider several nested sums, and show how binomial coefficients, Stirling numbers of the second kind and Gaussian binomial coefficients can be written as nested sums. We use this to find the rate of growth for diagonals of Stirling numbers of the second kind as well as another proof of a known identity for Gaussian binomial coefficients. (Written with Pavel Karasik.)
Journal of Integer Sequences 13 (2010), article 10.4.4, 8 pp. |
| Tiling polygons with lattice triangles | A triangle with coordinates of the vertices all integer are called lattice triangles. In this note we consider the location of the vertices of a tiling of a polygon using lattice triangles. In particular we show that if the polygon has rational coordinates for its vertices with one vertex at the origin and an incident vertex on the x-axis then the vertices have rational coordinates with all the possible denominators odd and the prime factors dependant on the cotangents of the angles. (Written with Fan Chung, Ron Graham and Miklos Laczkovich.)
Discrete & Computational Geometry 44 (2010), 896-903. |
| Finding patterns avoiding many monochromatic constellations | Fix some set of points. Then a constellation in [n] is a scaled translated copy of the points. Given a 2-coloring of [n] there must be some monochromatic copies of any fixed constellation (assuming n is sufficiently large). In this paper we outline a method to experimentally find a block coloring of [n] that avoids many monochromatic copies of the constellation. We also show that for constellations with three points we can always beat random coloring. (Written with Kevin Costello and Ron Graham.)
A MAPLE worksheet used to find coefficients of block patterns and also to do local perturbation of block patterns. (An expanded worksheet that includes some good block patterns.) JAVA programs for finding good block patterns for four term arithmetic progressions and for constellations of form [0,q,1]. An interactive JAVA applet related to the paper. Experimental Mathematics 19 (2010), 399-411. |
| Irreducible Apollonian configurations and packings | Apollonian configurations look at ways to pack circles in the plane so that the complement of the circles consist of curvilinear triangles. Often times these are formed by starting with a single set of three circles and then repeatedly filling in curvilinear triangles by a set rule, these rules are based on irreducible Apollonian configurations. This paper looks at the basic way to take these configurations and form recursive rules. It also shows that we can stay in a field all the way down. (Written with Ron Graham, Gerhard Guettler and Colin Mallows.)
Collection of irreducible representations in canonical form. A MAPLE worksheet used to find centers and radii of a standard packing. A collection of adjacency lists for irreducible configurations with between 10 and 15 circles. Discrete & Computational Geometry 44 (2010), 487-506. |
| The lost daughters of Gergonne | Given a triangle and a well defined center point it is easy to split the triangle into six "daughter" triangles. Here we look at going in reverse where we have a triangle S and we want to construct a triangle T so that S is a daughter triangle of T when using the center point. This can easily be done for the incenter and the median. In this note we show how to do it for the Gergonne point.
Forum Geometricorum, 9 (2009), 19-26. |
| Iterated triangle partitions | Given a triangle there are many well defined points associated with it (i.e., the incenter, the centroid, the Gergonne point, the Lemoine point and so on). Using such a point we can split a triangle into smaller triangles by drawing the Cevians, and then we can iterate the process of subdividing on each of the smaller triangles using the same defined point for that triangle and so on and so on. The question then becomes what can be said about one of these "typical" triangles after you repeat this process many times? The answer turns out to depend critically on what point you are using to subdivide. (Written with Ron Graham.)
Fete of Combinatorics and Computer Science, G. Katona, A. Schrijver, T. Szonyi, eds., Bolyai Society Mathematical Studies 29, Springer-Verlag, Heidelberg (2010), 23-42. |
| Jumping sequences | This is a follow up paper to "Optimal jumping patterns". Given a weight function for how to make a jump one can easily construct a sequence which produces weight minimal jumps from n to 1. Given such a sequence we can sieve it by looking at what terms can show up at depth 1,2,3,.... By starting with the right weight function we can sieve to interesting sets; in this paper we show that for the weight function w(i,j)=(i+j)/i2 the sequence it sieves to is the set of Pell numbers. (Written with Ron Graham and Nan Zang.)
Journal of Integer Sequences, 11 (2008), article 08.4.5, 13 pp. |
| Eigenvalues and Structures of Graphs | My dissertation written for my Ph. D. at UC San Diego. This combines a number of my previous papers which focuses on discrepancy of graphs, 2-edge-coverings with applications, and interlacing of graphs. It includes many results not contained elsewhere in my paper list. Finished in the spring quarter of 2008. |
| Intersecting domino tilings | This is a variant of an Erdos-Ko-Rado problem where we consider tilings of regions by dominos. Two tilings intersect if there is a domino that is in the same position in both tilings. A natural question is what is the largest collection of tilings so that any two of them intersect. We give a complete answer for regions that are strips of size 2xn and 3x(2n). (Written with Paul Horn and Eric Tressler.)
The Fibonacci Quarterly 48 (2010), 114-120. |
| Optimal jumping patterns | This paper looks at the problem of minimizing movement from 1 to N where each move has an associated cost. The main result is to show that if the cost of moving from a to b is (1-qb)/a for 0<q<1, then the moves are jumps with ratios between √2 and 19/4. (Written with Ron Graham and Nan Zang.)
Journal of Combinatorics and Number Theory 1 (2009), 1-13. |
| Cospectral graphs for both the adjacency and normalized Laplacian matrices | By "unfolding" a bipartite graph in two different ways it is possible to construct two distinct graphs which are cospectral with respect to both the adjacency and normalized Laplacian matrices at the same time. This gives a simple application for the results in the paper "Eigenvalues of 2-edge-coverings".
Linear and Multilinear Algebra 58 (2010), 387-390. |
| Eigenvalues of 2-edge-coverings | We say G is a 2-edge-covering of H if there is an onto homomorphism which covers each edge twice and so that edges can be lifted back. In this paper we consider how to find the eigenvalues of
G by using a modified form of H and another graph which we term the anti-cover. Several examples are shown and the difficulty of hearing the sound
of a graph using the normalized Laplacian is discussed. (A previous version of the paper with a slightly different approach and some interesting linear algebra results.)
Linear and Multilinear Algebra 58 (2010), 413-423. |
| Interlacing for weighted graphs using the normalized Laplacian | A short paper strengthening results of Chen et al. about the
interlacing of eigenvalues for the normalized Laplacian when removing a subgraph
from a graph. In addition the paper gives an interlacing result for weak covers
and also gives a non-example for interlacing for directed graphs as well as giving
an underlying connection for the Laplacian of directed graphs (as defined by Chung) with the Laplacian
for undirected graphs. [A small library
of digraphs and their corresponding eigenvalues is available for pleaying with (you might notice an unusual number of
graphs which share half of their spectrum).]
Electronic Journal of Linear Algebra 16 (March 2007), 90-98. |
| How to play the majority game with liars | The majority game involves two players one who holds n objects labeled 0 or 1 and
another who asks questions comparing two of the objects. The goal of the person asking questions is
to find one object (if it exists) which has a label which is most common (i.e., in the majority), the
goal of the person answering the questions is to make this as hard as possible. In this paper we consider
the added layer of allowing the person answering to lie some number of times and compute upper and
lower bounds on how many questions it takes to win.
(Written with Ron Graham and Jia Mao.)
AAIM 2007, Lecture Notes in Computer Science 4508, Springer-Verlag, Heidelberg, M.-Y. Kao and X.-Y. Li, eds. (2007), 221-230. |
| How to play the majority game with a liar | The complete version of the above paper (including proofs for lower bounds).
(Written with Ron Graham and Jia Mao.)
Discrete Mathematics 310 (6 February 2010), 622-629. |
| Enumerating (multiplex) juggling sequences | We give a method for enumerating certain types of multiplex juggling sequences.
This extends earlier work due to Fan Chung and Ron Graham.
(Written with Ron Graham.)
Annals of Combinatorics 13 (2010), 413-424. |
| Induced-universal graphs for graphs with bounded maximum degree | We give an explicit construction of a graph for which all graphs with bounded degree
appear as an induced subgraph. The paper is almost entirely self contained and only uses Hall's Marriage
Theorem to derive the result. This extends earlier work due to Fan Chung.
Graphs and Combinatorics 25 (2009), 461-468. |
| Small spectral gap in the combinatorial Laplacian implies Hamiltonian | The title is highly descriptive. The results are an extension of
work of Krivelevich and Sudakov who had established a similar result for
regular graphs using the spectrum of the adjacency matrix.
(Written with Fan Chung.)
Annals of Combinatorics 13 (2010), 403-412. |
| Hat guessing games | A problem from recreational mathematics dealing with finding optimal deterministic
strategies for players trying to guess what kind of hat they are wearing. (Written with Mohammad Hajiaghayi,
Robert Kleinberg, and Tom Leighton.)
SIAM Journal on Discrete Mathematics 22 (2008), 592-605. SIAM Review 51 (2009), 399-413. |
| Using discrepancy to control singular values for nonnegative matrices | Gives a connection between the second largest singular values and the discrepancy of
a matrix. The results are used to show how singular values of the normalized adjacenccy matrix
can control the distribution of
alternating walks on (directed) graphs. Linear Algebra and its Applications 419 (1 December 2006), 486-493. |
| Zero forcing sets and the minimum rank of graphs | This is a joint paper coming out of an AIM conference held in the Fall of 2006 that looks at ways to calculate the minimum rank of some special types of graphs (i.e., the minimum rank of graphs satisfying restricted zero/nonzero patterns as governed by the graph). (Written by the AIM minimum rank research group of which I am one of eighteen members.) Linear Algebra and its Applications 428 (1 April 2008), 1628-1648. |
| Forest-like permutations | A simple rule for associating a labeled graph to a permutation leads to many interesting problems.
In this paper we give necessary and sufficient conditions for the graph to be a forest. We also give an
enumeration of when these graphs are forests, trees, paths, and "smooth". (Written with Mireille Bousquet-Melou.) Annals of Combinatorics 11 (2007), 335-354. |
| Estimating the number of graphs containing very long induced paths | We give upper and lower bounds for the number of graphs containing very long induced paths
(very long in the sense that it involves all but k of the vertices). For fixed k we give
an asymptotic estimation for the number of paths containing these long induced graphs as the number of vertices
gets large. Ars Combinatoria 88 (2008), 321-332. (This is a condensed version of my Master's Thesis.) |
| Relating singular values and discrepancy of weighted directed graphs | Gives a connection between the second largest singular values and the distribution of
edges for weighted directed graphs. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, FL, 2006), 1112-1116, SIAM, Philadelphia, PA, 2006. |
| Tangent line transformations | Gives a simple map from a smooth curve to another smooth curve using a simple rule involving tangent lines.
The amazing property is that when applied twice you get back the original curve flipped around the y-axis.
The College Mathematics Journal 34 (2003), 105-106. (A longer version which includes more details.) |
| Problems | A collection of posed problems which have appeared in print. Includes American Mathematical Monthly #11030, #11265 and Mathematics Magazine #1668, #1730, #1761 |
TALKS |
|
| January 19, 2011 | "Avoiding monochromatic constellations" Colloquim, Michigan Technological University |
| January 7, 2011 | "Hypercube orientations with only two in-degrees" (slides) 2011 Joint Mathematics Meeting |
| December 16, 2010 | "Shuffling with ordered cards" 2010 Western Number Theory Conference |
| November 19, 2010 | "Hat guessing games and orienting hypercubes" Drake University |
| November 17, 2010 | "Iterated triangle partitions" Drake University |
| November 16, 2010 | "Hat guessing games and orienting hypercubes" Discrete mathematics seminar, Iowa State University |
| November 2, 2010 | "Orienting the edges of the hypercube with only two in-degrees" Combinatorics seminar, UC San Diego |
| June 17, 2010 | "Cospectral graphs for the normalized Laplacian" (slides) 2010 SIAM Conference on Discrete Mathematics |
| April 11, 2010 | "How to find a two coloring of {1,2,...,n} that has few monochromatic constellations" AMS 2010 Spring Central Section Meeting |
| March 23, 2010 | "Shuffling with ordered cards" (slides) Combinatorics, Groups, Algorithms, and Complexity; Conference in honor of Laci Babai's 60th birthday |
| January 21, 2010 | "Finding patterns that do not contain many monochromatic constellations" UC-Los Angeles, Combinatorics Seminar |
| January 12, 2010 | "Finding patterns that do not contain many monochromatic constellations" UC-San Diego, Combinatorics Seminar |
| November 7, 2009 | "Finding patterns avoiding many monochromatic constellations" (slides) AMS 2009 Fall Western Section Meeting |
| October 16, 2009 | "Tiling polygons with lattice triangles" (slides) INTEGERS Conference 2009, University of West Georgia |
| October 23, 2008 | "Jumping sequences" UC-Los Angeles, Combinatorics Seminar |
| October 14, 2008 | "Jumping sequences" (slides) UC-San Diego, Combinatorics Seminar |
| August 13, 2008 | "Iterated partitions of triangles" The 20th Canadian Conference on Computational Geometry. McGill University. (Co-presenter with Ron Graham) |
| June 16, 2008 | "Eigenvalues of 2-edge Coverings" (slides) SIAM Conference on Discrete Mathematics (DM08) |
| May 27, 2008 | "Dissertation defense" (slides) Final defense for Ph. D. |
| May 16, 2008 | "Iterated triangle partitions"
The Mathematical Interests of Peter Borwein. IRMACS. (Co-presenter with Ron Graham) |
| April 12, 2008 | "An Erdos-Ko-Rado problem on the strip" (slides) GSCC 2008 |
| March 24, 2008 | "Constructing small induced universal graphs for graphs with bounded maximum degree" BYU, colloquium |
| January 8, 2008 | "Induced-universal graphs for graphs with bounded maximum degree" AMS/MAA Joint Meeting, San Diego, CA |
| December 9, 2007 | "Eigenvalues of 2-edge-coverings" CMS Winter 2007 Meeting |
| June 22, 2007 | "Induced universal graphs" (slides) SDSU |
| June 7, 2007 | "How to play the majority game with liars" (slides) AAIM07 |
| May 22, 2007 | "Anti-covers of graphs" UC-San Diego, Combinatorics seminar |
| April 21, 2007 | "Induced-universal graphs for graphs with bounded maximum degree" AMS Sectional Meetings, Tucson, AZ |
| January 7, 2007 | "The Moebius transform of the triangular numbers" AMS/MAA Joint Meeting, New Orleans, LA |
| September 2006 | "Spectral graph theory" (notes) A series of lectures delivered at the Center for Combinatorics at Nankai University, Tianjin, China |
| July 19, 2006 | "Enumerating (multiplex) juggling sequences" Horizon of Combinatorics |
| July 10, 2006 | "Induced-universal graphs for graphs with bounded maximum degree" Sixth Czech-Slovak International Symposium |
| July 6, 2006 | "Enumerating (multiplex) juggling sequences" UC-San Diego, Combinatorics seminar |
| April 4, 2006 | "Induced-universal graphs for graphs with bounded maximum degree" UC-San Diego, Combinatorics seminar |
| January 24, 2006 | "Relating singular values and discrepancy of weighted directed graphs" ACM-SIAM Symposium on Discrete Algorithms, Miami, FL |
| January 13, 2006 | "The limited hats game" AMS/MAA Joint Meeting, San Antonio, TX |
| November 10, 2005 | "On permutations which avoid the patterns 1324 and (bar 2143)" Caltech, Combinatorics Seminar |
| November 8, 2005 | "A hat guessing game" UC-San Diego, Combinatorics seminar |
| November 2, 2005 | "A hypercube approach to a hats guessing game" UC-San Diego, Graduate student research colloquium |
| October 30, 2005 | "Constructing balanced strategies for the hats game" Integers Conference 2005, University of West Georgia |
| September 24, 2005 | "Relating eigenvalues and discrepancies of graphs" Midwestern Graph Theory Conference XLI, Middle Tennessee State University |
| June 23, 2005 | "Cycle avoidance in hypercubes" UC-San Diego, Combinatorics reading seminar |
| June 15, 2005 | "On discrepancy and singular values of a graph" UC-San Diego, Advancement to candidacy talk |
| April 19, 2005 | "On permutations which are 1324 and (bar 2143) avoiding" UC-San Diego, Combinatorics Seminar |
| March 14, 2005 | "On permutations which are 1324 and (bar 2143) avoiding" UC-Berkeley, Combinatorics Seminar |
MISCELLANEOUS |
|
 |
A slideshow featuring pictures of my beautiful wife, Zou Yang. (Contrary to popular belief, even mathematicians can attract beautiful women!!) |
| Lecture notes in combinatorics (Math 180) | A set of lecture notes written for the Math 180 course taught at UCLA in Spring 2009. |
| The Combinatorics of Patterns in Subsets and Graphs | This is a collection of lecture notes written by students in Fan Chung Graham's Math 262 course held in the fall of 2004. The focus of the notes is mostly on the regularity lemma of Szemeredi and its applications. | Notes From Trigonometry | This is a trigonometry book developed while teaching at Brigham Young University (BYU). These notes develop trigonometry from a geometric/intuitive perspective. |
| Letter to the editor | A letter published in BYU's student newspaper in response to a university fund-raising campaign using the slogan "$1=$6. Do the math." |
| Determining the underlying functions for the Cauchy power and exponential forms | A short unpublished note that resulted from research done with Dr. Donald Snow of BYU in the summer of 2000. It shows, for example, how given a function u(x,y) to find (if it exists) a function f so that u(x,y)= f(x+y)-f(x)f(y). |
| Method for doing the (approximate) Markov chains for bisection | A short unpublished note related to the paper "Iterated triange partitions" that mimics a Markov chain for bisection. It is not a true Markov chain but seems to work fairly well. |
| A property of positive semidefinite matrices | A short unpublished note that arose from a question from a Computer Science graduate student. The result itself was not quite strong enough for his application, but proved interesting in its own right. |
| A new discrepancy definition for hypergraphs | A short unpublished note that generalizes the definition of discrepancy to hypergraphs (note discrepancy has been generalized before, this version however still allows us to work with square matrices). Much work remains to be done in this direction. |
| Relating the arboricity with the chromatic number of a graph | A short unpublished note that connects the arboricity of a graph (i.e., the minimum number of forests the edges can be decomposed into) with the chromatic number of the graph (i.e., the minimum number of colors needed to color the vertices so no two adjacent vertices are colored the dame). Undoubtedly this has been done before, but since I don't know where, and I like the result, I am including it here. |
| Generalizing some results to the normalized Laplacian | In spectral graph theory working with the normalized Laplacian allows us more flexibility in some situations then working with the combinatorial Laplacian (and usually at only the cost of a little more bookkeeping). This note discusses gives some simple examples, and includes a nice definition for discrepancy of bipartite graphs. |
| The Moebius transform of the triangular numbers | A short proof-without-words type result that gives an interpretation of the Moebius transform of the triangular numbers which also can be easily generalized to higher dimensions. (A longer note form of the result.) |
| 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 known proof that the pth Lucas number is congruent to 1 modulo p when p is a prime. |
| Old course pages |
Math 61 (Fall 2008) course webpage Math 3b (Winter 2009) course webpage Math 180 (Spring 2009) course webpage Math 31a (Winter 2010) course webpage Math 32a (Spring 2010) course webpage |