Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Keyword
-
- Hamiltonian Cycles (2)
- Burnside's Lemma (1)
- Cauchy–Davenport Theorem (1)
- Centroid (1)
- Chess (1)
-
- Complete sequences (1)
- Complexity (1)
- Conjugacy classes (1)
- Delannoy Numbers (1)
- Derivations (1)
- Enumerative Combinatorics (1)
- Erdős–Rényi Random Graphs (1)
- Fibonacci sequence (1)
- Finite field (1)
- Finite order (1)
- Fundamental basis (1)
- Generating function (1)
- Generating functions (1)
- Graph Theory (1)
- Graph theory (1)
- Group action (1)
- Hypergraphs (1)
- Knight's Tour (1)
- Knight’s Tours (1)
- Lattice Paths (1)
- Lie groups (1)
- Linear invariants (1)
- Matrix (1)
- Morse-Hedlund (1)
- Multiplicative order (1)
Articles 1 - 13 of 13
Full-Text Articles in Discrete Mathematics and Combinatorics
Sumset Lower Bounds In Abelian Groups, Van T. Huynh
Sumset Lower Bounds In Abelian Groups, Van T. Huynh
Honors Theses
This thesis investigates sumset lower bounds across discrete and continuous settings. We begin with general inequalities in torsion-free abelian groups and then specialize to the integers modulo prime p, where we present the Cauchy–Davenport Theorem, which establishes the bound ∣A+B∣≥min(p,∣A∣+∣B∣−1). The equality case is further examined via Vosper's Theorem, which characterizes subsets attaining this bound as arithmetic progressions under suitable conditions. The continuous analogue in Euclidean spaces is then considered, where cardinality is replaced by Lebesgue measure. In this setting, the Brunn–Minkowski Inequality provides a sharp lower bound for the Lebesgue measure of A+B and serves as a geometric counterpart …
Algorithm Performance In The Search For Hamiltonian Cycles, Chance Davis
Algorithm Performance In The Search For Hamiltonian Cycles, Chance Davis
Honors Theses
The Hamiltonian cycle problem is ubiquitous in both computer science and graph theory: Given a connected graph, a solution would either confirm the existence of a cycle which visits each vertex only once or its nonexistence. The importance of this problem, as well as its difficulty, is described in the Clay Mathematics Institute’s Millenium Prize Problems and Karp’s 21 NP-complete problems. Despite its “hardness,” solutions to the Hamiltonian cycle problem are desired in logistics, electronic circuit design, and network routing, among other fields. In this work, we benchmark a promising exhaustive enumeration algorithm on various graphs, including ones derived from …
Enumerating Matrices Of A Given Order Over Finite Fields, Thor Richard Gabrielsen
Enumerating Matrices Of A Given Order Over Finite Fields, Thor Richard Gabrielsen
Honors Theses
This thesis derives a generating function that describes the matrices of a given multiplicative order over finite fields of a given order assuming that the order of a field is not a divisor of the desired order of the matrix. This is done by using the power series known as the cycle index derived from the rational canonical form. This index can be factored, and using the fact that the minimal polynomial divides some polynomial of the form x^k − 1 we can show that the minimal polynomial is squarefree. This sufficiently restricts the form of the rational canonical form …
Knighted Pawn's Tour, Morgan Wilson
Knighted Pawn's Tour, Morgan Wilson
Honors Theses
The Knighted Pawn’s Tour is a variant of the traditional Knight’s Tour problem, whichitself is an instance of the Hamiltonian cycle problem. The deviation from the Knight’s Tour problem is that a pawn begins on any field on the second rank (row), and advances with legal moves that can include captures to the opposite end of the board to become a knight. These fields, used by the pawn on the path to knighthood, are subsequently forbidden for the knight’s return to the starting field. The knight must traverse the rest of the chessboard, visiting each remaining field exactly once …
On Linear Invariants Of Hypergraphs, Clara Chaplin
On Linear Invariants Of Hypergraphs, Clara Chaplin
Honors Theses
We introduce linear invariants of hypergraphs as a way to study hypergraphs by their tensor representations. Our primary research goal is to determine what information linear invariants capture about the hypergraphs they arise from. We first investigate the centroid, which is shown to determine the connected components of a hypergraph. Next, we study the derivations of a hypergraph, and use this linear invariant to define a quotient operator $Q_\mathrm{Der}$ on the collection of all hypergraphs. This operator is shown to be a closure operator in that $Q_\mathrm{Der}(Q_\mathrm{Der}(\mathcal{H}))=Q_\mathrm{Der}(\mathcal{H})$ for any hypergraph $\mathcal{H}$. We apply the operator $Q_\mathrm{Der}$ to synthetically generated hypergraphs, …
Counting Conjugacy Classes Of Elements Of Finite Order In Compact Exceptional Groups, Qidong He
Counting Conjugacy Classes Of Elements Of Finite Order In Compact Exceptional Groups, Qidong He
Honors Theses
Given a compact exceptional group $G$ and $m,s\in\mathbb{N}$, let $N(G,m)$ be the number of conjugacy classes of elements of order $m$ in $G$, and $N(G,m,s)$ the number of such classes whose elements have $s$ distinct eigenvalues. In string theory, the problem of enumerating certain classes of vacua in the string landscape can be rephrased in terms of the study of these quantities. We develop unified combinatorial algorithms based on Burnside's Lemma that can be used to compute both quantities for each of the five compact exceptional groups. Thus, we provide a combinatorial, alternative method to that of Djoković and extend …
Lattice Paths In Diagonals And Dimensions, Freya Bennett
Lattice Paths In Diagonals And Dimensions, Freya Bennett
Honors Theses
The Lattice Paths of Combinatorics have been used in many applications, normally under the guise of a different name, due to its versatility in surface variety and specificity of answer. The Lattice Path’s of game development, in finding paths around barriers in mazes, is called Path Finder with the A∗ algorithms as its method of solving.
Positivity Among P-Partition Generating Functions Of Partially Ordered Sets, Nate Lesnevich
Positivity Among P-Partition Generating Functions Of Partially Ordered Sets, Nate Lesnevich
Honors Theses
We find necessary and separate sufficient conditions for the difference between two labeled partially ordered set's (poset) partition generating functions to be positive in the fundamental basis. We define the notion of a jump sequence for a poset and show how different conditions on the jump sequences of two posets are necessary for those posets to have an order relation in the fundamental basis. Our sufficient conditions are of two types. First, we show how manipulating a poset's Hasse diagram produces a poset that is greater according to the fundamental basis. Secondly, we also provide tools to explain posets that …
Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell
Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell
Honors Theses
Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …
Application Of Linear Sequences To Cryptography, Amanda C. Yeates
Application Of Linear Sequences To Cryptography, Amanda C. Yeates
Honors Theses
Cryptography is the study of a centuries–old technique of secretly transferring information between parties. Linear recurrences were the chosen method of encryption and decryption in the thesis. The Fibonacci sequence, with its Zeckendorf representation, allows for the flexibility of encoding any number desired based on a particular encoding technique used in the film Sherlock Holmes: A Game of Shadows. The main goal is to find other linear recurrences that possess characteristics similar to the Fibonacci sequence to use as suitable substitutes for encoding. Different sequences were analyzed based on a number of criteria. In order for a sequence to be …
Average Genus Of The Cube, Jody Koenemann
Average Genus Of The Cube, Jody Koenemann
Honors Theses
In recent years, there has been interest in the mathematical community in a rapidly developing branch of theoretical mathematics known as random topological graph theory. This new area of mathematics explores the different ways in which certain graphs can be imbedded in given surfaces. The random nature of the new branch results when one also imposes a random distribution on set of all imbeddings of a fixed graph, via the orientation of the edges at each vertex. Using the technique of J. Edmonds, developed in 1960, this paper explores the imbeddings for the graph Q3 using a particular group …
Third Order Degree Regular Graphs, Leslie D. Hayes
Third Order Degree Regular Graphs, Leslie D. Hayes
Honors Theses
A graph G is regular of degree d if for every vertex v in G there exist exactly d vertices at distance 1 from v. A graph G is kth order regular of degree d if for every vertex v in G, there exist exactly d vertices at distance k from v. In this paper, third order regular graphs of degree 1 with small order are characterized.
Imbedding Problems In Graph Theory, William Goodwin
Imbedding Problems In Graph Theory, William Goodwin
Honors Theses
For some years there has been interest among mathematicians in determining the different ways in which certain graphs can be imbedded in given surfaces. M.P. VanStraten in 1948, determined that it is possible to imbed the graph K3,3 (which is the graph representing the famous three houses, three utilities problem) in the torus in only two ways. She then used this fact to show that the graph representing the configuration of Desargues (containing K3,3 as a subgraph) has genus two. One major source of motivation for the work on imbedding problems has been their relation to coloring problems …