Mathematics Commons^™

Towards A Theory Of Recursive Function Complexity: Sigma Matrices And Inverse Complexity Measures, Bradford M. Fournier

University of New Orleans Theses and Dissertations

This paper develops a data structure based on preimage sets of functions on a finite set. This structure, called the sigma matrix, is shown to be particularly well-suited for exploring the structural characteristics of recursive functions relevant to investigations of complexity. The matrix is easy to compute by hand, defined for any finite function, reflects intrinsic properties of its generating function, and the map taking functions to sigma matrices admits a simple polynomial-time algorithm . Finally, we develop a flexible measure of preimage complexity using the aforementioned matrix. This measure naturally partitions all functions on a finite set by characteristics …

F–Geometric Mean Graphs, A. D. Baskar, S. Arockiaraj

Applications and Applied Mathematics: An International Journal (AAM)

In a study of traffic, the labelling problems in graph theory can be used by considering the crowd at every junction as the weights of a vertex and expected average traffic in each street as the weight of the corresponding edge. If we assume the expected traffic at each street as the arithmetic mean of the weight of the end vertices, that causes mean labelling of the graph. When we consider a geometric mean instead of arithmetic mean in a large population of a city, the rate of growth of traffic in each street will be more accurate. The geometric …

In Honor And Memory Of Professor Lajos Takács, Aliakbar M. Haghighi, Sri G. Mohanty

Applications and Applied Mathematics: An International Journal (AAM)

This issue of AAM is dedicated to honoring and remembering Professor Lajos Takács. While wrapping up the manuscript of my book (co-authored by Dr. Dimitar Mishev): Delayed and Network Queues, I went back to celebrate his 1962 book, Introduction to the Theory of Queues, where he gives an example illustrating a waiting time paradox, where the waiting time of a passenger waiting for a bus at a bus stop is infinite, while, in reality, he will wait a finite unit of time before a bus arrive. I sent Professor Takács an e-mail on December 4, 2015, inquiring if he had …

Independent Monopoly Size In Graphs, Ahmed M. Naji, N. D. Soner

Applications and Applied Mathematics: An International Journal (AAM)

In a graph G = (V;E), a set D ⊆V (G) is said to be a monopoly set of G if every vertex v ∈V-D has at least d(v)/ 2 neighbors in D. The monopoly size of G, denoted mo(G), is the minimum cardinality of a monopoly set among all monopoly sets in G. The set D ⊆ V (G) is an independent monopoly set in G if it is both a monopoly set and an independent set in G. The number of vertices in a minimum independent monopoly set in a graph G is the independent monopoly size of …

Solution To Some Open Problems On E-Super Vertex Magic Total Labeling Of Graphs, G. Marimuthu, M. S. Raja Durga, G. D. Devi

Applications and Applied Mathematics: An International Journal (AAM)

Let G be a finite graph with p vertices and q edges. A vertex magic total labeling is a bijection f from V(G)∪E(G) to the consecutive integers 1, 2, ..., p+q with the property that for every u∈V(G) , f( u)+ ∑f(uv)=K for some constant k. Such a labeling is E-super if f :E(G)→{1, 2,..., q}. A graph G is called E-super vertex magic if it admits an E-super vertex magic labeling. In this paper, we solve two open problems given by Marimuthu, Suganya, Kalaivani and Balakrishnan (Marimuthu et al., 2015).

Skew Row-Strict Quasisymmetric Schur Functions, Sarah K. Mason, Elizabeth Niese

Mathematics Faculty Research

Mason and Remmel introduced a basis for quasisymmetric functions known as the row-strict quasisymmetric Schur functions. This basis is generated combinatorially by fillings of composition diagrams that are analogous to the row-strict tableaux that generate Schur functions. We introduce a modification known as Young row-strict quasisymmetric Schur functions, which are generated by row-strict Young composition fillings. After discussing basic combinatorial properties of these functions, we define a skew Young row-strict quasisymmetric Schur function using the Hopf algebra of quasisymmetric functions and then prove this is equivalent to a combinatorial description. We also provide a decomposition of the skew Young row-strict …

A Nonlinear Filter For Markov Chains And Its Effect On Diffusion Maps, Stefan Steinerberger

Yale Day of Data

