| E-mail address sbutler@math.ucsd.edu Office AP&M 6436 Office Hours Mon. 11-12 (Math 20D) Wed. 10:30-12 (Math 20D) |
 |
Advisor Fan Chung Graham Mathematical interests Combinatorics, Graph theory Nonmathematical interests 
,juggling, tai chi, China |
PAPERS |
|
|---|---|
| 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 2x(3n). (Written with Paul Horn and Eric Tressler.)
Preprint. |
| 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.)
Preprint. |
| 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".
Preprint. |
| 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.)
Preprint. |
| 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.)
To appear. |
| 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.)
To appear in Annals of Combinatorics. |
| 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.
Preprint. |
| 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.)
To appear in Annals of Combinatorics. |
| 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. |
| 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. (Two Java programs designed to enumerate such permutations (a, b), were used to generate the initial terms of my first contribution to the encyclopedia of integer sequences: A111053.) |
| 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. To appear in Ars Combinatoria. (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 |
|
| 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!!) |
| 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." |
| Combinatorics reading seminar, Summer 2005 | An archived record of a Combinatorics Reading Seminar held at UCSD in the Summer of 2005, organized by Fan Chung Graham and Steve Butler. |
| 24 squares (color) 24 squares (B&W) METAPOST file |
The 24 distinct ways to color the four "sides" of a square with three colors. The puzzle
is to put them together in a 4x6 array so that adjacent squares have the same color on the sides and the
outside is all of one color (there are 13,328 such solutions). More information can be found in
Martin Gardner's "New Mathematical Diversions", chapter 16. (If the problem is too easy try getting a similar result with the 130 hexagons that are similarly colored (corresponding METAPOST file).) |
| 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). |
| A property of positive semidefinite matrices | A short unpublished note that arose from a question from a Computer Science graduate student. The result itself is 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.) |
| Math 10a Winter 2007 | The homepage for the math 10a course which I taught in Winter 2007. Student comments from that course about me as an instructor. |
| Math 130a Fall 2007 | The homepage for the math 130a course which I served as a TA for in Fall 2007. Student comments from that course about me as a TA. |
| Math 130b Winter 2008 | The homepage for the math 130b course which I served as a TA for in Winter 2008. |