Discrete Mathematics and Combinatorics Commons^™

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.

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 …

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.

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.

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.

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.

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.

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.

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 1324, 4231-Avoiding Permutations, Michael H. Albert, M. D. Atkinson, Vincent Vatter

Dartmouth Scholarship

A complete structural description and enumeration is found for permutations that avoid both 1324 and 4231.

Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V^′⊂V spans more than k|V^′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms …

Operations Research Methods For Optimization In Radiation Oncology, M Ehrgott, Allen Holder

Mathematical Sciences Technical Reports (MSTR)

Operations Research has a successful tradition of applying mathematical analysis to a wide range of applications, with one of the burgeoning areas of growth being in medical physics. The original application was in the optimal design of the influence map for a radiotherapy treatment, a problem that has continued to receive attention. However, operations research has been applied to other clinical problems like patient scheduling, vault design, and image alignment. The overriding theme of this article is to present how techniques in operations research apply to clinical problems, which we accomplish in three parts. First, we present the perspective from …

The Last Of The Mixed Triple Systems., Ernest Jum

Electronic Theses and Dissertations

In this thesis, we consider the decomposition of the complete mixed graph on v vertices denoted M_v, into every possible mixed graph on three vertices which has (like M_v) twice as many arcs as edges. Direct constructions are given in most cases. Decompositions of theλ-fold complete mixed graph λM_v, are also studied.

Independent Domination In Complementary Prisms., Joel Agustin Gongora

Electronic Theses and Dissertations

Let G be a graph and G̅ be the complement of G. The complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. For example, if G is a 5-cycle, then GG̅ is the Petersen graph. In this paper we investigate independent domination in complementary prisms.

Solving The P-Median Problem With Insights From Discrete Vector Quantization, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

The goals of this paper are twofold. First, we formally equate the p-median problem from facility location to the optimal design of a vector quantizer. Second, we use the equivalence to show that the Maranzana Algorithm can be interpreted as a projected Lloyd Algorithm, a fact that improves complexity. Numerical results verify significant improvements in run-time.

A Decomposition Of The Pure Parsimony Problem, Allen Holder, Thomas M. Langley

Mathematical Sciences Technical Reports (MSTR)

We partially order a collection of genotypes so that we can represent the problem of inferring the least number of haplotypes in terms of substructures we call g-lattices. This representation allows us to prove that if the genotypes partition into chains with certain structure, then the NP-Hard problem can be solved efficiently. Even without the specified structure, the decomposition shows how to separate the underlying integer programming model into smaller models.

A Clustering Approach For Optimizing Beam Angles In Imrt Planning, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

In this paper we introduce a p-median problem based clustering heuristic for selecting efficient beam angles for intensity-modulated radiation therapy. The essence of the method described here is the clustering of beam angles according to probability that an angle will be observed in the final solution and similarities among different angles and the selection of a representative angle from each of the p resulting cluster cells. We conduct experiments using several combinations of modeling parameters to find the conditions where the heuristic best performs. We found a combination of such parameters that outperformed all other parameters on three of the …

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 …

Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman

Mathematical Sciences Technical Reports (MSTR)

The absence of an efficient algorithm to solve the Discrete Logarithm Problem is often exploited in cryptography. While exponentiation with a modulus is extremely fast with a modern computer, the inverse is decidedly not. At the present time, the best algorithms assume that the inverse mapping is completely random. Yet there is at least some structure, and to uncover additional structure that may be useful in constructing or refining algorithms, statistical methods are employed to compare modular exponential mappings to random mappings. More concretely, structure will be defined by representing the mappings as functional graphs and using parameters from graph …

Discrete Logarithm Over Composite Moduli, Marcus L. Mace

Mathematical Sciences Technical Reports (MSTR)

In an age of digital information, security is of utmost importance. Many encryption schemes, such as the Diffie-Hellman Key Agreement and RSA Cryptosystem, use a function which maps x to y by a modular power map with generator g. The inverse of this function - trying to find x from y - is called the discrete logarithm problem. In most cases, n is a prime number. In some cases, however, n may be a composite number. In particular, we will look at when n = p^b for a prime p. We will show different techniques of obtaining graphs of this …