Discrete Mathematics and Combinatorics Commons^™

An Enumeration Of Nested Networks, Nathan Cornelius

Williams Honors College, Honors Research Projects

Nested networks have several applications in phylogenetics and electrical circuit theory. In many cases, there may exist more than one distinct network which correctly models a given data set. This proposes a combinatorial problem to determine all possible network solutions. In this paper, we partially solve this problem by developing exponential generating functions which enumerate all 1-nested and 2-nested unicyclic networks. We also describe our procedure to directly count all 1-nested and 2-nested networks and provide all 1-nested networks with 7, 8, and 9 terminal nodes.

Tiling Representations Of Zeckendorf Decompositions, John Lentfer

HMC Senior Theses

Zeckendorf’s theorem states that every positive integer can be decomposed uniquely into a sum of non-consecutive Fibonacci numbers (where f₁ = 1 and f₂ = 2). Previous work by Grabner and Tichy (1990) and Miller and Wang (2012) has found a generalization of Zeckendorf’s theorem to a larger class of recurrent sequences, called Positive Linear Recurrence Sequences (PLRS’s). We apply well-known tiling interpretations of recurrence sequences from Benjamin and Quinn (2003) to PLRS’s. We exploit that tiling interpretation to create a new tiling interpretation specific to PLRS’s that captures the behavior of the generalized Zeckendorf’s theorem.

Exploring Plane Partitions, Nicholas Heim

Williams Honors College, Honors Research Projects

The combinatorial theory of partitions has a number of applications including the representation theory of the symmetric group. A particularly important result counts the number of standard Young tableau of a given partition in terms of the hook lengths of the partition. In this paper we explore the analog of the hook length formula for plane partitions, the three-dimensional analog of ordinary partitions. We show that equality does not always hold but we conjecture that a certain inequality holds. Using a computer program, we verify this conjectured inequality for all 1982 plane partitions up to n = 11.

Integer Partitions Under Certain Finiteness Conditions, Tim Wagner

Dissertations, Master's Theses and Master's Reports

This dissertation focuses on problems related to integer partitions under various finiteness restrictions. Much of our work involves the collection of partitions fitting inside a fixed partition $\lambda$, and the associated generating function $G_{\lambda}$.

In Chapter 2, we discuss the flawlessness of such generating functions, as proved by Pouzet using the Multicolor Theorem. We give novel applications of the Multicolor Theorem to re-prove flawlessness of pure $O$-sequences, and show original flawlessness results for other combinatorial sequences. We also present a linear-algebraic generalization of the Multicolor Theorem that may have far-reaching applications.

In Chapter 3, we extend a technique due to …

On The Ranks Of String C-Group Representations For Symplectic And Orthogonal Groups, Peter A. Brooksbank

Faculty Journal Articles

We determine the ranks of string C-group representations of the groups PSp(4,q)=Ω(5,q), and comment on those of higher-dimensional symplectic and orthogonal groups.

Heterogeneous Generalizations Of Vertex Coloring, Lucia Ciletti Mazza

Graduate Theses, Dissertations, and Problem Reports (ETD)

This dissertation proves a collection of results in some heterogeneous generalizations of vertex coloring, i.e. generalizations in which the relationship between the colors of two adjacent vertices may differ throughout the graph. For the most part, the results are from group coloring, group list coloring, and DP coloring. The main results are as follows: a group list coloring analogue of Brooks' Theorem for multigraphs, a result linking group structure (rather than only group size) with group coloring, some results involving coloring edge-disjoint unions, and an examination of the relationship between the group and DP coloring numbers of a multigraph and …

Algebraic, Analytic, And Combinatorial Properties Of Power Product Expansions In Two Independent Variables., Mohamed Ammar Elewoday

Graduate Theses, Dissertations, and Problem Reports (ETD)

Let $F(x,y)=I+\hspace{-.3cm}\sum\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}A_{m,n}x^my^n$ be a formal power series, where the coefficients $A_{m,n}$ are either all matrices or all scalars. We expand $F(x,y)$ into the formal products $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I+G_{m,n}x^m y^n)$, $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I-H_{m,n}x^m y^n)^{-1}$, namely the \textit{ power product expansion in two independent variables} and \textit{inverse power product expansion in two independent variables} respectively. By developing new machinery involving the majorizing infinite product, we provide estimates on the domain of absolute convergence of the infinite product via the Taylor series coefficients of $F(x,y)$. This machinery introduces a myriad of "mixed expansions", uncovers various algebraic connections between the $(A_{m,n})$ and the $(G_{m,n})$, and uncovers various algebraic …

Approximation By The K^Lambda Means Of Fourier Series And Conjugate Series Of Functions In H_{Alpha,P}, Ben Landon, Holly Carley, R. N. Mohapatra

Publications and Research

No abstract provided.

Addendum For The Article Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory & Applications of Graphs

Additional references listed for the article: Saha, Laxman and Basunia, Alamgir Rahaman (2020) "Radio Graceful Labelling of Graphs," Theory and Applications of Graphs: Vol. 7: Iss. 1, Article 7. DOI: 10.20429/tag.2020.070107

Super Sudoku Squares, Dean Hoffman

Communications on Number Theory and Combinatorial Theory

We refer to a completed Sudoku puzzle as a Sudoku Square of order 3. We define a more restricted, but natural, extension --- a Super Sudoku Square of order n, and determine for which orders n one exists.

