Discrete Mathematics and Combinatorics Commons^™

Counting The Angels And Devils In Escher's Circle Limit Iv, John Choi, Nicholas Pippenger

Journal of Humanistic Mathematics

We derive the rational generating function that enumerates the angels and devils in M. C. Escher's Circle Limit IV according to their combinatorial distance from the six creatures whose feet meet at the center of the disk. This result shows that the base of the exponential rate of growth is 1.582... (the largest root of the polynomial 1 - z^2 - 2z^3 - z^4 + z^6).

Expectation Numbers Of Cyclic Groups, Miriam Mahannah El-Farrah

Masters Theses & Specialist Projects

When choosing k random elements from a group the kth expectation number is the expected size of the subgroup generated by those specific elements. The main purpose of this thesis is to study the asymptotic properties for the first and second expectation numbers of large cyclic groups. The first chapter introduces the kth expectation number. This formula allows us to determine the expected size of any group. Explicit examples and computations of the first and second expectation number are given in the second chapter. Here we show example of both cyclic and dihedral groups. In chapter three we discuss arithmetic …

A Posteriori Eigenvalue Error Estimation For The Schrödinger Operator With The Inverse Square Potential, Hengguang Li, Jeffrey S. Ovall

Mathematics and Statistics Faculty Publications and Presentations

We develop an a posteriori error estimate of hierarchical type for Dirichlet eigenvalue problems of the form (−∆ + (c/r) 2 )ψ = λψ on bounded domains Ω, where r is the distance to the origin, which is assumed to be in Ω. This error estimate is proven to be asymptotically identical to the eigenvalue approximation error on a family of geometrically-graded meshes. Numerical experiments demonstrate this asymptotic exactness in practice.

Generalizations And Algebraic Structures Of The Grøstl-Based Primitives, Dmitriy Khripkov, Nicholas Lacasse, Bai Lin, Michelle Mastrianni, Liljana Babinkostova (Mentor)

Idaho Conference on Undergraduate Research

With the large scale proliferation of networked devices ranging from medical implants like pacemakers and insulin pumps, to corporate information assets, secure authentication, data integrity and confidentiality have become some of the central goals for cybersecurity. Cryptographic hash functions have many applications in information security and are commonly used to verify data authenticity. Our research focuses on the study of the properties that dictate the security of a cryptographic hash functions that use Even-Mansour type of ciphers in their underlying structure. In particular, we investigate the algebraic design requirements of the Grøstl hash function and its generalizations. Grøstl is an …

E-Super Vertex Magic Labelling Of Graphs And Some Open Problems, G. Marimuthu, B. Suganya, S. Kalaivani, M. Balakrishnan

Applications and Applied Mathematics: An International Journal (AAM)

