Computable properties of quantum states are given a dual gravitational interpretation via the AdS/CFT correspondence. For holographic states, boundary entanglement entropy is dual to the area of bulk geodesics, known as Ryu-Takayanagi surfaces. Furthermore, the viability of states to admit a holographic dual at all is constrained by their entanglement structure. Entanglement therefore defines a coarse classification of states in the Hilbert space. Similarly, how a state transforms under a group of operators also provides a classification on the Hilbert space. Certain states, e.g. stabilizer states, are invariant under large sets of operations, and consequently can be simulated on a classical computer. Cayley graphs offer a useful representation for a group of operators, where vertices represent group elements and edges represent group generators. In this representation, the orbit of a state under action of the group can also be represented as a ``reachability graph'', defined as a quotient of the group Cayley graph. Reachability graphs can be dressed to encode entanglement information, making them a useful tool for studying entanglement dynamics under quantum operations. Further quotienting a reachability graph by group elements that fix a chosen state property, e.g. entanglement entropy, builds a ``contracted graph''. Contracted graphs provide explicit bounds on state parameter evolution under quantum circuits. In this work, an upper bound on entropy vector evolution under Clifford group action is presented. Another important property of quantum systems is magic, which quantifies the difficulty of classically simulating a quantum state. Magic and entanglement are intimately related, but the two are not equivalent measures of complexity. Nonetheless, entanglement and magic play complementary roles when describing emergent gravitational phenomena in AdS/CFT. This manuscript describes the interplay between entanglement and magic, and offers a holographic interpretation for magic as cosmic brane back-reaction.

We studied binomial edge ideals, which are at the intersection of graph theory and abstract algebra. Our focus was the multidegrees of these ideals, which contain valuable geometric information. We proved algebraic results that allowed us to write a closed formula for the multidegree of the binomial edge ideal of a graph based on combinatorial properties of the graph. Then we discovered methods to make the process more efficient. We concluded our research by using our results to find the multidegrees of the binomial edge ideals of many families of graphs.

With the ability to observe the atmospheres of terrestrial exoplanets via transit spectroscopy on the near-term horizon, the possibility of atmospheric biosignatures has received considerable attention in astrobiology. While traditionally exoplanet scientists looking for life focused on biologically relevant trace gases such as O2 and CH4, this approach has raised the spectre of false positives. Therefore, to address these shortcomings, a new set of methods is required to provide higher confidence in life detection. One possible approach is measuring the topology of atmospheric chemical reaction networks (CRNs). To investigate and assess this approach, the ability of network-theoretic metrics to distinguish the distance from thermochemical equilibrium in the atmosphere of hot jupiters was tested. After modeling the atmospheres of hot jupiters over a range of initial conditions using the VULCAN modeling package, atmospheric CRNs were constructed from the converged models and their topology measured using the Python package NetworkX. I found that network metrics were able to predict the distance from thermochemical equilibrium better than atmospheric species abundances alone. Building on this success, I modeled 30,000 terrestrial worlds. These models divided into two categories: Anoxic Archean Earth-like planets that varied in terms of CH4 surface flux (modeled as either biotic or abiotic in origin), and modern Earth-like planets with and without a surface flux of CCl2F2 (to represent the presence of industrial civilizations). I constructed atmospheric CRNs from the converged models, and analyzed their topology. I found that network metrics could distinguish between atmospheres with and without the presence of life or technology. In particular, mean degree and average shortest path length consistently performed better at distinguishing between abiotic and biotic Archean-like atmospheres than CH4 abundance.

Little is known about how cognitive and brain aging patterns differ in older adults with autism spectrum disorder (ASD). However, recent evidence suggests that individuals with ASD may be at greater risk of pathological aging conditions than their neurotypical (NT) counterparts. A growing body of research indicates that older adults with ASD may experience accelerated cognitive decline and neurodegeneration as they age, although studies are limited by their cross-sectional design in a population with strong age-cohort effects. Studying aging in ASD and identifying biomarkers to predict atypical aging is important because the population of older individuals with ASD is growing. Understanding the unique challenges faced as autistic adults age is necessary to develop treatments to improve quality of life and preserve independence. In this study, a longitudinal design was used to characterize cognitive and brain aging trajectories in ASD as a function of autistic trait severity. Principal components analysis (PCA) was used to derive a cognitive metric that best explains performance variability on tasks measuring memory ability and executive function. The slope of the integrated persistent feature (SIP) was used to quantify functional connectivity; the SIP is a novel, threshold-free graph theory metric which summarizes the speed of information diffusion in the brain. Longitudinal mixed models were using to predict cognitive and brain aging trajectories (measured via the SIP) as a function of autistic trait severity, sex, and their interaction. The sensitivity of the SIP was also compared with traditional graph theory metrics. It was hypothesized that older adults with ASD would experience accelerated cognitive and brain aging and furthermore, age-related changes in brain network topology would predict age-related changes in cognitive performance. For both cognitive and brain aging, autistic traits and sex interacted to predict trajectories, such that older men with high autistic traits were most at risk for poorer outcomes. In men with autism, variability in SIP scores across time points trended toward predicting cognitive aging trajectories. Findings also suggested that autistic traits are more sensitive to differences in brain aging than diagnostic group and that the SIP is more sensitive to brain aging trajectories than other graph theory metrics. However, further research is required to determine how physiological biomarkers such as the SIP are associated with cognitive outcomes.

