Discrete Mathematics and Combinatorics Commons^™

A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke

Computer Science: Faculty Publications

We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in R^d may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R² this says that any planar map all of whose faces are triangles may be 3-colored, and in R³ it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.

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.

Slider-Pinning Rigidity: A Maxwell-Laman-Type Theorem, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

We define and study slider-pinning rigidity, giving a complete combinatorial characterization. This is done via direction-slider networks, which are a generalization of Whiteley’s direction networks.

Building Graphs From Colored Trees, Rachel M. Esselstein, Peter Winkler

Dartmouth Scholarship

We will explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely, fix a radius $\rho$ and let $N(G)$ be the set of isomorphism classes of $\rho$-neighborhoods of vertices of $G$ where $G$ is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood will be the unique vertex at the "center" of the graph. Given a set S of colored graphs with a unique root, when is there a graph G with N (G) = S? Or N (G) ⊂ …

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

A Predictive Model For Secondary Rna Structure Using Graph Theory And A Neural Network., Denise Renee Koessler

Electronic Theses and Dissertations

In this work we use a graph-theoretic representation of secondary RNA structure found in the database RAG: RNA-As-Graphs. We model the bonding of two RNA secondary structures to form a larger structure with a graph operation called merge. The resulting data from each tree merge operation is summarized and represented by a vector. We use these vectors as input values for a neural network and train the network to recognize a tree as RNA-like or not based on the merge data vector.

The network correctly assigned a high probability of RNA-likeness to trees identified as RNA-like in the RAG database, …

Total Domination Dot Critical And Dot Stable Graphs., Stephanie Anne Marie Mcmahon

Electronic Theses and Dissertations

Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total …

Discrete Fractional Calculus And Its Applications To Tumor Growth, Sevgi Sengul

Masters Theses & Specialist Projects

Almost every theory of mathematics has its discrete counterpart that makes it conceptually easier to understand and practically easier to use in the modeling process of real world problems. For instance, one can take the "difference" of any function, from 1st order up to the n-th order with discrete calculus. However, it is also possible to extend this theory by means of discrete fractional calculus and make n- any real number such that the ½-th order difference is well defined. This thesis is comprised of five chapters that demonstrate some basic definitions and properties of discrete fractional calculus …

An Algorithm To Generate Two-Dimensional Drawings Of Conway Algebraic Knots, Jen-Fu Tung

Masters Theses & Specialist Projects

The problem of finding an efficient algorithm to create a two-dimensional embedding of a knot diagram is not an easy one. Typically, knots with a large number of crossings will not nicely generate two-dimensional drawings. This thesis presents an efficient algorithm to generate a knot and to create a nice two-dimensional embedding of the knot. For the purpose of this thesis a drawing is “nice” if the number of tangles in the diagram consisting of half-twists is minimal. More specifically, the algorithm generates prime, alternating Conway algebraic knots in O(n) time where n is the number of crossings …

On The Non-Existence Of A Projective (75, 4,12, 5) Set In Pg(3, 7), Aaron C.S. Chan, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

We show by a combination of theoretical argument and computer search that if a projective (75, 4, 12, 5) set in PG(3, 7) exists then its automorphism group must be trivial. This corresponds to the smallest open case of a coding problem posed by H. Ward in 1998, concerning the possible existence of an infinite family of projective two-weight codes meeting the Griesmer bound.

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.

Snort: A Combinatorial Game, Keiko Kakihara

Theses Digitization Project

This paper focuses on the game Snort, which is a combinatorial game on graphs. This paper will explore the characteristics of opposability through examples. More fully, we obtain some neccessary conditions for a graph to be opposable. Since an opposable graph guarantees a second player win, we examine graphs that result in a first player win.

The Maximum Rectilinear Crossing Number Of The Petersen Graph, Elie Feder, Heiko Harborth, Steven Herzberg, Sheldon Klein

Publications and Research

We prove that the maximum rectilinear crossing number of the Petersen graph is 49. First, we illustrate a picture of the Petersen graph with 49 crossings to prove the lower bound. We then prove that this bound is sharp by carefully analyzing the ten Cs's which occur in the Petersen graph and their properties.

Interval Linear Algebra, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

This Interval arithmetic or interval mathematics developed in 1950’s and 1960’s by mathematicians as an approach to putting bounds on rounding errors and measurement error in mathematical computations. However no proper interval algebraic structures have been defined or studies. In this book we for the first time introduce several types of interval linear algebras and study them. This structure has become indispensable for these concepts will find applications in numerical optimization and validation of structural designs. In this book we use only special types of intervals and introduce the notion of different types of interval linear algebras and interval vector …

Rank Distance Bicodes And Their Generalization, Florentin Smarandache, W.B. Vasantha Kandasamy, N. Suresh Babu, R.S. Selvaraj

Branch Mathematics and Statistics Faculty and Staff Publications