Prime Supporters In College Students' Support Networks, David Chan, Hollee Mcginnis, Michael Broda, Haya Hamid, Jeremy Winslow, Quindel Jones, Joy Ma

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Algebraic And Combinatorial Approaches For Counting Cycles Arising In Population Biology, Brian Chau

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Dna Self-Assembly Design For Gear Graphs, Chiara Mattamira

Rose-Hulman Undergraduate Mathematics Journal

Application of graph theory to the well-known complementary properties of DNA strands has resulted in new insights about more efficient ways to form DNA nanostructures, which have been discovered as useful tools for drug delivery, biomolecular computing, and biosensors. The key concept underlying DNA nanotechnology is the formation of complete DNA complexes out of a given collection of branched junction molecules. These molecules can be modeled in the abstract as portions of graphs made up of vertices and half-edges, where complete edges are representations of double-stranded DNA pieces that have joined together. For efficiency, one aim is to minimize the …

The Name Tag Problem, Christian Carley

Rose-Hulman Undergraduate Mathematics Journal

The Name Tag Problem is a thought experiment that, when formalized, serves as an introduction to the concept of an orthomorphism of $\Zn$. Orthomorphisms are a type of group permutation and their graphs are used to construct mutually orthogonal Latin squares, affine planes and other objects. This paper walks through the formalization of the Name Tag Problem and its linear solutions, which center around modular arithmetic. The characterization of which linear mappings give rise to these solutions developed in this paper can be used to calculate the exact number of linear orthomorphisms for any additive group Z/nZ, which is demonstrated …

Investigating First Returns: The Effect Of Multicolored Vectors, Shakuan Frankson, Myka Terry

Rose-Hulman Undergraduate Mathematics Journal

By definition, a first return is the immediate moment that a path, using vectors in the Cartesian plane, touches the x-axis after leaving it previously from a given point; the initial point is often the origin. In this case, using certain diagonal and horizontal vectors while restricting the movements to the first quadrant will cause almost every first return to end at the point (2n,0), where 2n counts the equal number of up and down steps in a path. The exception will be explained further in the sections below. Using the first returns of Catalan, Schröder, and Motzkin numbers, which …

On The Enumeration Of Shapes, May Cai, Nicholas Liao

Rose-Hulman Undergraduate Mathematics Journal

We define a shape as a union of finitely many line segments. Given an arrangement of lines on a plane, we count the number of shapes in the arrangement by examining the symmetries of the arrangement and applying Burnside's lemma. We further establish a generating function for the number of distinct line segments on a line with k distinguished points. We list all affine line arrangements of four and five line segments, together with the corresponding number of shapes on them.

Iterated Line Graphs On Bi-Regular Graphs And Trees, Brenden Balch

Rose-Hulman Undergraduate Mathematics Journal

In 1965, van Rooij and Wilf considered sequences of line graphs, in which they grouped sequences of line graphs into four categories. We’ll add to their research by presenting results on sequences of line graphs for star graphs and bi-regular graphs. We will then investigate slight variations of star graphs.

Legendre G-Array Pairs And The Theoretical Unification Of Several G-Array Families, K. T. Arasu, Dursun A. Bulutoglu, J. R. Hollon

Faculty Publications

We investigate how Legendre G-array pairs are related to several different perfect binary G-array families. In particular we study the relations between Legendre G-array pairs, Sidelnikov-Lempel-Cohn-Eastman ℤ_q−1-arrays, Yamada-Pott G-array pairs, Ding-Helleseth-Martinsen ℤ₂×ℤ^m_p-arrays, Yamada ℤ_(q−1)/2-arrays, Szekeres ℤ^m_p-array pairs, Paley ℤ^m_p-array pairs, and Baumert ℤ^m1_p1×ℤ^m2_p2-array pairs. Our work also solves one of the two open problems posed in Ding~[J. Combin. Des. 16 (2008), 164-171]. Moreover, we provide several computer search based existence and non-existence results regarding Legendre ℤ_n-array pairs. …

Some Generalizations Of Classical Integer Sequences Arising In Combinatorial Representation Theory, Sasha Verona Malone

Masters Theses & Specialist Projects

There exists a natural correspondence between the bases for a given finite-dimensional representation of a complex semisimple Lie algebra and a certain collection of finite edge-colored ranked posets, laid out by Donnelly, et al. in, for instance, [Don03]. In this correspondence, the Serre relations on the Chevalley generators of the given Lie algebra are realized as conditions on coefficients assigned to poset edges. These conditions are the so-called diamond, crossing, and structure relations (hereinafter DCS relations.) New representation constructions of Lie algebras may thus be obtained by utilizing edge-colored ranked posets. Of particular combinatorial interest are those representations whose corresponding …

Quasilinearization Applied To Boundary Value Problems At Resonance For Riemann-Liouville Fractional Differential Equations, Paul W. Eloe, Jaganmohan Jonnalagadda

Mathematics Faculty Publications

The quasilinearization method is applied to a boundary value problem at resonance for a Riemann-Liouville fractional differential equation. Under suitable hypotheses, the method of upper and lower solutions is employed to establish uniqueness of solutions. A shift method, coupled with the method of upper and lower solutions, is applied to establish existence of solutions. The quasilinearization algorithm is then applied to obtain sequences of lower and upper solutions that converge monotonically and quadratically to the unique solution of the boundary value problem at resonance.