Mathematics Commons^™

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar

All HMC Faculty Publications and Research

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root …

Combinatorics Of Two-Toned Tilings, Arthur T. Benjamin, Phyllis Chinn, Jacob N. Scott '11, Greg Simay

All HMC Faculty Publications and Research

We introduce the function a(r, n) which counts tilings of length n + r that utilize white tiles (whose lengths can vary between 1 and n) and r identical red squares. These tilings are called two-toned tilings. We provide combinatorial proofs of several identities satisfied by a(r, n) and its generalizations, including one that produces kth order Fibonacci numbers. Applications to integer partitions are also provided.

The Combinatorialization Of Linear Recurrences, Arthur T. Benjamin, Halcyon Derks, Jennifer J. Quinn

All HMC Faculty Publications and Research

We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings.

Third And Fourth Binomial Coefficients, Arthur T. Benjamin, Jacob N. Scott '11

All HMC Faculty Publications and Research

While formulas for the sums of kth binomial coefficients can be shown inductively or algebraically, these proofs give little insight into the combinatorics involved. We prove formulas for the sums of 3rd and 4th binomial coefficients via purely combinatorial arguments.

A Census Of Vertices By Generations In Regular Tessellations Of The Plane, Alice Paul '12, Nicholas Pippenger

All HMC Faculty Publications and Research

We consider regular tessellations of the plane as infinite graphs in which q edges and q faces meet at each vertex, and in which p edges and p vertices surround each face. For 1/p + 1/q = 1/2, these are tilings of the Euclidean plane; for 1/p + 1/q < 1/2, they are tilings of the hyperbolic plane. We choose a vertex as the origin, and classify vertices into generations according to their distance (as measured by the number of edges in a shortest path) from the origin. For all p ≥ 3 and q ≥ 3 with 1/p + 1/q ≤ 1/2, we give simple combinatorial derivations of the rational generating functions for the number of vertices in each generation.

Sums Of Evenly Spaced Binomial Coefficients, Arthur T. Benjamin, Bob Chen '10, Kimberly Kindred

All HMC Faculty Publications and Research

We provide a combinatorial proof of a formula for the sum of evenly spaced binomial coefficients. This identity, along with a generalization, are proved by counting weighted walks on a graph.

Combinatorial Trigonometry With Chebyshev Polynomials, Arthur T. Benjamin, Larry Ericksen, Pallavi Jayawant, Mark Shattuck

All HMC Faculty Publications and Research

We provide a combinatorial proof of the trigonometric identity cos(n_{θ) =} T_ncos(θ),
where T_n is the Chebyshev polynomial of the first kind. We also provide combinatorial proofs of other trigonometric identities, including those involving Chebyshev polynomials of the second kind.

Combinatorially Composing Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07

All HMC Faculty Publications and Research

We present a combinatorial proof of two fundamental composition identities associated with Chebyshev polynomials. Namely, for all m, n ≥ 0, T_m(T_n(x)) = T_mn(x) and U_m-1 (T_n(x))U_n-1(x) = U_mn-1(x).

Recognizing Graph Theoretic Properties With Polynomial Ideals, Jesus A. De Loera, Christopher J. Hillar, Peter N. Malkin, Mohamed Omar

All HMC Faculty Publications and Research

Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect k-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Gröbner bases, toric algebra, convex programming, and real algebraic geometry.

Voting, The Symmetric Group, And Representation Theory, Zajj Daugherty '05, Alexander K. Eustis '06, Gregory Minton '08, Michael E. Orrison

All HMC Faculty Publications and Research

