Digital Commons Network^™

Identities For Partitions Of N With Parts From A Finite Set, Acadia Larsen

Theses and Dissertations

We show for a prime power number of parts m that the first differences of partitions into at most m parts can be expressed as a non-negative linear combination of partitions into at most m – 1 parts. To show this relationship, we combine a quasipolynomial construction of p(n,m) with a new partition identity for a finite number of parts. We prove these results by providing combinatorial interpretations of the quasipolynomial of p(n,m) and the new partition identity. We extend these results by establishing conditions for when partitions of n with parts coming from …

Probabilistic And Extremal Problems In Combinatorics, Sean English

Dissertations

Graph theory as a mathematical branch has been studied rigorously for almost three centuries. In the past century, many new branches of graph theory have been proposed. One important branch of graph theory involves the study of extremal graph theory. In 1941, Turán studied one of the first extremal problems, namely trying to maximize the number of edges over all graphs which avoid having certain structures. Since then, a large body of work has been created in the study of similar problems. In this dissertation, a few different extremal problems are studied, but for hypergraphs rather than graphs. In particular, …

Two Results In Drawing Graphs On Surfaces, Joshua E. Fallon

LSU Doctoral Dissertations

In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct 2-crossing-critical graphs for each non-orientable surface. Next, we use 2-amalgamations to construct 2-crossing-critical graphs for each orientable surface other than the sphere. Finally, we contribute to the pursuit of characterizing 4-connected graphs that embed on the Klein bottle and fail to be edge-hamiltonian. We show that known 4-connected counterexamples to edge-hamiltonicity on the Klein bottle are hamiltonian …

The Search For The Cyclic Sieving Phenomenon In Plane Partitions, William J. Asztalos

DePaul Discoveries

The efforts of this research project are best understood in the context of the subfield of dynamical combinatorics, in which one enumerates a set of combinatorial objects by defining some action to guide the search for underlying structures. While there are many examples with varying degrees of complexity, the necklace problem, which concerns the possible unique configurations of beads in a ring up to rotational symmetry, is a well-known example. Though this sort of approach to enumeration has been around for a century or more, activity in this area has intensified in the last couple of decades. Perhaps the most …

Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole

Undergraduate Honors Theses

Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the d^t t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds …

Notes On The Proof Of The Van Der Waerden Permanent Conjecture, Vicente Valle Martinez

Vicente Valle Martinez

A Mathematical Analysis Of The Game Of Chess, John C. White

Selected Honors Theses

This paper analyzes chess through the lens of mathematics. Chess is a complex yet easy to understand game. Can mathematics be used to perfect a player’s skills? The work of Ernst Zermelo shows that one player should be able to force a win or force a draw. The work of Shannon and Hardy demonstrates the complexities of the game. Combinatorics, probability, and some chess puzzles are used to better understand the game. A computer program is used to test a hypothesis regarding chess strategy. Through the use of this program, we see that it is detrimental to be the first …

The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph G …

On The Density Of The Odd Values Of The Partition Function, Samuel Judge

Dissertations, Master's Theses and Master's Reports

The purpose of this dissertation is to introduce a new approach to the study of one of the most basic and seemingly intractable problems in partition theory, namely the conjecture that the partition function $p(n)$ is equidistributed modulo $2$. We provide a doubly-indexed, infinite family of conjectural identities in the ring of series $\Z_2[[q]]$, which relate $p(n)$ with suitable $t$-multipartition functions, and show how to, in principle, prove each such identity. We will exhibit explicit proofs for $32$ of our identities. However, the conjecture remains open in full generality. A striking consequence of these conjectural identities is that, under suitable …