Let G be a finite graph with p vertices and q edges. A vertex magic total labelling is a bijection from the union of the vertex set and the edge set to the consecutive integers 1, 2, 3, . . . , p + q with the property that for every u in the vertex set, the sum of the label of u and the label of the edges incident with u is equal to k for some constant k. Such a labelling is E-super, if the labels of the edge set is the set {1, 2, 3, . . …

Combinatorial Identities For Incomplete Tribonacci Polynomials, Mark Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

The incomplete tribonacci polynomials, denoted by T_n^(s)(x), generalize the usual tribonacci polynomials T_n (x) and have been shown to satisfy several algebraic identities. In this paper, we provide a combinatorial interpretation for T_n^(s)(x) in terms of weighted linear tilings involving three types of tiles. This allows one not only to supply combinatorial proofs of earlier identities for T_n^(s)(x) but also to derive new ones. In the final section, we provide a formula for the ordinary generating function of the sequence T_n^(s)(x) for a fixed s, as previously …

Commutative N-Ary Arithmetic, Aram Bingham

LSU New Orleans Theses and Dissertations

Motivated by primality and integer factorization, this thesis introduces generalizations of standard binary multiplication to commutative n-ary operations based upon geometric construction and representation. This class of operations are constructed to preserve commutativity and identity so that binary multiplication is included as a special case, in order to preserve relationships with ordinary multiplicative number theory. This leads to a study of their expression in terms of elementary symmetric polynomials, and connections are made to results from the theory of polyadic (n-ary) groups. Higher order operations yield wider factorization and representation possibilities which correspond to reductions in the set of primes …

Analysis Of Discrete Fractional Operators And Discrete Fractional Rheological Models, Meltem Uyanik

Masters Theses & Specialist Projects

This thesis is comprised of two main parts: Monotonicity results on discrete fractional operators and discrete fractional rheological constitutive equations. In the first part of the thesis, we introduce and prove new monotonicity concepts in discrete fractional calculus. In the remainder, we carry previous results about fractional rheological models to the discrete fractional case. The discrete method is expected to provide a better understanding of the concept than the continuous case as this has been the case in the past. In the first chapter, we give brief information about the main results. In the second chapter, we present some fundamental …

Extremal Results For The Number Of Matchings And Independent Sets, Lauren Keough

Department of Mathematics: Dissertations, Theses, and Student Research

This dissertation answers several questions in extremal graph theory, each concerning the maximum or minimum number of certain substructures a graph can have, given that it must satisfy certain properties. In recent years there has been increased interest in such problems, which are extremal problems for "counting" parameters of graphs. The results in this dissertation focus on graphs that have n vertices and e edges and 3-uniform hypergraphs that have n vertices and e edges.

We first observe in the preliminaries chapter that for graphs with a fixed number of vertices and edges there is a threshold graph attaining the …

The Apprentices' Tower Of Hanoi, Cory Bh Ball

Electronic Theses and Dissertations

The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.

Distance-2 Domatic Numbers Of Graphs, Derek Kiser

Electronic Theses and Dissertations

The distance d(u, v) between two vertices u and v in a graph G equals the length of a shortest path from u to v. A set S of vertices is called a distance-2 dominating set if every vertex in V \S is within distance-2 of at least one vertex in S. The distance-2 domatic number is the maximum number of sets in a partition of the vertices of G into distance-2 dominating sets. We give bounds on the distance-2 domatic number of a graph and determine the distance-2 domatic number of selected classes of graphs.

A Hierarchical Graph For Nucleotide Binding Domain 2, Samuel Kakraba

Electronic Theses and Dissertations

One of the most prevalent inherited diseases is cystic fibrosis. This disease is caused by a mutation in a membrane protein, the cystic fibrosis transmembrane conductance regulator (CFTR). CFTR is known to function as a chloride channel that regulates the viscosity of mucus that lines the ducts of a number of organs. Generally, most of the prevalent mutations of CFTR are located in one of two nucleotide binding domains, namely, the nucleotide binding domain 1 (NBD1). However, some mutations in nucleotide binding domain 2 (NBD2) can equally cause cystic fibrosis. In this work, a hierarchical graph is built for NBD2. …

Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just

GS4 Student Scholars Symposium

Pattern packing concerns finding an optimal permutation that contains the maximum number of occurrences of a given pattern and computing the corresponding packing density. In many instances such an optimal permutation can be characterized directly and the number of occurrences of the pattern in interest may be enumerated explicitly. In more complicated patterns a direct characterization may be more challenging, however computational results for long permutations can help provide an indirect characterization of the general form of an optimal permutation. Much work has been done on the study of pattern packing in layered patterns, as the optimal permutation of a …

Two Rosa-Type Labelings Of Uniform K-Distant Trees And A New Class Of Trees, Kimberly Wenger Diller

Honors Projects

A k-distant tree consists of a main path, called the spine, such that each vertex on the spine is joined by an edge to an end-vertex of at most one path on at most k vertices. Those paths, along with the edge joining them to the spine, are called tails. When every vertex on the spine has exactly one incident tail of length k we call the tree a uniform k-distant tree. We show that every uniform k-distant tree admits both a graceful- and an α-labeling.

For a graph G and a positive integer …

Recent Advances In Compressed Sensing: Discrete Uncertainty Principles And Fast Hyperspectral Imaging, Megan E. Lewis

Theses and Dissertations

Compressed sensing is an important field with continuing advances in theory and applications. This thesis provides contributions to both theory and application. Much of the theory behind compressed sensing is based on uncertainty principles, which state that a signal cannot be concentrated in both time and frequency. We develop a new discrete uncertainty principle and use it to demonstrate a fundamental limitation of the demixing problem, and to provide a fast method of detecting sparse signals. The second half of this thesis focuses on a specific application of compressed sensing: hyperspectral imaging. Conventional hyperspectral platforms require long exposure times, which …

Sandpiles, Spanning Trees, And Plane Duality, Melody Chan, Darren B. Glass, Matthew Macauley, David Perkinson, Caryn Werner, Qiaoyu Yang

Math Faculty Publications

Let G be a connected, loopless multigraph. The sandpile group of G is a finite abelian group associated to G whose order is equal to the number of spanning trees in G. Holroyd et al. used a dynamical process on graphs called rotor-routing to define a simply transitive action of the sandpile group of G on its set of spanning trees. Their definition depends on two pieces of auxiliary data: a choice of a ribbon graph structure on G, and a choice of a root vertex. Chan, Church, and Grochow showed that if G is a planar ribbon graph, it …

Periodic Body-And-Bar Frameworks, Ciprian Borcea, Ileana Streinu, Shin-Ichi Tanigawa

Computer Science: Faculty Publications

Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell–Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

Polynomials Occuring In Generating Function Identities For B-Ary Partitions, David Dakota Blair

Graduate Student Publications and Research

Let p_b(n) be the number of integer partitions of n whose parts are powers of b. For each m there is a generating function identity:

f_m(b,q)\sum_{n} p_b(n) q^n = (1-q)^m \sum_{n} p_b(b^m n q)q^n

where n ranges over all integer values. The proof of this identity appears in the doctoral thesis of the author. For more information see http://dakota.tensen.net/2015/rp/.

This dataset is a JSON object with keys m from 1 to 23 whose values are f_m(b,q).

A Plausibly Deniable Encryption Scheme For Personal Data Storage, Andrew Brockmann

HMC Senior Theses

Even if an encryption algorithm is mathematically strong, humans inevitably make for a weak link in most security protocols. A sufficiently threatening adversary will typically be able to force people to reveal their encrypted data. Methods of deniable encryption seek to mend this vulnerability by allowing for decryption to alternate data which is plausible but not sensitive. Existing schemes which allow for deniable encryption are best suited for use by parties who wish to communicate with one another. They are not, however, ideal for personal data storage. This paper develops a plausibly-deniable encryption system for use with personal data storage, …

An Exposition Of Kasteleyn's Solution Of The Dimer Model, Eric Stucky

HMC Senior Theses

In 1961, P. W. Kasteleyn provided a baffling-looking solution to an apparently simple tiling problem: how many ways are there to tile a rectangular region with dominos? We examine his proof, simplifying and clarifying it into this nearly self-contained work.