Discrete Mathematics and Combinatorics Commons^™

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.

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.

The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn

Faculty Publications

The (r, d)-relaxed coloring game is a two-player game played on the vertex set of a graph G. We consider a natural analogue to this game on the edge set of G called the (r, d)-relaxed edge-coloring game. We consider this game on trees and more generally, on k-degenerate graphs. We show that if G is k-degenerate with ∆(G) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆+k−1 and d≥2k² + 4k.

Towards The Computation Of The Convex Hull Of A Configuration From Its Corresponding Separating Matrix, Elie Feder, David Garber

Publications and Research

In this paper we cope with the following problem compute the size of the convex hull of a configuration C where the given data is the number of separating lines between any two points of the configuration (where the lines are generated by pairs of other points of the configuration)

We give an algorithm for the case that the convex hull is of size 3 and a partial algorithm and some directions for the case that the convex hull is of size bigger than 3.

Carathéodory Functions In The Banach Space Setting, Daniel Alpay, Olga Timoshenko, Dan Volok

Mathematics, Physics, and Computer Science Faculty Articles and Research

We prove representation theorems for Carathéodory functions in the setting of Banach spaces.

Efficient Domination In Knights Graphs, Anne Sinko, Peter J. Slater

Mathematics Faculty Publications

The influence of a vertex set S ⊆V(G) is I(S) = Σ_v∈S(1 + deg(v)) = Σ_v∈S |N[v]|, which is the total amount of domination done by the vertices in S. The efficient domination number F(G) of a graph G is equal to the maximum influence of a packing, that is, F(G) is the maximum number of vertices one can dominate under the restriction that no vertex gets dominated more than once.

In …

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.

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.

The Zeta Function Of A Hypergraph, Christopher K. Storm

Dartmouth Scholarship

We generalize the Ihara-Selberg zeta function to hypergraphs in a natural way. Hashimoto's factorization results for biregular bipartite graphs apply, leading to exact factorizations. For $(d,r)$-regular hypergraphs, we show that a modified Riemann hypothesis is true if and only if the hypergraph is Ramanujan in the sense of Winnie Li and Patrick Solé. Finally, we give an example to show how the generalized zeta function can be applied to graphs to distinguish non-isomorphic graphs with the same Ihara-Selberg zeta function.

Double Domination Edge Critical Graphs., Derrick Wayne Thacker

Electronic Theses and Dissertations

In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and …

On The Chromatic Number Of The Ao(2, K , K-1) Graphs., Navya Arora

Electronic Theses and Dissertations

The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs.

We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k …

Trees With Unique Minimum Locating-Dominating Sets., Stephen M. Lane

Electronic Theses and Dissertations

A set S of vertices in a graph G = (V, E) is a locating-dominating set if S is a dominating set of G, and every pair of distinct vertices {u, v} in V - S is located with respect to S, that is, if the set of neighbors of u that are in S is not equal to the set of neighbors of v that are in S. We give a construction of trees that have unique minimum locating-dominating sets.

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.

Freeness Of Hopf Algebras, Christopher David Walker

Theses Digitization Project

The Nichols-Zoeller freeness theorem states that a finite dimensional Hopf algebra is free as a module over any subHopfalgebra. We will prove this theorem, as well as the first significant generalization of this theorem, which was proven three years later. This generalization says that if the Hopf algebra is infinite dimensional, then the Hopf algebra is still free if the subHopfalgebra is finite dimensional and semisimple . We will also look at several other significant generalizations that have since been proven.

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 …

Fuzzy Interval Matrices, Neutrosophic Interval Matrices And Their Applications, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

The new concept of fuzzy interval matrices has been introduced in this book for the first time. The authors have not only introduced the notion of fuzzy interval matrices, interval neutrosophic matrices and fuzzy neutrosophic interval matrices but have also demonstrated some of its applications when the data under study is an unsupervised one and when several experts analyze the problem. Further, the authors have introduced in this book multiexpert models using these three new types of interval matrices. The new multi expert models dealt in this book are FCIMs, FRIMs, FCInMs, FRInMs, IBAMs, IBBAMs, nIBAMs, FAIMs, FAnIMS, etc. Illustrative …

Matrix-J-Unitary Non-Commutative Rational Formal Power Series, Daniel Alpay, D. S. Kalyuzhnyi-Verbovetzkii

Mathematics, Physics, and Computer Science Faculty Articles and Research

Formal power series in N non-commuting indeterminates can be considered as a counterpart of functions of one variable holomorphic at 0, and some of their properties are described in terms of coefficients. However, really fruitful analysis begins when one considers for them evaluations on N-tuples of n × n matrices (with n = 1, 2, . . .) or operators on an infinite-dimensional separable Hilbert space. Moreover, such evaluations appear in control, optimization and stabilization problems of modern system engineering.