We show how voting may be viewed naturally from an algebraic perspective by viewing voting profiles as elements of certain well-studied QS_n-modules. By using only a handful of simple combinatorial objects (e.g., tabloids) and some basic ideas from representation theory (e.g., Schur's Lemma), this allows us to recast and extend some well-known results in the field of voting theory.

Compression Theorems For Periodic Tilings And Consequences, Arthur T. Benjamin, Alex K. Eustis '06, Mark A. Shattuck

All HMC Faculty Publications and Research

We consider a weighted square-and-domino tiling model obtained by assigning real number weights to the cells and boundaries of an n-board. An important special case apparently arises when these weights form periodic sequences. When the weights of an nm-tiling form sequences having period m, it is shown that such a tiling may be regarded as a meta-tiling of length n whose weights have period 1 except for the first cell (i.e., are constant). We term such a contraction of the period in going from the longer to the shorter tiling as "period compression". It turns out that …

Counting On Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07

All HMC Faculty Publications and Research

Chebyshev polynomials have several elegant combinatorial interpretations. Specificially, the Chebyshev polynomials of the first kind are defined by T₀(x) = 1, T₁(x) = x, and T_n(x) = 2x T_n-1(x) - T_n-2(x). Chebyshev polynomials of the second kind U_n(x) are defined the same way, except U₁(x) = 2x. T_n and U_n are shown to count tilings of length n strips with squares and dominoes, where the tiles are given weights and sometimes color. Using these interpretations, many identities satisfied by Chebyshev polynomials can be given …

Tiling Proofs Of Recent Sum Identities Involving Pell Numbers, Arthur T. Benjamin, Sean S. Plott '08, James A. Sellers

All HMC Faculty Publications and Research

In a recent note, Santana and Diaz-Barrero proved a number of sum identities involving the well-known Pell numbers. Their proofs relied heavily on the Binet formula for the Pell numbers. Our goal in this note is to reconsider these identities from a purely combinatorial viewpoint. We provide bijective proofs for each of the results by interpreting the Pell numbers as enumerators of certain types of tilings. In turn, our proofs provide helpful insight for straightforward generalizations of a number of the identities.

An Alternate Approach To Alternating Sums: A Method To Die For, Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

The 99th Fibonacci Identity, Arthur T. Benjamin, Alex K. Eustis '06, Sean S. Plott '08

All HMC Faculty Publications and Research

We provide elementary combinatorial proofs of several Fibonacci and Lucas number identities left open in the book Proofs That Really Count [1], and generalize these to Gibonacci sequences G_n that satisfy the Fibonacci recurrence, but with arbitrary real initial conditions. We offer several new identities as well.

[1] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions, 27, Mathematical Association of America, Washington, DC, 2003

Paint It Black -- A Combinatorial Yawp, Arthur T. Benjamin, Jennifer J. Quinn, James A. Sellers, Mark A. Shattuck

All HMC Faculty Publications and Research

No abstract provided in this paper.

A Combinatorial Approach To Fibonomial Coefficients, Arthur T. Benjamin, Sean S. Plott '08

All HMC Faculty Publications and Research

A combinatorial argument is used to explain the integrality of Fibonomial coefficients and their generalizations. The numerator of the Fibonomial coeffcient counts tilings of staggered lengths, which can be decomposed into a sum of integers, such that each integer is a multiple of the denominator of the Fibonomial coeffcient. By colorizing this argument, we can extend this result from Fibonacci numbers to arbitrary Lucas sequences.

Distribution Of The Number Of Encryptions In Revocation Schemes For Stateless Receivers, Christopher Eagle, Zhicheng Gao, Mohamed Omar, Daniel Panario, Bruce Richmond

All HMC Faculty Publications and Research

We study the number of encryptions necessary to revoke a set of users in the complete subtree scheme (CST) and the subset-difference scheme (SD). These are well-known tree based broadcast encryption schemes. Park and Blake in: Journal of Discrete Algorithms, vol. 4, 2006, pp. 215--238, give the mean number of encryptions for these schemes. We continue their analysis and show that the limiting distribution of the number of encryptions for these schemes is normal. This implies that the mean numbers of Park and Blake are good estimates for the number of necessary encryptions used by these schemes.

Recounting Determinants For A Class Of Hessenberg Matrices, Arthur T. Benjamin, Mark A. Shattuck

All HMC Faculty Publications and Research

We provide combinatorial interpretations for determinants which are Fibonacci numbers of several recently introduced Hessenberg matrices. Our arguments make use of the basic definition of the determinant as a signed sum over the symmetric group.

Solution To Problem 1751, A Combinatorial Identity, Arthur T. Benjamin, Andrew Carman '09

All HMC Faculty Publications and Research

A combinatorial proof to Iliya Bluskov's proposed Problem 1751.

A Combinatorial Proof Of Vandermonde's Determinant, Arthur T. Benjamin, Gregory P. Dresden

All HMC Faculty Publications and Research

No abstract provided in this article.

A Combinatorial Solution To Intertwined Recurrences, Arthur T. Benjamin, Michael D. Hirschhorn

All HMC Faculty Publications and Research

We provide combinatorial derivations of solutions to intertwined second order linear recurrences (such as a_n = pb_n-1 + qa_n-2, b_n = ra_n-1 + sb_n-2) by counting tilings of length n strips with squares and dominoes of various colors and shades. A similar approach can be applied to intertwined third order recurrences with coefficients equal to one. Here we find that all solutions can be expressed in terms of tribonacci numbers. The method can also be easily extended to solve and combinatorially comprehend kth order Fibonacci recurrences.

Fibonacci Deteminants - A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn

All HMC Faculty Publications and Research

In this paper, we provide combinatorial interpretations for some determinantal identities involving Fibonacci numbers. We use the method due to Lindström-Gessel-Viennot in which we count nonintersecting n-routes in carefully chosen digraphs in order to gain insight into the nature of some well-known determinantal identities while allowing room to generalize and discover new ones.

Summing Cubes By Counting Rectangles, Arthur T. Benjamin, Jennifer J. Quinn, Calyssa Wurtz

All HMC Faculty Publications and Research

No abstract provided in this article.

Self-Avoiding Walks And Fibonacci Numbers, Arthur T. Benjamin

All HMC Faculty Publications and Research

By combinatorial arguments, we prove that the number of self-avoiding walks on the strip {0, 1} × Z is 8F_n − 4 when n is odd and is 8F_n − n when n is even. Also, when backwards moves are prohibited, we derive simple expressions for the number of length n self-avoiding walks on {0, 1} × Z, Z × Z, the triangular lattice, and the cubic lattice.

The Linear Complexity Of A Graph, David L. Neel, Michael E. Orrison Jr.

All HMC Faculty Publications and Research

The linear complexity of a matrix is a measure of the number of additions, subtractions, and scalar multiplications required to multiply that matrix and an arbitrary vector. In this paper, we define the linear complexity of a graph to be the linear complexity of any one of its associated adjacency matrices. We then compute or give upper bounds for the linear complexity of several classes of graphs.

Combinatorial Interpretations Of Spanning Tree Identities, Arthur T. Benjamin, Carl R. Yerger

All HMC Faculty Publications and Research

We present a combinatorial proof that the wheel graph Wn has L2n − 2 spanning trees, where Ln is the nth Lucas number, and that the number of spanning trees of a related graph is a Fibonacci number. Our proofs avoid the use of induction, determinants, or the matrix tree theorem.

The Linking Probability Of Deep Spider-Web Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

We consider crossbar switching networks with base b (that is, constructed from b x b crossbar switches), scale k (that is, with b^k inputs, b^k outputs, and b^k links between each consecutive pair of stages), and depth l (that is, with l stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least k stages. We assume that each vertex is independently idle with probability q, the vacancy probability. We assume that b ≥ 2 and the vacancy probability q are fixed, and that k …

Pythagorean Primes And Palindromic Continued Fractions, Arthur T. Benjamin, Doron Zeilberger

All HMC Faculty Publications and Research

In this note, we prove that every prime of the form 4m + 1 is the sum of the squares of two positive integers in a unique way. Our proof is based on elementary combinatorial properties of continued fractions. It uses an idea by Henry J. S. Smith ([3], [5], and [6]) most recently described in [4] (which provides a new proof of uniqueness and reprints Smith's paper in the original Latin). Smith's proof makes heavy use of nontrivial properties of determinants. Our purely combinatorial proof is self-contained and elementary.

Recounting The Odds Of An Even Derangement, Arthur T. Benjamin, Curtis D. Bennet, Florence Newberger

All HMC Faculty Publications and Research

No abstract provided in this article.