Discrete Mathematics and Combinatorics Commons^™

Problems In Chemical Graph Theory Related To The Merrifield-Simmons And Hosoya Topological Indices, William B. O'Reilly

College of Graduate Studies: Theses & Dissertations

In some sense, chemical graph theory applies graph theory to various physical sciences. This interdisciplinary field has significant applications to structure property relationships, as well as mathematical modeling. In particular, we focus on two important indices widely used in chemical graph theory, the Merrifield-Simmons index and Hosoya index. The Merrifield-Simmons index and the Hosoya index are two well-known topological indices used in mathematical chemistry for characterizing specific properties of chemical compounds. Substantial research has been done on the two indices in terms of enumerative problems and extremal questions. In this thesis, we survey known extremal results and consider the generalized …

Enumeration Of Lattice Paths With Restrictions, Vince White

College of Graduate Studies: Theses & Dissertations

Lattice path enumeration, through the lens of Catalan numbers, plays a crucial role in combinatorics. This thesis delves into enumerations of some of the most common lattice paths – north-east paths, up-down paths, and Dyck paths – with restrictions applied. The first restriction is counting north-east lattice paths that only cross the diagonal line, y=x, once. The second form of lattice paths with restrictions is up-down paths that cross the x-axis exactly once and fall to a fixed depth of k. While working through this module, a novel proof for a known integer sequence was used, then applied to generate …

Counting Conjugates Of Colored Compositions, Jesus Omar Sistos Barron

Honors College Theses

The properties of n-color compositions have been studied parallel to those of regular compositions. The conjugate of a composition as defined by MacMahon, however, does not translate well to n-color compositions, and there is currently no established analogous concept. We propose a conjugation rule for cyclic n-color compositions. We also count the number of self-conjugates under these rules and establish a couple of connections between these and regular compositions.

Zeckendorf Representation Analysis On Third Order Fibonacci Sequences That Do Not Satisfy The Uniqueness Property, Samuel A. Aguilar

Honors College Theses

Zeckendorf's Theorem states that every natural number can be expressed uniquely as the sum of distinct non-consecutive terms of the shifted Fibonacci sequence (i.e. 1, 2, 3, 5, ...). This theorem has motivated the study of representation of integers by the sum of non-adjacent terms of Nth order Fibonacci sequences, including the characterization of the uniqueness of Zeckendorf representation based on the initial terms of the sequence. Moreover, when this uniqueness property is satisfied for third order Fibonacci sequences, the ratio of integers less than a given number X that have a Zeckendorf representation has been estimated by Dr. Sungkon …

A Combinatorial Model For Affine Demazure Crystals Of Levels Zero And One, Samuel Spellman

Electronic Theses & Dissertations (2024 - present)

The symmetric and non-symmetric Macdonald polynomials are special families of orthogonal polynomials with parameters q and t. They are indexed by dominant, (resp. arbitrary) weights associated to a root system and generalize several well-known polynomials such as the Schur polynomials, Jack polynomials, Hall-Littlewood polynomials, etc. There are two well-known combinatorial models for computing these polynomials: a tableau model in type A, due to Haglund, Haiman and Loehr, and a type-independent model due to Ram and Yip, based on alcove walks.

Crystals bases are an important construction encoding information about Lie algebra representations. It turns out that there is an interesting …

Reducing Food Scarcity: The Benefits Of Urban Farming, S.A. Claudell, Emilio Mejia

Journal of Nonprofit Innovation

Urban farming can enhance the lives of communities and help reduce food scarcity. This paper presents a conceptual prototype of an efficient urban farming community that can be scaled for a single apartment building or an entire community across all global geoeconomics regions, including densely populated cities and rural, developing towns and communities. When deployed in coordination with smart crop choices, local farm support, and efficient transportation then the result isn’t just sustainability, but also increasing fresh produce accessibility, optimizing nutritional value, eliminating the use of ‘forever chemicals’, reducing transportation costs, and fostering global environmental benefits.

Imagine Doris, who is …

Difference Of Facial Achromatic Numbers Between Two Triangular Embeddings Of A Graph, Kengo Enami, Yumiko Ohno

Theory & Applications of Graphs

A facial $3$-complete $k$-coloring of a triangulation $G$ on a surface is a vertex $k$-coloring such that every triple of $k$-colors appears on the boundary of some face of $G$. The facial $3$-achromatic number $\psi_3(G)$ of $G$ is the maximum integer $k$ such that $G$ has a facial $3$-complete $k$-coloring. This notion is an expansion of the complete coloring, that is, a proper vertex coloring of a graph such that every pair of colors appears on the ends of some edge.

For two triangulations $G$ and $G'$ on a surface, $\psi_3(G)$ may not be equal to $\psi_3(G')$ even if $G$ …

The Ricci Curvature On Simplicial Complexes, Taiki Yamada

Theory & Applications of Graphs

We define the Ricci curvature on simplicial complexes modifying the definition of the Ricci curvature on graphs, and prove upper and lower bounds of the Ricci curvature. These properties are generalizations of previous studies. Moreover, we obtain an estimate of the eigenvalues of the Laplacian on simplicial complexes by the Ricci curvature.

Toughness Of Recursively Partitionable Graphs, Calum Buchanan, Brandon Du Preez, K. E. Perry, Puck Rombach

Theory & Applications of Graphs

