Discrete Mathematics and Combinatorics Commons^™

Golden Arm: A Probabilistic Study Of Dice Control In Craps, Donald R. Smith, Robert Scott Iii

UNLV Gaming Research & Review Journal

This paper calculates how much control a craps shooter must possess on dice outcomes to eliminate the house advantage. A golden arm is someone who has dice control (or a rhythm roller or dice influencer). There are various strategies for dice control in craps. We discuss several possibilities of dice control that would result in several different mathematical models of control. We do not assert whether dice control is possible or not (there is a lack of published evidence). However, after studying casino-legal methods described by dice-control advocates, we can see only one realistic mathematical model that describes the resulting …

Secure Multiparty Protocol For Differentially-Private Data Release, Anthony Harris

Boise State University Theses and Dissertations

In the era where big data is the new norm, a higher emphasis has been placed on models which guarantees the release and exchange of data. The need for privacy-preserving data arose as more sophisticated data-mining techniques led to breaches of sensitive information. In this thesis, we present a secure multiparty protocol for the purpose of integrating multiple datasets simultaneously such that the contents of each dataset is not revealed to any of the data owners, and the contents of the integrated data do not compromise individual’s privacy. We utilize privacy by simulation to prove that the protocol is privacy-preserving, …

Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole

Undergraduate Honors Theses

Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the d^t t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds …

Graphs With Few Spanning Substructures, Jessica De Silva

Department of Mathematics: Dissertations, Theses, and Student Research

In this thesis, we investigate a number of problems related to spanning substructures of graphs. The first few chapters consider extremal problems related to the number of forest-like structures of a graph. We prove that one can find a threshold graph which contains the minimum number of spanning pseudoforests, as well as rooted spanning forests, amongst all graphs on n vertices and e edges. This has left the open question of exactly which threshold graphs have the minimum number of these spanning substructures. We make progress towards this question in particular cases of spanning pseudoforests.

The final chapter takes on …

On Coding For Partial Erasure Channels, Carolyn Mayer

Department of Mathematics: Dissertations, Theses, and Student Research

Error correcting codes have been essential to the technology we use in everyday life in digital storage, wireless communication, barcodes, and much more. Different channel models are used for different types of communication (for example, if information is sent to one person or to many people) and different types of errors. Partial erasure channels were recently introduced to model applications in which some information remains after an erasure event. These remnants of information may be used to increase the chances of successful decoding. We introduce a new partial erasure channel in which partial erasures correspond to individual bit erasures in …

Vector Partitions, Jennifer French

Electronic Theses and Dissertations

Integer partitions have been studied by many mathematicians over hundreds of years. Many identities exist between integer partitions, such as Euler’s discovery that every number has the same amount of partitions into distinct parts as into odd parts. These identities can be proven using methods such as conjugation or generating functions. Over the years, mathematicians have worked to expand partition identities to vectors. In 1963, M. S. Cheema proved that every vector has the same number of partitions into distinct vectors as into vectors with at least one component odd. This parallels Euler’s result for integer partitions. The primary purpose …

On Some Geometry Of Graphs, Zachary S. Mcguirk

Dissertations, Theses, and Capstone Projects

In this thesis we study the intrinsic geometry of graphs via the constants that appear in discretized partial differential equations associated to those graphs. By studying the behavior of a discretized version of Bochner's inequality for smooth manifolds at the cone point for a cone over the set of vertices of a graph, a lower bound for the internal energy of the underlying graph is obtained. This gives a new lower bound for the size of the first non-trivial eigenvalue of the graph Laplacian in terms of the curvature constant that appears at the cone point and the size of …

The Average Measure Of A K-Dimensional Simplex In An N-Cube, John A. Carter

Graduate Theses/Dissertations

Within an n-dimensional unit cube, a number of k-dimensional simplices can be formed whose vertices are the vertices of the n-cube. In this thesis, we analyze the average measure of a k-simplex in the n-cube. We develop exact equations for the average measure when k = 1, 2, and 3. Then we generate data for these cases and conjecture that their averages appear to approach n^k/2 times some constant. Using the convergence of Bernstein polynomials and a k-simplex Bernstein generalization, we prove the conjecture is true for the 1-simplex and 2-simplex cases. We then develop a generalized formula for …

