Discrete Mathematics and Combinatorics Commons^™

Distribution Of Permutation Statistics Across Pattern Avoidance Classes, And The Search For A Denert-Associated Condition Equivalent To Pattern Avoidance, Joshua Thomas Agustin Davies

Dissertations, Master's Theses and Master's Reports

We begin with a discussion of the symmetricity of $\maj$ over $\des$ in pattern avoidance classes, and its relationship to $\maj$-Wilf equivalence. From this, we explore the distribution of permutation statistics across pattern avoidance for patterns of length 3 and 4.

We then begin discussion of Han's bijection, a bijection on permutations which sends the major index to Denert's statistic and the descent number to the (strong) excedance number. We show the existence of several infinite families of fixed points for Han's bijection.

Finally, we discuss the image of pattern avoidance classes under Han's bijection, for the purpose of finding …

Distance Magic-Type And Distance Antimagic-Type Labelings Of Graphs, Bryan Freyberg

Dissertations, Master's Theses and Master's Reports

Generally speaking, a distance magic-type labeling of a graph G of order n is a bijection f from the vertex set of the graph to the first n natural numbers or to the elements of a group of order n, with the property that the weight of each vertex is the same. The weight of a vertex x is defined as the sum (or appropriate group operation) of all the labels of vertices adjacent to x. If instead we require that all weights differ, then we refer to the labeling as a distance antimagic-type labeling. This idea can be generalized …

Edge Colorings Of K(M,N) With M+N-1 Colors Which Forbid Rainbow Cycles, Peter Johnson, Claire Zhang

Theory & Applications of Graphs

For positive integers m, n, the greatest number of colors that can appear in an edge coloring of K(m,n) which avoids rainbow cycles is m + n - 1. Here these colorings are constructively characterized. It turns out that these colorings can be encoded by certain vertex labelings of full binary trees with m + n leafs.

An Eternal Domination Problem In Grids, William Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello

Theory & Applications of Graphs

A dynamic domination problem in graphs is considered in which an infinite sequence of attacks occur at vertices with mobile guards; the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack, the vertices containing guards must form a dominating set of the graph. The minimum number of guards that can defend the graph against such an arbitrary sequence of attacks is called the m-eviction number of the graph. In this paper, the m-eviction …

Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb

Theory & Applications of Graphs

A perfect forest is a spanning forest of a connected graph G, all of whose components are induced subgraphs of G and such that all vertices have odd degree in the forest. A perfect forest can be thought of as a generalization of a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra.

We give here two very short proofs of the Perfect Forest Theorem which use only …

Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica Mcdonald

Theory & Applications of Graphs

An extremal result about vertex covers, attributed by Hajnal to Erdős and Gallai, is applied to prove the following: If n, k, and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2t - 2, and G is a graph with the minimum number of edges among graphs on n vertices with the property that every induced subgraph on k vertices contains a complete subgraph on t vertices, then every component of G is complete.

Network Analytics For The Mirna Regulome And Mirna-Disease Interactions, Joseph Jayakar Nalluri

Theses and Dissertations

miRNAs are non-coding RNAs of approx. 22 nucleotides in length that inhibit gene expression at the post-transcriptional level. By virtue of this gene regulation mechanism, miRNAs play a critical role in several biological processes and patho-physiological conditions, including cancers. miRNA behavior is a result of a multi-level complex interaction network involving miRNA-mRNA, TF-miRNA-gene, and miRNA-chemical interactions; hence the precise patterns through which a miRNA regulates a certain disease(s) are still elusive. Herein, I have developed an integrative genomics methods/pipeline to (i) build a miRNA regulomics and data analytics repository, (ii) create/model these interactions into networks and use optimization techniques, motif …

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

Dynamics Of Gene Networks In Cancer Research, Paul Scott

College of Graduate Studies: Theses & Dissertations

Cancer prevention treatments are being researched to see if an optimized treatment schedule would decrease the likelihood of a person being diagnosed with cancer. To do this we are looking at genes involved in the cell cycle and how they interact with one another. Through each gene expression during the life of a normal cell we get an understanding of the gene interactions and test these against those of a cancerous cell. First we construct a simplified network model of the normal gene network. Once we have this model we translate it into a transition matrix and force changes on …

Graph Invariants Of Trees With Given Degree Sequence, Rachel Bass

College of Graduate Studies: Theses & Dissertations

Graph invariants are functions defined on the graph structures that stay the same under taking graph isomorphisms. Many such graph invariants, including some commonly used graph indices in Chemical Graph Theory, are defined on vertex degrees and distances between vertices. We explore generalizations of such graph indices and the corresponding extremal problems in trees. We will also briefly mention the applications of our results.

Combinatorics Of Compositions, Meghann M. Gibson

College of Graduate Studies: Theses & Dissertations

Integer compositions and related enumeration problems have been extensively studied. The cyclic analogues of such questions, however, have significantly fewer results. In this thesis, we follow the cyclic construction of Flajolet and Soria to obtain generating functions for cyclic compositions and n-color cyclic compositions with various restrictions. With these generating functions we present some statistics and asymptotic formulas for the number of compositions and parts in such compositions. Combinatorial explanations are also provided for many of the enumerative observations presented.

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.