Discrete Mathematics and Combinatorics Commons^™

Very Cost Effective Domination In Graphs, Tony K. Rodriguez

Electronic Theses and Dissertations

A set S of vertices in a graph G=(V,E) is a dominating set if every vertex in V\S is adjacent to at least one vertex in S, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of …

Combinatorial And Algebraic Coding Techniques For Flash Memory Storage, Kathryn A. Haymaker

Department of Mathematics: Dissertations, Theses, and Student Research

Error-correcting codes are used to achieve reliable and efficient transmission when storing or sending information across a noisy channel. This thesis investigates a mathematical approach to coding techniques for storage devices such as flash memory storage, although many of the resulting codes and coding schemes can be applied in other contexts. The main contributions of this work include the design of efficient codes and decoding algorithms using discrete structures such as graphs and finite geometries, and developing a variety of strategies for adapting codes to a multi-level setting.

Information storage devices are prone to errors over time, and the frequency …

New Combinatorial Formulations Of The Shuffle Conjecture, Nicholas A. Loehr, Elizabeth Niese

Mathematics Faculty Research

The shuffle conjecture (due to Haglund, Haiman, Loehr, Remmel, and Ulyanov) provides a combinatorial formula for the Frobenius series of the diagonal harmonics module DH_n, which is the symmetric function∇(e_n). This formula is a sum over all labeled Dyck paths of terms built from combinatorial statistics called area, dinv, and IDes. We provide three new combinatorial formulations of the shuffle conjecture based on other statistics on labeled paths, parking functions, and related objects. Each such reformulation arises by introducing an appropriate new definition of the inverse descent set. Analogous results are proved for the higher-order shuffle …

On The Dynamic Coloring Of Cartesian Product Graphs., Saieed Akbari, Maryam Ghanbari, S. Jahanbekam

Faculty Publications

No abstract provided.

Cycle Lengths Of Θ-Biased Random Permutations, Tongjia Shi

HMC Senior Theses

Consider a probability distribution on the permutations of n elements. If the probability of each permutation is proportional to θ^K, where K is the number of cycles in the permutation, then we say that the distribution generates a θ-biased random permutation. A random permutation is a special θ-biased random permutation with θ = 1. The m^th moment of the r^th longest cycle of a random permutation is Θ(n^m), regardless of r and θ. The joint moments are derived, and it is shown that the longest cycles of a permutation can either be positively or …

Characterizing Forced Communication In Networks, Samuel C. Gutekunst

HMC Senior Theses

This thesis studies a problem that has been proposed as a novel way to disrupt communication networks: the load maximization problem. The load on a member of a network represents the amount of communication that the member is forced to be involved in. By maximizing the load on an important member of the network, we hope to increase that member's visibility and susceptibility to capture. In this thesis we characterize load as a combinatorial property of graphs and expose possible connections between load and spectral graph theory. We specifically describe the load and how it changes in several canonical classes …

Arithmetical Graphs, Riemann-Roch Structure For Lattices, And The Frobenius Number Problem, Jeremy Usatine

HMC Senior Theses

If R is a list of positive integers with greatest common denominator equal to 1, calculating the Frobenius number of R is in general NP-hard. Dino Lorenzini defines the arithmetical graph, which naturally arises in arithmetic geometry, and a notion of genus, the g-number, that in specific cases coincides with the Frobenius number of R. A result of Dino Lorenzini's gives a method for quickly calculating upper bounds for the g-number of arithmetical graphs. We discuss the arithmetic geometry related to arithmetical graphs and present an example of an arithmetical graph that arises in this context. We also discuss the …

Reed's Conjecture And Cycle-Power Graphs, Alexa Serrato

HMC Senior Theses

Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.

Boij-Söderberg Decompositions, Cellular Resolutions, And Polytopes, Stephen Sturgeon

Theses and Dissertations--Mathematics

Boij-Söderberg theory shows that the Betti table of a graded module can be written as a linear combination of pure diagrams with integer coefficients. In chapter 2 using Ferrers hypergraphs and simplicial polytopes, we provide interpretations of these coefficients for ideals with a d-linear resolution, their quotient rings, and for Gorenstein rings whose resolution has essentially at most two linear strands. We also establish a structural result on the decomposition in the case of quasi-Gorenstein modules. These results are published in the Journal of Algebra, see [25].

In chapter 3 we provide some further results about Boij-Söderberg decompositions. We …

Symmetries Of Embedded Complete Bipartite Graphs, Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn

Mathematics, Statistics and Data Science Faculty Works

We characterize which automorphisms of an arbitrary complete bipartite graph K_n,m can be induced by a homeomorphism of some embedding of the graph in S³.

Algebraic Structures On Real And Neutrosophic Semi Open Squares, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

Here for the first time we introduce the semi open square using modulo integers. Authors introduce several algebraic structures on them. These squares under addition modulo ‘n’ is a group and however under product  this semi open square is only a semigroup as under  the square has infinite number of zero divisors. Apart from + and  we define min and max operation on this square. Under min and max operation this semi real open square is a semiring. It is interesting to note that this semi open square is not a ring under + and  since …

