Discrete Mathematics and Combinatorics Commons^™

Equitable Decompositions: A Gateway To Spectral Theory Through Graph Automorphisms, Daniel Ford

Master's Theses

Graphs with symmetry appear throughout mathematics and its applications, from the structure of molecules and network design to combinatorial game theory. A central question in spectral graph theory is how to compute or characterise the eigenvalues of the matrices associated with such graphs. Classical decomposition methods, such as diagonalisation or Jordan normal form, accomplish this but only once some spectral information is already known. A different approach, introduced by Barrett et al. (2015), uses the automorphisms of a graph to block-diagonalise its adjacency matrix without any prior spectral information. Because one of the resulting summands is always the quotient matrix …

On The Number Of Ways To Express A Set As A Union Of Individually Interesting Sets, Alison Watson

Master's Theses

In a dataset that contains what ought rightly to be several distinct datasets placed in juxtaposition with each other, grouping datapoints based on observed similarities can be done in many ways. Topological Data Analysis (TDA) is a field of math that seeks to impose geometric structure onto datasets, thereby translating problems in statistics to problems in geometry or topology. A common truism in this field is “Data has shape and shape has meaning.” In this thesis, we use combinatorial and categorical arguments to demonstrate some shortcomings of a TDA approach on a class of inverse problems inspired by marine wildlife …

Demystifying Hardware Formal Verification For Undergraduate Education: A Risc-V Processor Case Study With Coursework Implementation, Riley A. Peters

Master's Theses

Hardware verification engineers apply formal methods to prove that a digital device always behaves according to its specification. This differs from traditional functional verification, in which engineers establish correctness by repeatedly sending test inputs to the device and comparing the outputs against a reference model. With the growing complexity of integrated circuits, the demand for digital verification engineers with formal methods experience has continued to increase. However, California Polytechnic State University: San Luis Obispo's current curriculum lacks dedicated material to prepare students for these roles.

This thesis seeks to address the lack of formal methods material through two efforts. First, …

The Degrees Of The Irreducible Representations Of The Symmetric Group With Respect To Primes, Vanessa F. Beeler

Master's Theses

In this thesis, we explore the relationship between the degrees of irreducible matrix representations of the symmetric group and prime numbers. We start by building up the required background necessary to construct our results. We dive into topics of discrete mathematics including matrix representations, characters of representations, integer partitions, conjugacy classes, class functions, and tableaux. Some other key ingredients in our work include using character tables to classify the irreducible rep- resentations of the symmetric group and the hook-length formula to easily compute the degrees of these representations. Once we have laid the groundwork for our in- vestigation, we begin …

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 …

Representations From Group Actions On Words And Matrices, Joel T. Anderson

Master's Theses

We provide a combinatorial interpretation of the frequency of any irreducible representation of Sn in representations of Sn arising from group actions on words. Recognizing that representations arising from group actions naturally split across orbits yields combinatorial interpretations of the irreducible decompositions of representations from similar group actions. The generalization from group actions on words to group actions on matrices gives rise to representations that prove to be much less transparent. We share the progress made thus far on the open problem of determining the irreducible decomposition of certain representations of Sm × Sn arising from group actions on matrices.

Irreducible Representations From Group Actions On Trees, Charlie Liou

Master's Theses

We study the representations of the symmetric group $S_n$ found by acting on

labeled graphs and trees with $n$ vertices. Our main results provide

combinatorial interpretations that give the number of times the irreducible

representations associated with the integer partitions $(n)$ and $(1^n)$ appear

in the representations. We describe a new sign

reversing involution with fixed points that provide a combinatorial

interpretation for the number of times the irreducible associated with the

integer partition $(n-1, 1)$ appears in the representations.

Computing Homology Of Hypergraphs, Jackson Earl

STAR Program Research Presentations

In the modern age of data science, the necessity for efficient and insightful analytical tools that enable us to interpret large data structures inherently presents itself. With the increasing utility of metrics offered by the mathematics of hypergraph theory and algebraic topology, we are able to explore multi-way relational datasets and actively develop such tools. Throughout this research endeavor, one of the primary goals has been to contribute to the development of computational algorithms pertaining to the homology of hypergraphs. More specifically, coding in python to compute the homology groups of a given hypergraph, as well as their Betti numbers …

Optimal Layout For A Component Grid, Michael W. Ebert

Computer Science and Software Engineering

Several puzzle games include a specific type of optimization problem: given components that produce and consume different resources and a grid of squares, find the optimal way to place the components to maximize output. I developed a method to evaluate potential solutions quickly and automated the solving of the problem using a genetic algorithm.

A High Quality, Eulerian 3d Fluid Solver In C++, Lejon Anthony Mcgowan

Computer Science and Software Engineering

Fluids are a part of everyday life, yet are one of the hardest elements to properly render in computer graphics. Water is the most obvious entity when thinking of what a fluid simulation can achieve (and it is indeed the focus of this project), but many other aspects of nature, like fog, clouds, and particle effects. Real-time graphics like video games employ many heuristics to approximate these effects, but large-scale renderers aim to simulate these effects as closely as possible.

In this project, I wish to achieve effects of the latter nature. Using the Eulerian technique of discrete grids, I …