In this work, we explore the potential for realistic and accurate generation of hourly traffic volume with machine learning (ML), using the ground-truth data of Manhattan road segments collected by the New York State Department of Transportation (NYSDOT). Specifically, we address the following question– can we develop a ML algorithm that generalizes the existing NYSDOT data to all road segments in Manhattan?– by introducing a supervised learning task of multi-output regression, where ML algorithms use road segment attributes to predict hourly traffic volume. We consider four ML algorithms– K-Nearest Neighbors, Decision Tree, Random Forest, and Neural Network– and hyperparameter tune by evaluating the performances of each algorithm with 10-fold cross validation. Ultimately, we conclude that neural networks are the best-performing models and require the least amount of testing time. Lastly, we provide insight into the quantification of “trustworthiness” in a model, followed by brief discussions on interpreting model performance, suggesting potential project improvements, and identifying the biggest takeaways. Overall, we hope our work can serve as an effective baseline for realistic traffic volume generation, and open new directions in the processes of supervised dataset generation and ML algorithm design.

Ensuring reliable operation of large power systems subjected to multiple outages is a challenging task because of the combinatorial nature of the problem. Traditional methods of steady-state security assessment in power systems involve contingency analysis based on AC or DC power flows. However, power flow based contingency analysis is not fast enough to evaluate all contingencies for real-time operations. Therefore, real-time contingency analysis (RTCA) only evaluates a subset of the contingencies (called the contingency list), and hence might miss critical contingencies that lead to cascading failures.This dissertation proposes a new graph-theoretic approach, called the feasibility test (FT) algorithm, for analyzing whether a contingency will create a saturated or over-loaded cut-set in a meshed power network; a cut-set denotes a set of lines which if tripped separates the network into two disjoint islands. A novel feature of the proposed approach is that it lowers the solution time significantly making the approach viable for an exhaustive real-time evaluation of the system. Detecting saturated cut-sets in the power system is important because they represent the vulnerable bottlenecks in the network. The robustness of the FT algorithm is demonstrated on a 17,000+ bus model of the Western Interconnection (WI). Following the detection of post-contingency cut-set saturation, a two-component methodology is proposed to enhance the reliability of large power systems during a series of outages. The first component combines the proposed FT algorithm with RTCA to create an integrated corrective action (iCA), whose goal is to secure the power system against post-contingency cut-set saturation as well as critical branch overloads. The second component only employs the results of the FT to create a relaxed corrective action (rCA) that quickly secures the system against saturated cut-sets. The first component is more comprehensive than the second, but the latter is computationally more efficient. The effectiveness of the two components is evaluated based upon the number of cascade triggering contingencies alleviated, and the computation time. Analysis of different case-studies on the IEEE 118-bus and 2000-bus synthetic Texas systems indicate that the proposed two-component methodology enhances the scope and speed of power system security assessment during multiple outages.

The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of a graph

$G$ is the minimum number $k$ such that there exists a linear ordering

of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.

It is well known that the coloring number is an upper bound for the

chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is

a generalization of the coloring number, and it was first introduced

by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$

is the minimum integer $k$ such that for some linear ordering $L$

of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller

vertices $u$ (with respect to $L$) with a path of length at most

$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.

The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$

is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$

if and only if the distance between $x$ and $y$ in $G$ is $3$.

This dissertation improves the best known upper bound of the

chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$

of planar graphs $G$, which is $105$, to $95$. It also improves

the best known lower bound, which is $7$, to $9$.

A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number.

This dissertation focuses on creating a pluralistic approach to understanding and measuring interdisciplinarity at various scales to further the study of the evolution of knowledge and innovation. Interdisciplinarity is considered an important research component and is closely linked to higher rates of innovation. If the goal is to create more innovative research, we must understand how interdisciplinarity operates.

I begin by examining interdisciplinarity with a small scope, the research university. This study uses metadata to create co-authorship networks and examine how a change in university policies to increase interdisciplinarity can be successful. The New American University Initiative (NAUI) at Arizona State University (ASU) set forth the goal of making ASU a world hub for interdisciplinary research. This kind of interdisciplinarity is produced from a deliberate, engineered, reorganization of the individuals within the university and the knowledge they contain. By using a set of social network analysis measurements, I created an algorithm to measure the changes to the co-authorship networks that resulted from increased university support for interdisciplinary research.