Special Pseudo Linear Algebras Using [0,N), Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book we introduce some special type of linear algebras called pseudo special linear algebras using the interval [0, n). These new types of special pseudo interval linear algebras has several interesting properties. Special pseudo interval linear algebras are built over the subfields in Zn where Zn is a S-ring. We study the substructures of them. The notion of Smarandache special interval pseudo linear algebras and Smarandache strong special pseudo interval linear algebras are introduced. The former Sspecial interval pseudo linear algebras are built over the Sring itself. Study in this direction has yielded several interesting results. S-strong special …

Groupoids Of Type I And Ii Using [0, N), Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

Study of algebraic structures built using [0, n) happens to be one of an interesting and innovative research. Here in this book authors define non associative algebraic structures using the interval [0, n). Here we define two types of groupoids using [0, n) both of them are of infinite order. It is an open conjecture to find whether these new class of groupoids satisfy any of the special identities like Moufang identity or Bol identity or Bruck identity or so on. We know on [0, n) we cannot build rings only pseudo rings, however in this book we use these …

Algebraic Structures On Finite Complex Modulo Integer Interval C([0, N)), Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors introduce the notion of finite complex modulo integer intervals. Finite complex modulo integers was introduced by the authors in 2011. Now using this finite complex modulo integer intervals several algebraic structures are built. Further the concept of finite complex modulo integers itself happens to be new and innovative for in case of finite complex modulo integers the square value of the finite complex number varies with varying n of Zn. In case of finite complex modulo integer intervals also we can have only pseudo ring as the distributive law is not true, in general in C([0, …

Soft Neutrosophic Algebraic Structures And Their Generalization - Vol. 1, Florentin Smarandache, Mumtaz Ali, Muhammad Shabir

Branch Mathematics and Statistics Faculty and Staff Publications

In this book the authors introduced the notions of soft neutrosophic algebraic structures. These soft neutrosophic algebraic structures are basically defined over the neutrosophic algebraic structures which means a parameterized collection of subsets of the neutrosophic algebraic structure. For instance, the existence of a soft neutrosophic group over a neutrosophic group or a soft neutrosophic semigroup over a neutrosophic semigroup, or a soft neutrosophic field over a neutrosophic field, or a soft neutrosophic LA-semigroup over a neutrosophic LAsemigroup, or a soft neutosophic loop over a neutrosophic loop. It is interesting to note that these notions are defined over finite and …

Pseudo Lattice Graphs And Their Applications To Fuzzy And Neutrosophic Models, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book for the first time authors introduce the concept of merged lattice, which gives a lattice or a graph. The resultant lattice or graph is defined as the pseudo lattice graph of type I. Here we also merge a graph with a lattice or two or more graphs which call as the pseudo lattice graph of type II. We merge either edges or vertices or both of a lattice and a graph or a lattice and a lattice or graph with itself. Such study is innovative and these mergings are adopted on all fuzzy and neutrosophic models which …

Distance In Matrices And Their Applications To Fuzzy Models And Neutrosophic Models, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of distance between any two m  n matrices. If the distance is 0 or m  n there is nothing interesting. When the distance happens to be a value t; 0 < t < m  n the study is both innovating and interesting. The three cases of study which is carried out in this book are 1. If the difference between two square matrices is large, will it imply the eigen values and eigen vectors of those matrices are distinct? Several open conjectures in this direction are given. 2. The difference between parity check matrix and the generator matrix for the same C(n, k) code is studied. This will help in detecting errors in storage systems as well as in cryptography.

Interpolation By Polynomials With Symmetries, Daniel Alpay, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

We here specialize the standard matrix-valued polynomial interpolation to the case where on the imaginary axis the interpolating polynomials admit various symmetries: Positive semidefinite, Skew-Hermitian, J- Hermitian, Hamiltonian and others.

The procedure is comprized of three stages, illustrated through the case where on $i\R$ the interpolating polynomials are to be positive semidefinite. We first, on the expense of doubling the degree, obtain a minimal degree interpolating polynomial P(s) which on $i\R$ is Hermitian. Then we find all polynomials Ψ(s), vanishing at the interpolation points which are positive semidefinite on $i\R$. Finally, using the fact that the set of positive semidefinite …

On Free Stochastic Processes And Their Derivatives, Daniel Alpay, Palle Jorgensen, Guy Salomon

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study a family of free stochastic processes whose covariance kernels K may be derived as a transform of a tempered measure σ. These processes arise, for example, in consideration non-commutative analysis involving free probability. Hence our use of semi-circle distributions, as opposed to Gaussians. In this setting we find an orthonormal bases in the corresponding noncommutative L2 of sample-space. We define a stochastic integral for our family of free processes.

Krein-Langer Factorization And Related Topics In The Slice Hyperholomorphic Setting, Daniel Alpay, Fabrizio Colombo, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study various aspects of Schur analysis in the slice hyperholomorphic setting. We present two sets of results: first, we give new results on the functional calculus for slice hyperholomorphic functions. In particular, we introduce and study some properties of the Riesz projectors. Then we prove a Beurling-Lax type theorem, the so-called structure theorem. A crucial fact which allows to prove our results, is the fact that the right spectrum of a quaternionic linear operator and the point S-spectrum coincide. Finally, we study the Krein-Langer factorization for slice hyperholomorphic generalized Schur functions. Both the Beurling-Lax type theorem and the Krein-Langer …