A simple graph G = (V,E) on n vertices is said to be recursively partitionable (RP) if G ≃ K1, or if G is connected and satisfies the following recursive property: for every integer partition a₁, a₂, . . . , a_k of n, there is a partition {A₁,A₂, . . . ,A_k} of V such that each |A_i| = a_i, and each induced subgraph G[A_i] is RP (1 ≤ i ≤ k). We show that if S is a …

Wiener Index In Graphs Given Girth, Minimum, And Maximum Degrees, Fadekemi J. Osaye, Liliek Susilowati, Alex S. Alochukwu, Cadavious Jones

Theory & Applications of Graphs

Let $G$ be a connected graph of order $n$. The Wiener index $W(G)$ of $G$ is the sum of the distances between all unordered pairs of vertices of $G$. The well-known upper bound $\big( \frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph of order $n$ and minimum degree $\delta$ by Kouider and Winkler \cite{Kouider} was improved significantly by Alochukwu and Dankelmann \cite{Alex} for graphs containing a vertex of large degree $\Delta$ to $W(G) \leq {n-\Delta+\delta \choose 2} \big( \frac{n+2\Delta}{\delta+1}+4 \big)$. In this paper, we give upper bounds on the Wiener index of $G$ in terms of order …

On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak

Theory & Applications of Graphs

The Balanced Connected Subgraph problem (BCS) was introduced by Bhore et al. In the BCS problem we are given a vertex-colored graph G = (V, E) where each vertex is colored “red” or “blue”. The goal is to find a maximum cardinality induced connected subgraph H of G such that H contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as many special classes of graphs. In this work we explore the time complexity of the BCS problem in case of regular graphs. We prove that the BCS …

The Vulnerabilities To The Rsa Algorithm And Future Alternative Algorithms To Improve Security, James Johnson

Cybersecurity Undergraduate Research Showcase

The RSA encryption algorithm has secured many large systems, including bank systems, data encryption in emails, several online transactions, etc. Benefiting from the use of asymmetric cryptography and properties of number theory, RSA was widely regarded as one of most difficult algorithms to decrypt without a key, especially since by brute force, breaking the algorithm would take thousands of years. However, in recent times, research has shown that RSA is getting closer to being efficiently decrypted classically, using algebraic methods, (fully cracked through limited bits) in which elliptic-curve cryptography has been thought of as the alternative that is stronger than …

Discrete Complementary Exponential And Sine Integral Functions, Samer Assaf, Tom Cuchta

Mathematics Faculty Research

Discrete analogues of the sine integral and complementary exponential integral functions are investigated. Hypergeometric representation, power series, and Laplace transforms are derived for each. The difficulties in extending these definitions to other common trigonometric integral functions are discussed.

Foundations Of Memory Capacity In Models Of Neural Cognition, Chandradeep Chowdhury

Master's Theses

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the …

A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu

Electronic Theses and Dissertations

Graph Neural Networks and Transformers are very powerful frameworks for learning machine learning tasks. While they were evolved separately in diverse fields, current research has revealed some similarities and links between them. This work focuses on bridging the gap between GNNs and Transformers by offering a uniform framework that highlights their similarities and distinctions. We perform positional encodings and identify key properties that make the positional encodings node embeddings. We found that the properties of expressiveness, efficiency and interpretability were achieved in the process. We saw that it is possible to use positional encodings as node embeddings, which can be …

Zero-Knowledge Reductions And Confidential Arithmetic, Marvin Jones

All Dissertations

The changes in computing paradigms to shift computations to third parties have resulted in the necessity of these computations to be provable. Zero-knowledge arguments are probabilistic arguments that are used to to verify computations without secret data being leaked to the verifying party.

In this dissertation, we study zero-knowledge arguments with specific focus on reductions. Our main contributions are:

1. Provide a thorough survey in a variety of zero-knowledge techniques and protocols.
2. Prove various results of reductions that can be used to study interactive protocols in terms of subroutines. Additionally, we identify an issue in the analogous definition of zero-knowledge for …

Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham

All Theses

Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.

Jumping Frogs On Cyclic Graphs, Jake Mitchell

Honors College Theses

From the traditional game of Solitaire to modern video games like Candy Crush and Five Nights at Freddy’s, single-player games have captivated audiences for gener- ations. We investigate a lesser-known single-player game, the Jumping Frogs problem, on various classes of simple graphs, a graph with no multiple edges or looped ver- tices. We determine whether frogs can be stacked together on one vertex of a given graph. In a graph with k vertices and one frog on each vertex, the frogs must make legal jumps to form a stack of k frogs. The problem is known to be solvable on …

Combinatorially Orthogonal Paths, Sean A. Bailey, David E. Brown, Leroy Beaseley

Communications on Number Theory and Combinatorial Theory

Vectors x=(x₁,x₂,...,x_n)^T and y=(y₁,y₂,...,y_n)^T are combinatorially orthogonal if |{i:x_iy_i≠0}|≠1. An undirected graph G=(V,E) is a combinatorially orthogonal graph if there exists f:V→ℝⁿ such that for any u,v∈V, uv∉E iff f(u) and f(v) are combinatorially orthogonal. We will show that every graph has a combinatorially orthogonal representation. We will show …

Msis-Kadelka: On The Uniqueness Of Network Identification, Alan Veliz-Cuba, Elena Dimitrova

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.