An Optimized Route For Q100'S Bert And Kristin To Visit All Jersey Mike's Subs In Atlanta For Charity

Symposium of Student Scholars

The Bert Show is a popular morning show on Atlanta’s Q100 radio station. They host a non-profit organization that provides a “magical, all-expenses-paid, five-day journey to Walt Disney World for children with chronic and terminal illnesses and their families” called “Bert’s Big Adventure.” On March 28^th, 2018, thirty-seven locations of Jersey Mike’s are participating in the their Jersey Mike’s Day of Giving to support Bert’s Big Adventure. The goal is to have two popular radio show hosts visit each of these locations for some photos and presence to draw in more customers! But how do we get two …

Efficient Reduced Bias Genetic Algorithm For Generic Community Detection Objectives, Aditya Karnam Gururaj Rao

Theses

The problem of community structure identification has been an extensively investigated area for biology, physics, social sciences, and computer science in recent years for studying the properties of networks representing complex relationships. Most traditional methods, such as K-means and hierarchical clustering, are based on the assumption that communities have spherical configurations. Lately, Genetic Algorithms (GA) are being utilized for efficient community detection without imposing sphericity. GAs are machine learning methods which mimic natural selection and scale with the complexity of the network. However, traditional GA approaches employ a representation method that dramatically increases the solution space to be searched by …

On Structures Of Large Rooted Graphs, Shilin Wang

LSU Doctoral Dissertations

A rooted graph is a pair (G,R), where G is a graph and R⊆V(G). There are two research topics in this thesis. One is about unavoidable substructures in sufficiently large rooted graphs. The other is about characterizations of rooted graphs excluding specific large graphs.

The first topic of this thesis is motivated by Ramsey Theorem, which states that K_n and ¯(K_n ) are unavoidable induced subgraphs in every sufficiently large graph. It is also motivated by a classical result of Oporowski, Oxley, and Thomas, which determines unavoidable large 3-connected minors. We first determine unavoidable induced subgraphs, and unavoidable subgraphs in …

Vertex-Relaxed Graceful Labelings Of Graphs And Congruences, Florin Aftene

Masters Theses & Specialist Projects

A labeling of a graph is an assignment of a natural number to each vertex

of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous result …

Runs Of Identical Outcomes In A Sequence Of Bernoulli Trials, Matthew Riggle

Masters Theses & Specialist Projects

The Bernoulli distribution is a basic, well-studied distribution in probability. In this thesis, we will consider repeated Bernoulli trials in order to study runs of identical outcomes. More formally, for t ∈ N, we let Xt ∼ Bernoulli(p), where p is the probability of success, q = 1 − p is the probability of failure, and all Xt are independent. Then Xt gives the outcome of the tth trial, which is 1 for success or 0 for failure. For n, m ∈ N, we define Tn to be the number of trials needed to first observe n …

Controllability And Observability Of The Discrete Fractional Linear State-Space Model, Duc M. Nguyen

Masters Theses & Specialist Projects

This thesis aims to investigate the controllability and observability of the discrete fractional linear time-invariant state-space model. First, we will establish key concepts and properties which are the tools necessary for our task. In the third chapter, we will discuss the discrete state-space model and set up the criteria for these two properties. Then, in the fourth chapter, we will attempt to apply these criteria to the discrete fractional model. The general flow of our objectives is as follows: we start with the first-order linear difference equation, move on to the discrete system, then the fractional difference equation, and finally …

Strong Degrees In Single Valued Neutrosophic Graphs, Florentin Smarandache, Said Broumi, Assia Bakali, Seema Mehra, Mohamed Talea, Manjeet Singh

Branch Mathematics and Statistics Faculty and Staff Publications

The concept of single valued neutrosophic graphs (SVNGs) generalizes the concept of fuzzy graphs and intuitionistic fuzzy graphs. The purpose of this research paper is to define different types of strong degrees in SVNGs and introduce novel concepts, such as the vertex truth-membership, vertex indeterminacy-membership and falsity-membership sequence in SVNG with proof and numerical illustrations.

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory & Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to …

Design And Analysis Of Graph-Based Codes Using Algebraic Lifts And Decoding Networks, Allison Beemer

