Digital Commons Network^™

Seating Groups And 'What A Coincidence!': Mathematics In The Making And How It Gets Presented, Peter J. Rowlett

Journal of Humanistic Mathematics

Mathematics is often presented as a neatly polished finished product, yet its development is messy and often full of mis-steps that could have been avoided with hindsight. An experience with a puzzle illustrates this conflict. The puzzle asks for the probability that a group of four and a group of two are seated adjacently within a hundred seats, and is solved using combinatorics techniques.

An Inquiry Into Lorentzian Polynomials, Tomás Aguilar-Fraga

HMC Senior Theses

In combinatorics, it is often desirable to show that a sequence is unimodal. One method of establishing this is by proving the stronger yet easier-to-prove condition of being log-concave, or even ultra-log-concave. In 2019, Petter Brändén and June Huh introduced the concept of Lorentzian polynomials, an exciting new tool which can help show that ultra-log-concavity holds in specific cases. My thesis investigates these Lorentzian polynomials, asking in which situations they are broadly useful. It covers topics such as matroid theory, discrete convexity, and Mason’s conjecture, a long-standing open problem in matroid theory. In addition, we discuss interesting applications to known …

Counting Spanning Trees On Triangular Lattices, Angie Wang

CMC Senior Theses

This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …

On The Mysteries Of Interpolation Jack Polynomials, Havi Ellers

HMC Senior Theses

Interpolation Jack polynomials are certain symmetric polynomials in N variables with coefficients that are rational functions in another parameter k, indexed by partitions of length at most N. Introduced first in 1996 by F. Knop and S. Sahi, and later studied extensively by Sahi, Knop-Sahi, and Okounkov-Olshanski, they have interesting connections to the representation theory of Lie algebras. Given an interpolation Jack polynomial we would like to differentiate it with respect to the variable k and write the result as a linear combination of other interpolation Jack polynomials where the coefficients are again rational functions in k. In this …

Tropical Derivation Of Cohomology Ring Of Heavy/Light Hassett Spaces, Shiyue Li

HMC Senior Theses

The cohomology of moduli spaces of curves has been extensively studied in classical algebraic geometry. The emergent field of tropical geometry gives new views and combinatorial tools for treating these classical problems. In particular, we study the cohomology of heavy/light Hassett spaces, moduli spaces of heavy/light weighted stable curves, denoted as $\calm_{g, w}$ for a particular genus $g$ and a weight vector $w \in (0, 1]^n$ using tropical geometry. We survey and build on the work of \citet{Cavalieri2014}, which proved that tropical compactification is a \textit{wonderful} compactification of the complement of hyperplane arrangement for these heavy/light Hassett spaces. For $g …

Combinatorial Polynomial Hirsch Conjecture, Sam Miller

HMC Senior Theses

The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the …

Patterns Formed By Coins, Andrey M. Mishchenko

Journal of Humanistic Mathematics

This article is a gentle introduction to the mathematical area known as circle packing, the study of the kinds of patterns that can be formed by configurations of non- overlapping circles. The first half of the article is an exposition of the two most important facts about circle packings, (1) that essentially whatever pattern we ask for, we may always arrange circles in that pattern, and (2) that under simple conditions on the pattern, there is an essentially unique arrangement of circles in that pattern. In the second half of the article, we consider related questions, but where we …

Fibonomial Tilings And Other Up-Down Tilings, Robert Bennett

HMC Senior Theses

The Fibonomial coefficients are a generalization of the binomial coefficients with a rather nice combinatorial interpretation. While the ordinary binomial coefficients count lattice paths in a grid, the Fibonomial coefficients count the number of ways to draw a lattice path in a grid and then Fibonacci-tile the regions above and below the path in a particular way. We may forgo a literal tiling interpretation and, instead of the Fibonacci numbers, use an arbitrary function to count the number of ways to "tile" the regions of the grid delineated by the lattice path. When the function is a combinatorial sequence such …

A Combinatorial Exploration Of Elliptic Curves, Matthew Lam

HMC Senior Theses

At the intersection of algebraic geometry, number theory, and combinatorics, an interesting problem is counting points on an algebraic curve over a finite field. When specialized to the case of elliptic curves, this question leads to a surprising connection with a particular family of graphs. In this document, we present some of the underlying theory and then summarize recent results concerning the aforementioned relationship between elliptic curves and graphs. A few results are additionally further elucidated by theory that was omitted in their original presentation.

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.

A New Framework For Network Disruption, Susan E. Martonosi, Doug Altner, Michael Ernst, Elizabeth Ferme, Kira Langsjoen, Danika Lindsay, Sean S. Plott '08, Andrew S. Ronan

All HMC Faculty Publications and Research

Traditional network disruption approaches focus on disconnecting or lengthening paths in the network. We present a new framework for network disruption that attempts to reroute flow through critical vertices via vertex deletion, under the assumption that this will render those vertices vulnerable to future attacks. We define the load on a critical vertex to be the number of paths in the network that must flow through the vertex. We present graph-theoretic and computational techniques to maximize this load, firstly by removing either a single vertex from the network, secondly by removing a subset of vertices.

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.

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.

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 …

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.

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 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.

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.