Discrete Mathematics and Combinatorics Commons^™

Pattern Containment In Circular Permutations, Charles Lanning

College of Graduate Studies: Theses & Dissertations

Pattern containment in permutations, as opposed to pattern avoidance, involves two aspects. The first is to contain every pattern at least once from a given set, known as finding superpatterns; while the second is to contain some given pattern as many times as possible, known as pattern packing. In this thesis, we explore these two questions in circular permutations and present some interesting observations. We also raise some questions and propose some directions for future study.

On A Class Of Quaternionic Positive Definite Functions And Their Derivatives, Daniel Alpay, Fabrizio Colombo, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

In this paper, we start the study of stochastic processes over the skew field of quaternions. We discuss the relation between positive definite functions and the covariance of centered Gaussian processes and the construction of stochastic processes and their derivatives. The use of perfect spaces and strong algebras and the notion of Fock space are crucial in this framework.

Characterizations Of Families Of Rectangular, Finite Impulse Response, Para-Unitary Systems, Daniel Alpay, Palle Jorgensen, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

We here study Finite Impulse Response (FIR) rectangular, not necessarily causal, systems which are (para)-unitary on the unit circle (=the class U). First, we offer three characterizations of these systems. Then, introduce a description of all FIRs in U, as copies of a real polytope, parametrized by the dimensions and the McMillan degree of the FIRs.

Finally, we present six simple ways (along with their combinations) to construct, from any FIR, a large family of FIRs, of various dimensions and McMillan degrees, so that whenever the original system is in U, so is the whole family.

A key role is …

Functions Of The Infinitesimal Generator Of A Strongly Continuous Quaternionic Group, Daniel Alpay, Fabrizio Colombo, Jonathan Gantner, David P. Kimsey

Mathematics, Physics, and Computer Science Faculty Articles and Research

The analogue of the Riesz-Dunford functional calculus has been introduced and studied recently as well as the theory of semigroups and groups of linear quaternionic operators. In this paper we suppose that T is the infinitesimal generator of a strongly continuous group of operators (ZT (t))t2R and we show how we can define bounded operators f(T ), where f belongs to a class of functions which is larger than the class of slice regular functions, using the quaternionic Laplace-Stieltjes transform. This class will include functions that are slice regular on the S-spectrum of T but not necessarily at infinity. Moreover, …

A Generalized Polynomial Identity Arising From Quantum Mechanics, Shashikant B. Mulay, John J. Quinn, Mark A. Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

We establish a general identity that expresses a Pfaffian of a certain matrix as a quotient of homogeneous polynomials. This identity arises in the study of weakly interacting many-body systems and its proof provides another way of realizing the equivalence of two proposed types of trial wave functions used to describe such systems. In the proof of our identity, we make use of only elementary linear algebra and combinatorics and thereby avoid use of more advanced conformal field theory in establishing the aforementioned equivalence.

The History Of Algorithmic Complexity, Audrey A. Nasar

Publications and Research

This paper provides a historical account of the development of algorithmic complexity in a form that is suitable to instructors of mathematics at the high school or undergraduate level. The study of algorithmic complexity, despite being deeply rooted in mathematics, is usually restricted to the computer science curriculum. By providing a historical account of algorithmic complexity through a mathematical lens, this paper aims to equip mathematics educators with the necessary background and framework for incorporating the analysis of algorithmic complexity into mathematics courses as early on as algebra or pre-calculus.

Latin Squares And Their Applications To Cryptography, Nathan O. Schmidt

Boise State University Theses and Dissertations

A latin square of order-n is an n x n array over a set of n symbols such that every symbol appears exactly once in each row and exactly once in each column. Latin squares encode features of algebraic structures. When an algebraic structure passes certain "latin square tests", it is a candidate for use in the construction of cryptographic systems. A transversal of a latin square is a list of n distinct symbols, one from each row and each column. The question regarding the existence of transversals in latin squares that encode the Cayley tables of finite groups …

Matching Transversal Edge Domination In Graphs, Anwar Alwardi

Applications and Applied Mathematics: An International Journal (AAM)

Let G =(V,E) be a graph. A subset X of E is called an edge dominating set of G if every edge in E - X is adjacent to some edge in X . An edge dominating set which intersects every maximum matching inG is called matching transversal edge dominating set. The minimum cardinality of a matching transversal edge dominating set is called the matching transversal edge domination number of G and is denoted by γ_mt(G). In this paper, we begin an investigation of this parameter.

Planar Graphs, Biplanar Graphs And Graph Thickness, Sean M. Hearon

Electronic Theses, Projects, and Dissertations

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.

Bounds On The Expected Size Of The Maximum Agreement Subtree, Colby Long, Daniel Irving Bernstein, Lam Si Tung Ho, Mike Steel, Katherine St. John, Seth Sullivant

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Exploring The Space Of Rna Secondary Structures, Heather C. Smith

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Markov Chains On Graphical Models Of Gene Regulation, Megan Bernstein

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Genome Rearrangement: Graphs And Matrices, Jeffrey Davis

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

On The Expected Number Of Crossings In A Tanglegram, Eva Czabarka

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

On The Perfect Reconstruction Of The Structure Of Dynamic Networks, Alan Veliz-Cuba

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Spectral Graph Theory And New Stability Measures For Deterministic Gene Regulatory Networks, Fusun Akman, Devin Akman

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Cycle Structures Of Orthomorphisms Extending Partial Orthomorphisms Of Boolean Groups, Nichole Louise Schimanski, John S. Caughman Iv

Mathematics and Statistics Faculty Publications and Presentations

A partial orthomorphism of a group GG (with additive notation) is an injection π:S→G for some S⊆G such that π(x)−x ≠ π(y) for all distinct x,y∈S. We refer to |S| as the size of π, and if S=G, then π is an orthomorphism. Despite receiving a fair amount of attention in the research literature, many basic questions remain concerning the number of orthomorphisms of a given group, and what cycle types these permutations have.

It is known that conjugation by automorphisms of G forms a group action on the set of orthomorphisms of G. In this paper, we consider the …

On The Geodesic Centers Of Polygonal Domains, Haitao Wang

Computer Science Faculty and Staff Publications

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain P of n vertices. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of P that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the size of the shortest path map equivalence decomposition of P, which is known to be O(n^{10}). One key observation is a pi-range property on shortest path lengths when points are moving. With these observations, …

Improving Proof-Writing With Reading Guides, Mike Janssen

Faculty Work Comprehensive List

One of the barriers in the transition to advanced mathematics is that the proofs and ideas in even the best mathematics texts must be read more carefully than many students are accustomed to. Yet in order to learn to write proofs well, one must learn how to read proofs well. Borrowing an idea from Lewis Ludwig, I flipped my introduction to proofs (discrete structures) course in Spring 2016 with the use of reading guides. Each day, students were responsible for reading a section of the text and completing a worksheet that highlighted the main points, asked students to create their …

An Update On A Few Permanent Conjectures, Fuzhen Zhang

Mathematics Faculty Articles

We review and update on a few conjectures concerning matrix permanent that are easily stated, understood, and accessible to general math audience. They are: Soules permanent-on-top conjecture†, Lieb permanent dominance conjecture, Bapat and Sunder conjecture† on Hadamard product and diagonal entries, Chollet conjecture on Hadamard product, Marcus conjecture on permanent of permanents, and several other conjectures. Some of these conjectures are recently settled; some are still open.We also raise a few new questions for future study. (†conjectures have been recently settled negatively.)