Department of Mathematics: Dissertations, Theses, and Student Research

Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The …

Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger

Faculty Publications

The k-weak-dynamic number of a graph G is the smallest number of colors we need to color the vertices of G in such a way that each vertex v of degree d(v) sees at least min{k, d(v)} colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.

Summary Of The Special Issue “Neutrosophic Information Theory And Applications” At “Information” Journal, Florentin Smarandache, Jun Ye

Branch Mathematics and Statistics Faculty and Staff Publications

Over a period of seven months (August 2017–February 2018), the Special Issue dedicated to “Neutrosophic Information Theory and Applications” by the “Information” journal (ISSN 2078-2489), located in Basel, Switzerland, was a success. The Guest Editors, Prof. Dr. Florentin Smarandache from the University of New Mexico (USA) and Prof. Dr. Jun Ye from the Shaoxing University (China), were happy to select—helped by a team of neutrosophic reviewers from around the world, and by the “Information” journal editors themselves—and publish twelve important neutrosophic papers, authored by 27 authors and coauthors. There were a variety of neutrosophic topics studied and used by the …

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory & Applications of Graphs

We say that a blinking node system modulo n is an ordered pair (G,L) where G is a graph and L is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of G such that the position of each vertex modulo n is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other graphs.

The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph G …

An Extension Of The Jeu De Taquin, Joanna Mckinney

Theses, Dissertations and Capstones

The Knuth transformations on words, the jeu de taquin moves on tableaux, and the Robinson–Schensted–Knuth algorithm produce the same equivalence classes for words. By observing the connections between these three methods we find and prove there exists connections between the Assaf–Knuth transformations, our extension of the jeu de taquin, and p-RSK. We know there exists an algebraic way to expand Macdonald polynomials in terms of the Schur functions. The form of the expansion implies there should be a combinatorial way to find the expansion. Loehr found a Robinson–Schensted–Knuth like algorithm that works in some cases. By finding an extension of …

An Incidence Approach To The Distinct Distances Problem, Bryce Mclaughlin

HMC Senior Theses

In 1946, Erdös posed the distinct distances problem, which asks for the minimum number of distinct distances that any set of n points in the real plane must realize. Erdös showed that any point set must realize at least &Omega(n^1/2) distances, but could only provide a construction which offered &Omega(n/&radic(log(n)))$ distances. He conjectured that the actual minimum number of distances was &Omega(n^1-&epsilon) for any &epsilon > 0, but that sublinear constructions were possible. This lower bound has been improved over the years, but Erdös' conjecture seemed to hold until in 2010 Larry Guth and Nets Hawk Katz …

Hilbert Bases, Descent Statistics, And Combinatorial Semigroup Algebras, Mccabe J. Olsen

Theses and Dissertations--Mathematics

The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials.

Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory.

In Chapter …

A Combinatorial Miscellany: Antipodes, Parking Cars, And Descent Set Powers, Alexander Thomas Happ

Theses and Dissertations--Mathematics

In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the 𝑟th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results …

3-Maps And Their Generalizations, Kevin J. Mccall

Theses and Dissertations

A 3-map is a 3-region colorable map. They have been studied by Craft and White in their paper 3-maps. This thesis introduces topological graph theory and then investigates 3-maps in detail, including examples, special types of 3-maps, the use of 3-maps to find the genus of special graphs, and a generalization known as n-maps.

On Saturation Numbers Of Ramsey-Minimal Graphs, Hunter M. Davenport

Honors Undergraduate Theses

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H₁,...,H_k) if every k-edge-coloring of G contains a monochromatic copy of H_i in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains no red K₃or blue K …

Polytopes Associated To Graph Laplacians, Marie Meyer

Theses and Dissertations--Mathematics

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, P_G, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, P_D.

Basic properties of both families of simplices, P_G and P …

Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …

String C-Groups Of Order 1024, Yasushi Gomi, Mark L. Loyola, Ma. Louise Antonette N. De Las Peñas

Mathematics Faculty Publications

This paper determines the nondegenerate string C-groups of order 1024. For groups of rank 3, we use the technique of central extension of string C-groups of order 512. For groups of rank at least 4, we compute for quotients of universal string C-groups.