In this book the authors introduce the new notion of rank distance bicodes and generalize this concept to Rank Distance n-codes (RD n-codes), n, greater than or equal to three. This definition leads to several classes of new RD bicodes like semi circulant rank bicodes of type I and II, semicyclic circulant rank bicode, circulant rank bicodes, bidivisible bicode and so on. It is important to mention that these new classes of codes will not only multitask simultaneously but also they will be best suited to the present computerised era. Apart from this, these codes are best suited in cryptography. …

Interval Groupoids, Florentin Smarandache, W.B. Vasantha Kandasamy, Moon Kumar Chetry

Branch Mathematics and Statistics Faculty and Staff Publications

This book introduces several new classes of groupoid, like polynomial groupoids, matrix groupoids, interval groupoids, polynomial interval groupoids, matrix interval groupoids and their neutrosophic analogues.

Some Implications Of Chu's 10Ψ10 Generalization Of Bailey's 6Ψ6 Summation Formula, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

Lucy Slater used Bailey's 6Ã6 summation formula to derive the Bailey pairs she used to construct her famous list of 130 identities of the Rogers-Ramanujan type.

In the present paper we apply the same techniques to Chu's 10Ã10 generalization of Bailey's formula to produce quite general Bailey pairs. Slater's Bailey pairs are then recovered as special limiting cases of these more general pairs.

In re-examining Slater's work, we find that her Bailey pairs are, for the most part, special cases of more general Bailey pairs containing one or more free parameters. Further, we also find new …

Ergodic And Combinatorial Proofs Of Van Der Waerden's Theorem, Matthew Samuel Rothlisberger

CMC Senior Theses

Followed two different proofs of van der Waerden's theorem. Found that the two proofs yield important information about arithmetic progressions and the theorem. van der Waerden's theorem explains the occurrence of arithmetic progressions which can be used to explain such things as the Bible Code.

Krein Systems And Canonical Systems On A Finite Interval: Accelerants With A Jump Discontinuity At The Origin And Continuous Potentials, Daniel Alpay, I. Gohberg, M. A. Kaashoek, L. Lerer, A. Sakhnovich

Mathematics, Physics, and Computer Science Faculty Articles and Research

This paper is devoted to connections between accelerants and potentials of Krein systems and of canonical systems of Dirac type, both on a finite interval. It is shown that a continuous potential is always generated by an accelerant, provided the latter is continuous with a possible jump discontinuity at the origin. Moreover, the generating accelerant is uniquely determined by the potential. The results are illustrated on pseudo-exponential potentials. The paper is a continuation of the earlier paper of the authors [1] dealing with the direct problem for Krein systems.

On The Characteristics Of A Class Of Gaussian Processes Within The White Noise Space Setting, Daniel Alpay, Haim Attia, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

Using the white noise space framework, we define a class of stochastic processes which include as a particular case the fractional Brownian motion and its derivative. The covariance functions of these processes are of a special form, studied by Schoenberg, von Neumann and Krein.

Discrete-Time Multi-Scale Systems, Daniel Alpay, Mamadou Mboup

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce multi-scale filtering by the way of certain double convolution systems. We prove stability theorems for these systems and make connections with function theory in the poly-disc. Finally, we compare the framework developed here with the white noise space framework, within which a similar class of double convolution systems has been defined earlier.

Linear Stochastic State Space Theory In The White Noise Space Setting, Daniel Alpay, David Levanony, Ariel Pinhas

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study state space equations within the white noise space setting. A commutative ring of power series in a countable number of variables plays an important role. Transfer functions are rational functions with coefficients in this commutative ring, and are characterized in a number of ways. A major feature in our approach is the observation that key characteristics of a linear, time invariant, stochastic system are determined by the corresponding characteristics associated with the deterministic part of the system, namely its average behavior.

Linear Stochastic Systems: A White Noise Approach, Daniel Alpay, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

Using the white noise setting, in particular the Wick product, the Hermite transform, and the Kondratiev space, we present a new approach to study linear stochastic systems, where randomness is also included in the transfer function. We prove BIBO type stability theorems for these systems, both in the discrete and continuous time cases. We also consider the case of dissipative systems for both discrete and continuous time systems. We further study ℓ1-ℓ2 stability in the discrete time case, and L2-L∞ stability in the continuous time case.

On Self-Clique Graphs., Ong Poh Hwa

Student Works (2010-2019)

The clique graph of a graph G is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques have non-empty intersection. A graph G is self-clique if it is isomorphic to its clique graph. Clique graphs have been studied for some time. However, not much is known about self-clique graphs. Self-clique graphs were ¯rst introduced and studied by Escalante [Abh. Math. Sem. Univ. Hamburg 39 (1973) 59-68]. Since then, self-clique graphs have been characterized for some classes of graphs. Chia [Discrete Math. 212 (2000) 185-189] gave a …