Matching Items (4)
Filtering by
Description
This paper focuses on the Szemerédi regularity lemma, a result in the field of extremal graph theory. The lemma says that every graph can be partitioned into bounded equal parts such that most edges of the graph span these partitions, and these edges are distributed in a fairly uniform way. Definitions and notation will be established, leading to explorations of three proofs of the regularity lemma. These are a version of the original proof, a Pythagoras proof utilizing elemental geometry, and a proof utilizing concepts of spectral graph theory. This paper is intended to supplement the proofs with background information about the concepts utilized. Furthermore, it is the hope that this paper will serve as another resource for students and others to begin study of the regularity lemma.
ContributorsByrne, Michael John (Author) / Czygrinow, Andrzej (Thesis director) / Kierstead, Hal (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Department of Chemistry and Biochemistry (Contributor)
Created2015-05
Description
Analytic research on basketball games is growing quickly, specifically in the National Basketball Association. This paper explored the development of this analytic research and discovered that there has been a focus on individual player metrics and a dearth of quantitative team characterizations and evaluations. Consequently, this paper continued the exploratory research of Fewell and Armbruster's "Basketball teams as strategic networks" (2012), which modeled basketball teams as networks and used metrics to characterize team strategy in the NBA's 2010 playoffs. Individual players and outcomes were nodes and passes and actions were the links. This paper used data that was recorded from playoff games of the two 2012 NBA finalists: the Miami Heat and the Oklahoma City Thunder. The same metrics that Fewell and Armbruster used were explained, then calculated using this data. The offensive networks of these two teams during the playoffs were analyzed and interpreted by using other data and qualitative characterization of the teams' strategies; the paper found that the calculated metrics largely matched with our qualitative characterizations of the teams. The validity of the metrics in this paper and Fewell and Armbruster's paper was then discussed, and modeling basketball teams as multiple-order Markov chains rather than as networks was explored.
ContributorsMohanraj, Hariharan (Co-author) / Choi, David (Co-author) / Armbruster, Dieter (Thesis director) / Fewell, Jennifer (Committee member) / Brooks, Daniel (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor)
Created2013-05
Description
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.
ContributorsOtstot, Kyle (Author) / De Luca, Gennaro (Thesis director) / Chen, Yinong (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Computer Science and Engineering Program (Contributor)
Created2022-05
Description
In the ordering game on a graph G, Alice and Bob take turns placing the vertices of G into a linear ordering. The score of the game is the maximum number of neighbors that any vertex has before it in the ordering. Alice's goal in the ordering game is to minimize the score, while Bob's goal is to maximize it. The game coloring number is the least score that Alice can always guarantee in the ordering game, no matter how Bob plays. This paper examines what happens to the game coloring number if Alice or Bob skip turns on the ordering game. Preliminary definitions and examples are provided to give context to the ordering game. These include a polynomial time algorithm to compute the coloring number, a non-competitive version of the game coloring number. The notion of the preordered game is introduced as the primary tool of the paper, along with its naturally defined preordered game coloring number. To emphasize the complex relationship between the coloring number and the preordered game coloring number, a non-polynomial time strategy is given to Alice and Bob that yields the preordered game coloring number on any graph. Additionally, the preordered game coloring number is shown to be monotonic, one of the most useful properties for turn-skipping. Techniques developed throughout the paper are then used to determine that Alice cannot reduce the score and Bob cannot improve the score by skipping any number of their respective turns. This paper can hopefully be used as a stepping stone towards bounding the score on graphs when vertices are removed, as well as in deciphering further properties of the asymmetric marking game.
ContributorsGuglielmo, Jason A (Author) / Kierstead, Henry (Thesis director) / Czygrinow, Andrzej (Committee member) / School of Molecular Sciences (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2019-05