Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Algebra (13)
- Geometry and Topology (8)
- Computer Sciences (5)
- Applied Mathematics (4)
- Other Mathematics (4)
-
- Theory and Algorithms (4)
- Algebraic Geometry (3)
- Number Theory (3)
- Set Theory (3)
- Data Science (2)
- Harmonic Analysis and Representation (2)
- Other Applied Mathematics (2)
- Statistics and Probability (2)
- Analysis (1)
- Applied Statistics (1)
- Artificial Intelligence and Robotics (1)
- Dynamic Systems (1)
- Engineering (1)
- Geropsychology (1)
- Graphics and Human Computer Interfaces (1)
- Logic and Foundations (1)
- Non-linear Dynamics (1)
- Numerical Analysis and Computation (1)
- Numerical Analysis and Scientific Computing (1)
- Operational Research (1)
- Operations Research, Systems Engineering and Industrial Engineering (1)
- Ordinary Differential Equations and Applied Dynamics (1)
- Institution
-
- Claremont Colleges (8)
- University of Kentucky (6)
- Virginia Commonwealth University (4)
- City University of New York (CUNY) (3)
- Clemson University (3)
-
- Bard College (2)
- California Polytechnic State University, San Luis Obispo (2)
- California State University, San Bernardino (2)
- East Tennessee State University (2)
- University of Massachusetts Amherst (2)
- West Virginia University (2)
- Western Michigan University (2)
- Western University (2)
- Dartmouth College (1)
- Eastern Washington University (1)
- Louisiana State University (1)
- Mississippi State University (1)
- Murray State University (1)
- New Jersey Institute of Technology (1)
- Rollins College (1)
- University of Louisville (1)
- University of North Florida (1)
- University of South Carolina (1)
- Wilfrid Laurier University (1)
- William & Mary (1)
- Keyword
-
- Graph theory (10)
- Combinatorics (5)
- Graph (3)
- Algebraic combinatorics (2)
- Domination (2)
-
- Graph Theory (2)
- Matroid (2)
- $(s (1)
- 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)
- Ad allocation (1)
- Automorphism (1)
- Balance (1)
- Bijection (1)
- Binary Linear Codes Classification SageMath (1)
- Bipartite graphs (1)
- Bipartite graphs. (1)
- Publication
-
- HMC Senior Theses (6)
- Theses and Dissertations--Mathematics (6)
- Theses and Dissertations (5)
- Dissertations, Theses, and Capstone Projects (3)
- Electronic Theses and Dissertations (3)
-
- All Theses (2)
- Dissertations (2)
- Doctoral Dissertations (2)
- Electronic Theses, Projects, and Dissertations (2)
- Electronic Thesis and Dissertation Repository (2)
- Graduate Theses, Dissertations, and Problem Reports (2)
- Master's Theses (2)
- Senior Projects Spring 2023 (2)
- All Dissertations (1)
- CMC Senior Theses (1)
- Dartmouth College Ph.D Dissertations (1)
- EWU Masters Thesis Collection (1)
- Honors College Theses (1)
- Honors Program Theses (1)
- LSU Doctoral Dissertations (1)
- Scripps Senior Theses (1)
- Senior Theses (1)
- Theses (1)
- Theses and Dissertations (Comprehensive) (1)
- UNF Graduate Theses and Dissertations (1)
- Undergraduate Honors Theses (1)
Articles 31 - 52 of 52
Full-Text Articles in Discrete Mathematics and Combinatorics
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 …
The Multiset Partition Algebra: Diagram-Like Bases And Representations, Alexander N. Wilson
The Multiset Partition Algebra: Diagram-Like Bases And Representations, Alexander N. Wilson
Dartmouth College Ph.D Dissertations
There is a classical connection between the representation theory of the symmetric group and the general linear group called Schur--Weyl Duality. Variations on this principle yield analogous connections between the symmetric group and other objects such as the partition algebra and more recently the multiset partition algebra. The partition algebra has a well-known basis indexed by graph-theoretic diagrams which allows the multiplication in the algebra to be understood visually as combinations of these diagrams. My thesis begins with a construction of an analogous basis for the multiset partition algebra. It continues with applications of this basis to constructing the irreducible …
On Eulerian Subgraphs And Hamiltonian Line Graphs, Yikang Xie
On Eulerian Subgraphs And Hamiltonian Line Graphs, Yikang Xie
Graduate Theses, Dissertations, and Problem Reports
A graph {\color{black}$G$} is Hamilton-connected if for any pair of distinct vertices {\color{black}$u, v \in V(G)$}, {\color{black}$G$} has a spanning $(u,v)$-path; {\color{black}$G$} is 1-hamiltonian if for any vertex subset $S \subseteq {\color{black}V(G)}$ with $|S| \le 1$, $G - S$ has a spanning cycle. Let $\delta(G)$, $\alpha'(G)$ and $L(G)$ denote the minimum degree, the matching number and the line graph of a graph $G$, respectively. The following result is obtained. {\color{black} Let $G$ be a simple graph} with $|E(G)| \ge 3$. If $\delta(G) \geq \alpha'(G)$, then each of the following holds. \\ (i) $L(G)$ is Hamilton-connected if and only if $\kappa(L(G))\ge …
Classification Of Doubly-Even Linear Binary Codes: An Analysis Of The Sagemath Implementation, Tom Gadron
Classification Of Doubly-Even Linear Binary Codes: An Analysis Of The Sagemath Implementation, Tom Gadron
Senior Projects Spring 2023
Classification of doubly-even linear binary codes involves finding and enumerating permutation equivalence classes of subspaces of the vector space F2_n . This project provides an analysis and explanation of the SageMath functions written by Robert Miller that implement the algorithm used for generating these codes.
Parking Garage Functions, Felicia Elizabeth Flores
Parking Garage Functions, Felicia Elizabeth Flores
Senior Projects Spring 2023
Senior Project submitted to The Division of Science, Mathematics and Computing of Bard College.
This project is about a generalization of parking functions called parking garage functions. Parking functions have been well studied, but the concept of parking garage functions is new and introduced in the project. Parking garage functions are sequences that represent the parking garage level preferences of cars which lead to all cars parking on a level after a systematic placement. We found a recursive formula for the number of sequences that are a parking garage function. We also found a closed formula for a subset of …
Modeling Repairable System Failure Data Using Nhpp Realiability Growth Mode., Eunice Ofori-Addo
Modeling Repairable System Failure Data Using Nhpp Realiability Growth Mode., Eunice Ofori-Addo
EWU Masters Thesis Collection
Stochastic point processes have been widely used to describe the behaviour of repairable systems. The Crow nonhomogeneous Poisson process (NHPP) often known as the Power Law model is regarded as one of the best models for repairable systems. The goodness-of-fit test rejects the intensity function of the power law model, and so the log-linear model was fitted and tested for goodness-of-fit. The Weibull Time to Failure recurrent neural network (WTTE-RNN) framework, a probabilistic deep learning model for failure data, is also explored. However, we find that the WTTE-RNN framework is only appropriate failure data with independent and identically distributed interarrival …
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.
Surjectivity Of The Wahl Map On Cubic Graphs, Angela C. Hanson
Surjectivity Of The Wahl Map On Cubic Graphs, Angela C. Hanson
Theses and Dissertations--Mathematics
Much of algebraic geometry is the study of curves. One tool we use to study curves is whether they can be embedded in a K3 surface or not. If the Wahl map is surjective on a curve, that curve cannot be embedded in a K3 surface. Therefore, studying if the Wahl map is surjective for a particular curve gives us more insight into the properties of that curve. We simplify this problem by converting graph curves to dual graphs. Then the information for graphs can be used to study the underlying curves. We will discuss conditions for the Wahl map …
Methods Of Computing Graph Gonalities, Noah Speeter
Methods Of Computing Graph Gonalities, Noah Speeter
Theses and Dissertations--Mathematics
Chip firing is a category of games played on graphs. The gonality of a graph tells us how many chips are needed to win one variation of the chip firing game. The focus of this dissertation is to provide a variety of new strategies to compute the gonality of various graph families. One family of graphs which this dissertation is particularly interested in is rook graphs. Rook graphs are the Cartesian product of two or more complete graphs and we prove that the gonality of two dimensional rook graphs is the expected value of (n − 1)m where n is …
Geometric And Combinatorial Properties Of Lattice Polytopes Defined From Graphs, Kaitlin Bruegge
Geometric And Combinatorial Properties Of Lattice Polytopes Defined From Graphs, Kaitlin Bruegge
Theses and Dissertations--Mathematics
Polytopes are geometric objects that generalize polygons in the plane and polyhedra in 3-dimensional space. Of particular interest in geometric combinatorics are families of lattice polytopes defined from combinatorial objects, such as graphs. In particular, this dissertation studies symmetric edge polytopes (SEPs), defined from simple undirected graphs. In 2019, Higashitani, Jochemko, and Michalek gave a combinatorial description of the hyperplanes that support facets of a symmetric edge polytope in terms of certain labelings of the underlying graph.
Using this framework, we explore the number of facets that can be attained by the symmetric edge polytopes for graphs with certain structure. …
Q-Polymatroids And Their Application To Rank-Metric Codes., Benjamin Jany
Q-Polymatroids And Their Application To Rank-Metric Codes., Benjamin Jany
Theses and Dissertations--Mathematics
Matroid theory was first introduced to generalize the notion of linear independence. Since its introduction, the theory has found many applications in various areas of mathematics including coding theory. In recent years, q-matroids, the q-analogue of matroids, were reintroduced and found to be closely related to the theory of linear vector rank metric codes. This relation was then generalized to q-polymatroids and linear matrix rank metric codes. This dissertation aims at developing the theory of q-(poly)matroid and its relation to the theory of rank metric codes. In a first part, we recall and establish preliminary results for both q-polymatroids and …
Geometry Of Pipe Dream Complexes, Benjamin Reese
Geometry Of Pipe Dream Complexes, Benjamin Reese
Theses and Dissertations--Mathematics
In this dissertation we study the geometry of pipe dream complexes with the goal of gaining a deeper understanding of Schubert polynomials. Given a pipe dream complex PD(w) for w a permutation in the symmetric group, we show its boundary is Whitney stratified by the set of all pipe dream complexes PD(v) where v > w in the strong Bruhat order. For permutations w in the symmetric group on n elements, we introduce the pipe dream complex poset P(n). The dual of this graded poset naturally corresponds to the poset of strata associated to the Whitney stratification of the boundary of …
The Lie Algebra Sl2(C) And Krawtchouk Polynomials, Nkosi Alexander
The Lie Algebra Sl2(C) And Krawtchouk Polynomials, Nkosi Alexander
UNF Graduate Theses and Dissertations
The Lie algebra L = sl2(C) consists of the 2 × 2 complex matrices that have trace zero, together with the Lie bracket [y, z] = yz − zy. In this thesis we study a relationship between L and Krawtchouk polynomials. We consider a type of element in L said to be normalized semisimple. Let a, a^∗ be normalized semisimple elements that generate L. We show that a, a^∗ satisfy a pair of relations, called the Askey-Wilson relations. For a positive integer N, we consider an (N + 1)-dimensional irreducible L-module V consisting of the homogeneous polynomials in two variables …
Lattice Minors And Eulerian Posets, William Gustafson
Lattice Minors And Eulerian Posets, William Gustafson
Theses and Dissertations--Mathematics
We study a partial ordering on pairings called the uncrossing poset, which first appeared in the literature in connection with a certain stratified space of planar electrical networks. We begin by examining some of the relationships between the uncrossing poset and Catalan combinatorics, and then proceed to study the structure of lower intervals. We characterize the lower intervals in the uncrossing poset that are isomorphic to the face lattice of a cube. Moving up in complexity certain lower intervals are isomorphic to the poset of simple vertex labeled minors of an associated graph.
Inspired by this structure, we define a …
Minimal Sets, Union-Closed Families, And Frankl's Conjecture, Christopher S. Flippen
Minimal Sets, Union-Closed Families, And Frankl's Conjecture, Christopher S. Flippen
Theses and Dissertations
The most common statement of Frankl's conjecture is that for every finite family of sets closed under the union operation, there is some element which belongs to at least half of the sets in the family. Despite its apparent simplicity, Frankl's conjecture has remained open and highly researched since its first mention in 1979. In this paper, we begin by examining the history and previous attempts at solving the conjecture. Using these previous ideas, we introduce the concepts of minimal sets and minimally-generated families, some ideas related to viewing union-closed families as posets, and some constructions of families involving poset-defined …
Selected Problems In Graph Coloring, Hudson Lafayette
Selected Problems In Graph Coloring, Hudson Lafayette
Theses and Dissertations
The Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4.
For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or nearly sharp upper bounds on the t-tone chromatic number of various classes of sparse graphs. In particular, we determine τ2(G) exactly when mad(G) < 12/5 and also determine τ2(G), up to a small additive constant, when G is outerplanar. Finally, we determine τt(Cn) exactly when t ∈ {3, 4, 5}.
Rainbow Turan Methods For Trees, Victoria Bednar
Rainbow Turan Methods For Trees, Victoria Bednar
Theses and Dissertations
The rainbow Turan number, a natural extension of the well-studied traditional
Turan number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstraete. The rainbow Tur ́an number of a graph F , ex*(n, F ), is the largest number of edges for an n vertex graph G that can be properly edge colored with no rainbow F subgraph. Chapter 1 of this dissertation gives relevant definitions and a brief history of extremal graph theory. Chapter 2 defines k-unique colorings and the related k-unique Turan number and provides preliminary results on this new variant. In Chapter 3, we explore the …
Investigations In The Semi-Strong Product Of Graphs And Bootstrap Percolation, Kevin J. Mccall
Investigations In The Semi-Strong Product Of Graphs And Bootstrap Percolation, Kevin J. Mccall
Theses and Dissertations
The semi-strong product of graphs G and H is a way of forming a new graph from the graphs G and H. The vertex set of the semi-strong product is the Cartesian product of the vertex sets of G and H, V(G) x V(H). The edges of the semi-strong product are determined as follows: (g1,h1)(g2,h2) is an edge of the product whenever g1g2 is an edge of G and h1h2 is an edge of H or g1 = g2 and h1h2 …
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 …
Finite Matroidal Spaces And Matrological Spaces, Ziyad M. Hamad
Finite Matroidal Spaces And Matrological Spaces, Ziyad M. Hamad
Graduate Theses, Dissertations, and Problem Reports
The purpose of this thesis is to present new different spaces as attempts to generalize the concept of topological vector spaces. A topological vector space, a well-known concept in mathematics, is a vector space over a field \mathbb{F} with a topology that makes the addition and scalar multiplication operations of the vector space continuous functions. The field \mathbb{F} is usually \mathbb{R} or \mathbb{C} with their standard topologies. Since every vector space is a finitary matroid, we define two spaces called finite matroidal spaces and matrological spaces by replacing the linear structure of the topological vector space with a finitary matroidal …
Opposite Trees, Theo Goossens
Opposite Trees, Theo Goossens
Theses and Dissertations (Comprehensive)
A spanning tree of a graph G is a connected acyclic subgraph of G that includes all of the vertices in G. The degree of a vertex is the number of edges incident to that vertex. Given a spanning tree T of a graph G, an opposite tree of T is a spanning tree of G where the degree of each of its vertices is different from its degree in T. For complete, complete bipartite, and complete multipartite graphs, we give the conditions spanning trees of these graphs must satisfy in order to have an opposite tree.