Diffusion maps are a modern mathematical tool that helps to find structure in large data sets - we present a new filtering technique that is based on the assumption that errors in the data are intrinsically random to isolate and filter errors and thus boost the efficiency of diffusion maps. Applications include data sets from medicine (the Cleveland Heart Disease Data set and the Wisconsin Breast Cancer Data set) and engineering (the Ionosphere data set).

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 …

On The Topology Of The Permutation Pattern Poset, Peter R. W. Mcnamara, Einar Steingrímsson

Faculty Journal Articles

The set of all permutations, ordered by pattern containment, forms a poset. This paper presents the first explicit major results on the topology of intervals in this poset. We show that almost all (open) intervals in this poset have a disconnected subinterval and are thus not shellable. Nevertheless, there seem to be large classes of intervals that are shellable and thus have the homotopy type of a wedge of spheres. We prove this to be the case for all intervals of layered permutations that have no disconnected subintervals of rank 3 or more. We also characterize in a simple way …

The Robinson-Schensted Correspondence And A2-Web Bases, Matthew Housley, Heather M. Russell, Julianna Tymoczko

Mathematics Sciences: Faculty Publications

We study natural bases for two constructions of the irreducible representation of the symmetric group corresponding to [n, n, n]: the reduced web basis associated to Kuperberg’s combinatorial description of the spider category; and the left cell basis for the left cell construction of Kazhdan and Lusztig. In the case of [n, n], the spider category is the Temperley-Lieb category; reduced webs correspond to planar matchings, which are equivalent to left cell bases. This paper compares the image of these bases under classical maps: the Robinson–Schensted algorithm between permutations and Young tableaux and Khovanov–Kuperberg’s bijection between Young tableaux and reduced …

Graph Centers, Hypergraph Degree Sequences, And Induced-Saturation, Sarah Lynne Behrens

Department of Mathematics: Dissertations, Theses, and Student Research

The center of a graph is the set of vertices whose distance to other vertices is minimal. The centralizing number of a graph G is the minimum number of additional vertices in any graph H where V(G) is the center of H. Buckley, Miller, and Slater and He and Liu provided infinite families of graphs with each centralizing number. We show the number of graphs with each nonzero centralizing number grows super-exponentially with the number of vertices. We also provide a method of altering graphs without changing the centralizing number and give results about the centralizing …

On A Convex Set With Nondifferentiable Metric Projection, Shyan S. Akmal, Nguyen Mau Nam, J. J. P. Veerman

Mathematics and Statistics Faculty Publications and Presentations

A remarkable example of a nonempty closed convex set in the Euclidean plane for which the directional derivative of the metric projection mapping fails to exist was constructed by A. Shapiro. In this paper, we revisit and modify that construction to obtain a convex set with smooth boundary which possesses the same property.

On The Topology Of The Permutation Pattern Poset, Peter R. W. Mcnamara, Einar Steingrímsson

Peter R. W. McNamara

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.

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 …

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, . . …

Commutative N-Ary Arithmetic, Aram Bingham

University of 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 …

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.

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 …

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

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 …

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

GS4 Georgia Southern 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 …

Examining The Literature On “Networks In Space And In Time.” An Introduction, Luca De Benedictis, Prosperina Vitale, Stanley Wasserman

Luca De Benedictis

The Network science special issue of “Networks in space and in time: methods and applications” contributes to the debate on contextual analysis in network science. It includes seven research papers that shed light on the analysis of network phenomena studied within geographic space and across temporal dimensions. In these papers, methodological issues as well as specific applications are described from different fields. We take the seven papers, study their citations and texts, and relate them to the broader literature. By exploiting the bibliographic information and the textual data of these seven documents, citation analysis and lexical correspondence analysis allow us …

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 …

Combinatorics Of Equivariant Cohomology: Flags And Regular Nilpotent Hessenberg Varieties, Elizabeth J. Drellich

Doctoral Dissertations

The field of Schubert Calculus deals with computations in the cohomology rings of certain algebraic varieties, including flag varieties and Schubert varieties. In the equivariant setting, GKM theory turns multiplication in the cohomology ring of certain varieties into a combinatorial computation. This dissertation uses combinatorial tools, including Billey’s formula, to do Schubert calculus computations in several varieties. First we address do computations in the equivariant cohomology of full and partial flag varieties, the classical spaces in Schubert calculus. We then do computations in the equivariant cohomology of a family of non-classical spaces: regular nilpotent Hessenberg varieties. The final chapter gives …

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 …