In this paper, a theory of realization and minimal factorization of rational matrix-valued functions which are J-unitary on the imaginary …

Kernels Of Directed Graph Laplacians, John S. Caughman Iv, J. J. P. Veerman

Mathematics and Statistics Faculty Publications and Presentations

Let G denote a directed graph with adjacency matrix Q and in- degree matrix D. We consider the Kirchhoff matrix L = D − Q, sometimes referred to as the directed Laplacian. A classical result of Kirchhoff asserts that when G is undirected, the multiplicity of the eigenvalue 0 equals the number of connected components of G. This fact has a meaningful generalization to directed graphs, as was observed by Chebotarev and Agaev in 2005. Since this result has many important applications in the sciences, we offer an independent and self-contained proof of their theorem, showing in this paper …

Chord Diagrams And Gauss Codes For Graphs, Thomas Fleming, Blake Mellor

Mathematics, Statistics and Data Science Faculty Works

Chord diagrams on circles and their intersection graphs (also known as circle graphs) have been intensively studied, and have many applications to the study of knots and knot invariants, among others. However, chord diagrams on more general graphs have not been studied, and are potentially equally valuable in the study of spatial graphs. We will define chord diagrams for planar embeddings of planar graphs and their intersection graphs, and prove some basic results. Then, as an application, we will introduce Gauss codes for immersions of graphs in the plane and give algorithms to determine whether a particular crossing sequence is …

Tree Diagrams For String Links, Blake Mellor

Mathematics, Statistics and Data Science Faculty Works

In previous work, the author defined the intersection graph of a chord diagram associated with string links (as in the theory of finite type invariants). In this paper, we classify the trees which can be obtained as intersection graphs of string link diagrams.

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.

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.

Fibonacci Determinants — 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.

On The Action Of Weight-Preserving Sets, Matthew Badger

Mathematical Sciences Technical Reports (MSTR)

We introduce weight-preserving sets of binary words. Any transformation that respects the row and column weights of a 0-1 matrix can be decomposed as a composition of two types of action on the matrix. We conjecture that weight-preserving sets perform only one type of action, permutations of rows and columns; i.e., weight-preserving sets are cwatsets.

Big Cwatsets And Hamming Code, Matthew Davis, Thomas M. Langley, Norah Mazel

Mathematical Sciences Technical Reports (MSTR)

In contrast to Lagrange's Theorem in Finite Group Theory, we show that the ratio of the largest proper cwatset of degree d to the size of binary d-space approaches 1 as d approaches infinity. We show how to explicitly construct large cwatsets as cosets of Hamming Codes, and discuss many open questions that arise.

Q.954 And A.954, Quickie Problem And Solution, Arthur T. Benjamin, Michel Bataille

All HMC Faculty Publications and Research

Problem and proof proposed by authors.

Another proof, using lattice paths, can be found in Robert A. Sulanke's article, Objects Counted by the Central Delannoy Numbers, The Journal of Integer Sequences, Vol 6, 2003. A proof by polynomials is in Michel Bataille's paper Some Identities about an Old Combinatorial Sum, The Mathematical Gazette, March 2003, pp. 144-8. A slight change in the above proof leads to m ≥ n, a generalization proved by Li Zhou using lattice paths in The Mathematical Gazette.

A Constructive Proof Of Ky Fan's Generalization Of Tucker's Lemma, Timothy Prescott '02, Francis E. Su

All HMC Faculty Publications and Research

We present a proof of Ky Fan's combinatorial lemma on labellings of triangulated spheres that differs from earlier proofs in that it is constructive. We slightly generalize the hypotheses of Fan's lemma to allow for triangulations of Sⁿ that contain a flag of hemispheres. As a consequence, we can obtain a constructive proof of Tucker's lemma that holds for a more general class of triangulations than the usual version.

Mapping The Discrete Logarithm, Daniel R. Cloutier

Mathematical Sciences Technical Reports (MSTR)

The discrete logarithm is a problem that surfaces frequently in the field of cryptog- raphy as a result of using the transformation g^a mod n. This paper focuses on a prime modulus, p, for which it is shown that the basic structure of the functional graph is largely dependent on an interaction between g and p-1. In fact, there are precisely as many different functional graph structures as there are divisors of p-1. This paper extracts two of these structures, permutations and binary functional graphs. Estimates exist for the shape of a random permutation, but …

Monomial Nonnegativity And The Bruhat Order, Brian Drake, Sean Gerrish, Mark Skandera

Dartmouth Scholarship

We show that five nonnegativity properties of polynomials coincide when restricted to polynomials of the form x_{1, pi(1)} ... x_n,pi(n) - x_{1, sigma(1)} ... x_{n, sigma(n)}, where $\pi and sigma are permutations in S_n. In particular, we show that each of these properties may be used to characterize the Bruhat order on S_n.