Discrete Mathematics and Combinatorics Commons^™

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.

Counting On Determinants, Arthur T. Benjamin, Naiomi T. Cameron

All HMC Faculty Publications and Research

No abstract provided in this article.

Lower Bounds For Simplicial Covers And Triangulations Of Cubes, Adam Bliss '03, Francis E. Su

All HMC Faculty Publications and Research

We show that the size of a minimal simplicial cover of a polytope P is a lower bound for the size of a minimal triangulation of P, including ones with extra vertices. We then use this fact to study minimal triangulations of cubes, and we improve lower bounds for covers and triangulations in dimensions 4 through at least 12 (and possibly more dimensions as well). Important ingredients are an analysis of the number of exterior faces that a simplex in the cube can have of a specified dimension and volume, and a characterization of corner simplices in terms of their …

Double Arrays, Triple Arrays And Balanced Grids, John P. Mcsorley, Nicholas C. Phillips, Walter D. Wallis, Joseph L. Yucas

Articles and Preprints

Triple arrays are a class of designs introduced by Agrawal in 1966 for two-way elimination of heterogeneity in experiments. In this paper we investigate their existence and their connection to other classes of designs, including balanced incomplete block designs and balanced grids.

The Terwilliger Algebra Of An Almost-Bipartite P- And Q-Polynomial Association Scheme, John S. Caughman Iv, Mark S. Maclean, Paul M. Terwilliger

Mathematics and Statistics Faculty Publications and Presentations

Let Y denote a D-class symmetric association scheme with D≥3, and suppose Y is almost-bipartite P- and Q-polynomial. Let x denote a vertex of Y and let T=T(x) denote the corresponding Terwilliger algebra. We prove that any irreducible T-module W is both thin and dual thin in the sense of Terwilliger. We produce two bases for W and describe the action of T on these bases. We prove that the isomorphism class of W as a T-module is determined by two parameters, the dual endpoint and diameter of W. We find a recurrence which gives the multiplicities with which the …

Combinatorial Proofs Of Fermat's, Lucas's, And Wilson's Theorems, Peter G. Anderson, Arthur T. Benjamin, Jeremy A. Rouse

All HMC Faculty Publications and Research

No abstract provided in this article.

Convergence Analysis Of Mcmc Method In The Study Of Genetic Linkage With Missing Data, Diana Fisher

Theses, Dissertations and Capstones

Computational infeasibility of exact methods for solving genetic linkage analysis problems has led to the development of a new collection of stochastic methods, all of which require the use of Markov chains. The purpose of this work is to investigate the complexities of missing data in pedigree analysis using the Monte Carlo Markov Chain (MCMC) method as compared to the exact results. Also, we attempt to determine an association between missing data in a familial pedigree and the convergence to stationarity of a descent graph Markov chain implemented in the stochastic method for parametric linkage analysis.

In particular, we will …

Reduction Of The Gibbs Phenomenon Via Interpolation Using Chebyshev Polynomials, Filtering And Chebyshev-Pade' Approximations, Rob-Roy L. Mace

Theses, Dissertations and Capstones

In this manuscript, we will examine several methods of interpolation, with an emphasis on Chebyshev polynomials and the removal of the Gibbs Phenomenon. Included as an appendix are the author’s Mat- Lab implementations of Lagrange, Chebyshev, and rational interpolation methods.

Introduction To Linear Bialgebra, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

The algebraic structure, linear algebra happens to be one of the subjects which yields itself to applications to several fields like coding or communication theory, Markov chains, representation of groups and graphs, Leontief economic models and so on. This book has for the first time, introduced a new algebraic structure called linear bialgebra, which is also a very powerful algebraic tool that can yield itself to applications. With the recent introduction of bimatrices (2005) we have ventured in this book to introduce new concepts like linear bialgebra and Smarandache neutrosophic linear bialgebra and also give the applications of these algebraic …

Applications Of Bimatrices To Some Fuzzy And Neutrosophic Models, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

Graphs and matrices play a vital role in the analysis and study of several of the real world problems which are based only on unsupervised data. The fuzzy and neutrosophic tools like fuzzy cognitive maps invented by Kosko and neutrosophic cognitive maps introduced by us help in the analysis of such real world problems and they happen to be mathematical tools which can give the hidden pattern of the problem under investigation. This book, in order to generalize the two models, has systematically invented mathematical tools like bimatrices, trimatrices, n-matrices, bigraphs, trigraphs and n-graphs and describe some of its properties. …

Point Evaluation And Hardy Space On A Homogeneous Tree, Daniel Alpay, Dan Volok

Mathematics, Physics, and Computer Science Faculty Articles and Research

We consider stationary multiscale systems as defined by Basseville, Benveniste, Nikoukhah and Willsky. We show that there are deep analogies with the discrete time non stationary setting as developed by the first author, Dewilde and Dym. Following these analogies we define a point evaluation with values in a C*–algebra and the corresponding “Hardy space” in which Cauchy’s formula holds. This point evaluation is used to define in this context the counterpart of classical notions such as Blaschke factors.

Introduction To Bimatrices, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

Matrix theory has been one of the most utilised concepts in fuzzy models and neutrosophic models. From solving equations to characterising linear transformations or linear operators, matrices are used. Matrices find their applications in several real models. In fact it is not an exaggeration if one says that matrix theory and linear algebra (i.e. vector spaces) form an inseparable component of each other. The study of bialgebraic structures led to the invention of new notions like birings, Smarandache birings, bivector spaces, linear bialgebra, bigroupoids, bisemigroups, etc. But most of these are abstract algebraic concepts except, the bisemigroup being used in …

Rational Hyperholomorphic Functions In R4, Daniel Alpay, Michael Shapiro, Dan Volok

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce the notion of rationality for hyperholomorphic functions (functions in the kernel of the Cauchy-Fueter operator). Following the case of one complex variable, we give three equivalent definitions: the first in terms of Cauchy-Kovalevskaya quotients of polynomials, the second in terms of realizations and the third in terms of backward-shift invariance. Also introduced and studied are the counterparts of the Arveson space and Blaschke factors.