Computationally hard problems are routinely encountered during the course of solving practical problems. This is commonly dealt with by settling for less than optimal solutions, through the use of heuristics or approximation algorithms. This dissertation examines the alternate possibility of solving such problems exactly, through a detailed study of one particular problem, the maximum clique problem. It discusses algorithms, implementations, and the application of maximum clique results to real-world problems. First, the theoretical roots of the algorithmic method employed are discussed. Then a practical approach is described, which separates out important algorithmic decisions so that the algorithm can be easily tuned for different types of input data. This general and modifiable approach is also meant as a tool for research so that different strategies can easily be tried for different situations. Next, a specific implementation is described. The program is tuned, by use of experiments, to work best for two different graph types, real-world biological data and a suite of synthetic graphs. A parallel implementation is then briefly discussed and tested. After considering implementation, an example of applying these clique-finding tools to a specific case of real-world biological data is presented. Results are analyzed using both statistical and biological metrics. Then the development of practical algorithms based on clique-finding tools is explored in greater detail. New algorithms are introduced and preliminary experiments are performed. Next, some relaxations of clique are discussed along with the possibility of developing new practical algorithms from these variations. Finally, conclusions and future research directions are given.

Followed two different proofs of van der Waerden's theorem. Found that the two proofs yield important information about arithmetic progressions and the theorem. van der Waerden's theorem explains the occurrence of arithmetic progressions which can be used to explain such things as the Bible Code.

Rational expectations provide people or economic agents making future decision with available information and past experiences. The first approach to the idea of rational expectations was given approximately fifty years ago by John F. Muth. Many models in economics have been studied using the rational expectations idea. The most familiar one among them is the rational expectations version of the Cagans hyperination model where the expectation for tomorrow is formed using all the information available today. This model was reinterpreted by Thomas J. Sargent and Neil Wallace in 1973. After that time, many solution techniques were suggested to solve the Cagan type rational expectations (CTRE) model. Some economists such as Muth [13], Taylor [26] and Shiller [27] consider the solutions admitting an infinite moving-average representation. Blanchard and Kahn [28] find solutions by using a recursive procedure. A general characterization of the solution was obtained using the martingale approach by Broze, Gourieroux and Szafarz in [22], [23]. We choose to study martingale solution of CTRE model. This thesis is comprised of five chapters where the main aim is to study the CTRE model on isolated time scales. Most of the models studied in economics are continuous or discrete. Discrete models are more preferable by economists since they give more meaningful and accurate results. Discrete models only contain uniform time domains. Time scale calculus enables us to study on m-periodic time domains as well as non periodic time domains. In the first chapter, we give basics of time scales calculus and stochastic calculus. The second chapter is the brief introduction to rational expectations and the CTRE model. Moreover, many other solution techniques are examined in this chapter. After we introduce the necessary background, in the third chapter we construct the CTRE Model on isolated time scales. Then we give the general solution of this model in terms of martingales. We continue our work with defining the linear system and higher order CTRE on isolated time scales. We use Putzer Algorithm to solve the system of the CTRE Model. Then, we examine the existence and uniqueness of the solution of the CTRE model. In the fourth chapter, we apply our solution algorithm developed in the previous chapter to models in Finance and stochastic growth models in Economics.

Almost every theory of mathematics has its discrete counterpart that makes it conceptually easier to understand and practically easier to use in the modeling process of real world problems. For instance, one can take the "difference" of any function, from 1st order up to the n-th order with discrete calculus. However, it is also possible to extend this theory by means of discrete fractional calculus and make n- any real number such that the ½-th order difference is well defined. This thesis is comprised of five chapters that demonstrate some basic definitions and properties of discrete fractional calculus while developing the simplest discrete fractional variational theory. Some applications of the theory to tumor growth are also studied. The first chapter is a brief introduction to discrete fractional calculus that presents some important mathematical functions widely used in the theory. The second chapter shows the main fractional difference and sum operators as well as their important properties. In the third chapter, a new proof for Leibniz formula is given and summation by parts for discrete fractional calculus is stated and proved. The simplest variational problem in discrete calculus and the related Euler-Lagrange equation are developed in the fourth chapter. In the fifth chapter, the fractional Gompertz difference equation is introduced. First, the existence and uniqueness of the solution is shown and then the equation is solved by the method of successive approximation. Finally, applications of the theory to tumor and bacterial growth are presented.

This thesis studies a problem that has been proposed as a novel way to disrupt communication networks: the load maximization problem. The load on a member of a network represents the amount of communication that the member is forced to be involved in. By maximizing the load on an important member of the network, we hope to increase that member's visibility and susceptibility to capture. In this thesis we characterize load as a combinatorial property of graphs and expose possible connections between load and spectral graph theory. We specifically describe the load and how it changes in several canonical classes of graphs and determine the range of values that the load can take on. We also consider a connection between load and liquid paint flow and use this connection to build a heuristic solver for the load maximization problem. We conclude with a detailed discussion of open questions for future work.

The secondary structures of ribonucleic acid (RNA) have been successfully modeled with graph-theoretic structures. Often, simple graphs are used to represent secondary RNA structures; however, in this research, a multigraph representation of RNA is used, in which vertices represent stems and edges represent the internal motifs. Any type of RNA secondary structure may be represented by a graph in this manner. We define novel graphical invariants to quantify the multigraphs and obtain characteristic descriptors of the secondary structures. These descriptors are used to train an artificial neural network (ANN) to recognize the characteristics of secondary RNA structure. Using the ANN, we classify the multigraphs as either RNA-like or not RNA-like. This classification method produced results similar to other classification methods. Given the expanding library of secondary RNA motifs, this method may provide a tool to help identify new structures and to guide the rational design of RNA molecules.

Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total domination number three and all total domination dot-stable graphs.

A Steiner triple system of order v, denoted STS(v), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic STS(v) when one of the cycles is of length one. In this case, the STS(v) will contain a subsystem which admits an automorphism consisting of a fixed point and a single cycle. The subsystem is said to be 1-rotational.

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 used for machine learning tasks such as node classification, graph classification, and link prediction. We discuss some challenges and provide future directions.

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 capacity of the Assembly Calculus, a derivative of Valiant's Neuroidal model. In this paper, we provide rigorous definitions for capacity and interference and present theoretical formulations for the memory capacity within a finite set, where subsets represent memories. We propose that these results can be adapted to suit both the Neuroidal model and Assembly calculus. Furthermore, we substantiate our claims by providing simulations that validate the theoretical findings. Our study aims to contribute essential insights into the understanding of memory capacity in complex cognitive models, offering potential ideas for applications and extensions to contemporary models of cognition.