The second case study increases the scope of interdisciplinarity from individual universities to a single scientific discourse, the Anthropocene. The idea of the Anthropocene began as an idea about the need for a new geological epoch and underwent unsupervised interdisciplinary expansion due to climate change integrating itself into the core of the discourse. In contrast to the NAUI which was specifically engineered to increase interdisciplinarity, the I use keyword co-occurrence networks to measure how the Anthropocene discourse increases its interdisciplinarity through unsupervised expansion after climate change becomes a core keyword within the network and behaves as an anchor point for new disciplines to connect and join the discourse.

The scope of interdisciplinarity increases again with the final case study about the field of evolutionary medicine. Evolutionary medicine is a case of engineered interdisciplinary integration between evolutionary biology and medicine. The primary goal of evolutionary medicine is to better understand "why we get sick" through the lens of evolutionary biology. This makes it an excellent candidate to understand large-scale interdisciplinarity. I show through multiple type of networks and metadata analyses that evolutionary medicine successfully integrates the concepts of evolutionary biology into medicine.

By increasing our knowledge of interdisciplinarity at various scales and how it behaves in different initial conditions, we are better able to understand the elusive nature of innovation. Interdisciplinary can mean different things depending on how its defined. I show that a pluralistic approach to defining and measuring interdisciplinarity is not only appropriate but necessary if our goal is to increase interdisciplinarity, the frequency of innovations, and our understanding of the evolution of knowledge.

Autism spectrum disorder (ASD) is a developmental neuropsychiatric condition with early childhood onset, thus most research has focused on characterizing brain function in young individuals. Little is understood about brain function differences in middle age and older adults with ASD, despite evidence of persistent and worsening cognitive symptoms. Functional Magnetic Resonance Imaging (MRI) in younger persons with ASD demonstrate that large-scale brain networks containing the prefrontal cortex are affected. A novel, threshold-selection-free graph theory metric is proposed as a more robust and sensitive method for tracking brain aging in ASD and is compared against five well-accepted graph theoretical analysis methods in older men with ASD and matched neurotypical (NT) participants. Participants were 27 men with ASD (52 +/- 8.4 years) and 21 NT men (49.7 +/- 6.5 years). Resting-state functional MRI (rs-fMRI) scans were collected for six minutes (repetition time=3s) with eyes closed. Data was preprocessed in SPM12, and Data Processing Assistant for Resting-State fMRI (DPARSF) was used to extract 116 regions-of-interest defined by the automated anatomical labeling (AAL) atlas. AAL regions were separated into six large-scale brain networks. This proposed metric is the slope of a monotonically decreasing convergence function (Integrated Persistent Feature, IPF; Slope of the IPF, SIP). Results were analyzed in SPSS using ANCOVA, with IQ as a covariate. A reduced SIP was in older men with ASD, compared to NT men, in the Default Mode Network [F(1,47)=6.48; p=0.02; 2=0.13] and Executive Network [F(1,47)=4.40; p=0.04; 2=0.09], a trend in the Fronto-Parietal Network [F(1,47)=3.36; p=0.07; 2=0.07]. There were no differences in the non-prefrontal networks (Sensory motor network, auditory network, and medial visual network). The only other graph theory metric to reach significance was network diameter in the Default Mode Network [F(1,47)=4.31; p=0.04; 2=0.09]; however, the effect size for the SIP was stronger. Modularity, Betti number, characteristic path length, and eigenvalue centrality were all non-significant. These results provide empirical evidence of decreased functional network integration in pre-frontal networks of older adults with ASD and propose a useful biomarker for tracking prognosis of aging adults with ASD to enable more informed treatment, support, and care methods for this growing population.

Extremal graph theory results often provide minimum degree

conditions which guarantee a copy of one graph exists within

another. A perfect $F$-tiling of a graph $G$ is a collection

$\mathcal{F}$ of subgraphs of $G$ such that every element of

$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$

is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote

the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph

obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$

on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is

uniquely assigned to $e$. This dissertation proves for even

$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$

on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree

$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +

1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect

$C^{3}_{t}$-tiling. The result is tight, generalizing previous

results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,

let the minimum color degree $\delta^c(G)$ be the minimum number of

distinctly colored edges incident to a vertex. Call $G$ rainbow if

every edge has a unique color. For $\ell \geq 5$, this dissertation

proves that any sufficiently large edge colored graph $G$ on $n$

vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow

cycle on $\ell$ vertices. The result is tight for odd $\ell$ and

extends previous results for $\ell = 3$. In addition, for even

$\ell \geq 4$, this dissertation proves that any sufficiently large

edge colored graph $G$ on $n$ vertices with

$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where

$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$

vertices. The result is tight when $6 \nmid \ell$. As a related

result, this dissertation proves for all $\ell \geq 4$, that any

sufficiently large oriented graph $D$ on $n$ vertices with

$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on

$\ell$ vertices. This partially generalizes a result by Kelly,

K\uhn" and Osthus that uses minimum semidegree rather than minimum

out degree."