Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Algebraic combinatorics (2)
- Combinatorics (2)
- 00A69 - general applied mathematics (1)
- 05 (1)
- 05-02 (1)
-
- 05A05 (1)
- 05C81 - random walks on graphs (1)
- 05Cxx Graph theory (1)
- 05E (1)
- 05E10 (1)
- 11A67 (1)
- 11B39 (1)
- 20B30 (1)
- 52-XX Convex and discrete geometry (1)
- 57-XX Manifolds and cell complexes (1)
- 68R05 (1)
- 90C31 - sensitivity and stability (1)
- Bipartite graphs. (1)
- Combinatorial aspects of representation theory (1)
- Combinatorics in computer science (1)
- Fibonacci and Lucas numbers and polynomials and generalizations (1)
- Gerrymandering (1)
- Graph theory (1)
- Latin squares (1)
- Minimum embeddings (1)
- Other number representations (1)
- Partition algebra (1)
- Permutation statistics (1)
- Permutations & Words & Matrices (1)
- Random walk (1)
Articles 1 - 8 of 8
Full-Text Articles in Discrete Mathematics and Combinatorics
Generalized Far-Difference Representations, Prakod Ngamlamai
Generalized Far-Difference Representations, Prakod Ngamlamai
HMC Senior Theses
Integers are often represented as a base-$b$ representation by the sum $\sum c_ib^i$. Lekkerkerker and Zeckendorf later provided the rules for representing integers as the sum of Fibonacci numbers. Hannah Alpert then introduced the far-difference representation by providing rules for writing an integer with both positive and negative multiples of Fibonacci numbers. Our work aims to generalize her work to a broader family of linear recurrences. To do so, we describe desired properties of the representations, such as lexicographic ordering, and provide a family of algorithms for each linear recurrence that generate unique representations for any integer. We then prove …
The Sensitivity Of A Laplacian Family Of Ranking Methods, Claire S. Chang
The Sensitivity Of A Laplacian Family Of Ranking Methods, Claire S. Chang
HMC Senior Theses
Ranking from pairwise comparisons is a particularly rich subset of ranking problems. In this work, we focus on a family of ranking methods for pairwise comparisons which encompasses the well-known Massey, Colley, and Markov methods. We will accomplish two objectives to deepen our understanding of this family. First, we will consider its network diffusion interpretation. Second, we will analyze its sensitivity by studying the "maximal upset" where the direction of an arc between the highest and lowest ranked alternatives is flipped. Through these analyses, we will build intuition to answer the question "What are the characteristics of robust ranking methods?" …
Discrete Analogues Of The Poincaré-Hopf Theorem, Kate Perkins
Discrete Analogues Of The Poincaré-Hopf Theorem, Kate Perkins
HMC Senior Theses
My thesis unpacks the relationship between two discrete formulations of the Poincaré-Hopf index theorem. Chapter 1 introduces necessary definitions. Chapter 2 describes the discrete analogs and their differences. Chapter 3 contains a proof that one analog implies the other and chapter 4 contains a proof that the Poincaré-Hopf theorem implies the discrete analogs. Finally, chapter 5 presents still open questions and further research directions.
An Inquiry Into Lorentzian Polynomials, Tomás Aguilar-Fraga
An Inquiry Into Lorentzian Polynomials, Tomás Aguilar-Fraga
HMC Senior Theses
In combinatorics, it is often desirable to show that a sequence is unimodal. One method of establishing this is by proving the stronger yet easier-to-prove condition of being log-concave, or even ultra-log-concave. In 2019, Petter Brändén and June Huh introduced the concept of Lorentzian polynomials, an exciting new tool which can help show that ultra-log-concavity holds in specific cases. My thesis investigates these Lorentzian polynomials, asking in which situations they are broadly useful. It covers topics such as matroid theory, discrete convexity, and Mason’s conjecture, a long-standing open problem in matroid theory. In addition, we discuss interesting applications to known …
Long Increasing Subsequences, Hannah Friedman
Long Increasing Subsequences, Hannah Friedman
HMC Senior Theses
In my thesis, I investigate long increasing subsequences of permutations from two angles. Motivated by studying interpretations of the longest increasing subsequence statistic across different representations of permutations, we investigate the relationship between reduced words for permutations and their RSK tableaux in Chapter 3. In Chapter 4, we use permutations with long increasing subsequences to construct a basis for the space of 𝑘-local functions.
Permutations, Representations, And Partition Algebras: A Random Walk Through Algebraic Statistics, Ian Shors
Permutations, Representations, And Partition Algebras: A Random Walk Through Algebraic Statistics, Ian Shors
HMC Senior Theses
My thesis examines a class of functions on the symmetric group called permutation statistics using tools from representation theory. In 2014, Axel Hultman gave formulas for computing expected values of permutation statistics sampled via random walks. I present analogous formulas for computing variances of these statistics involving Kronecker coefficients – certain numbers that arise in the representation theory of the symmetric group. I also explore deep connections between the study of moments of permutation statistics and the representation theory of the partition algebras, a family of algebras introduced by Paul Martin in 1991. By harnessing these partition algebras, I derive …
Partially Filled Latin Squares, Mariam Abu-Adas
Partially Filled Latin Squares, Mariam Abu-Adas
Scripps Senior Theses
In this thesis, we analyze various types of Latin squares, their solvability and embeddings. We examine the results by M. Hall, P. Hall, Ryser and Evans first, and apply our understandings to develop an algorithm that the determines the minimum possible embedding of an unsolvable Latin square. We also study Latin squares with missing diagonals in detail.
Counting Spanning Trees On Triangular Lattices, Angie Wang
Counting Spanning Trees On Triangular Lattices, Angie Wang
CMC Senior Theses
This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …