Digital Commons Network^™

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 …

The Earth Mover's Distance Through The Lens Of Algebraic Combinatorics, William Quentin Erickson

Theses and Dissertations

The earth mover's distance (EMD) is a metric for comparing two histograms, with burgeoning applications in image retrieval, computer vision, optimal transport, physics, cosmology, political science, epidemiology, and many other fields. In this thesis, however, we approach the EMD from three distinct viewpoints in algebraic combinatorics. First, by regarding the EMD as the symmetric difference of two Young diagrams, we use combinatorial arguments to answer statistical questions about histogram pairs. Second, we adopt as a natural model for the EMD a certain infinite-dimensional module, known as the first Wallach representation of the Lie algebra su(p,q), which arises in the Howe …

The Gini Index In Algebraic Combinatorics And Representation Theory, Grant Joseph Kopitzke

Theses and Dissertations

The Gini index is a number that attempts to measure how equitably a resource is distributed throughout a population, and is commonly used in economics as a measurement of inequality of wealth or income. The Gini index is often defined as the area between the "Lorenz curve" of a distribution and the line of equality, normalized to be between zero and one. In this fashion, we will define a Gini index on the set of integer partitions and prove some combinatorial results related to it; culminating in the proof of an identity for the expected value of the Gini index. …

Cocyclic Hadamard Matrices: An Efficient Search Based Algorithm, Jonathan S. Turner

Theses and Dissertations

This dissertation serves as the culmination of three papers. “Counting the decimation classes of binary vectors with relatively prime fixed-density" presents the first non-exhaustive decimation class counting algorithm. “A Novel Approach to Relatively Prime Fixed Density Bracelet Generation in Constant Amortized Time" presents a novel lexicon for binary vectors based upon the Discrete Fourier Transform, and develops a bracelet generation method based upon the same. “A Novel Legendre Pair Generation Algorithm" expands upon the bracelet generation algorithm and includes additional constraints imposed by Legendre Pairs. It further presents an efficient sorting and comparison algorithm based upon symmetric functions, as well …

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 …

Algebraic And Combinatorial Properties Of Schur Rings Over Cyclic Groups, Andrew F. Misseldine

Theses and Dissertations

In this dissertation, we explore the nature of Schur rings over finite cyclic groups, both algebraically and combinatorially. We provide a survey of many fundamental properties and constructions of Schur rings over arbitrary finite groups. After specializing to the case of cyclic groups, we provide an extensive treatment of the idempotents of Schur rings and a description for the complete set of primitive idempotents. We also use Galois theory to provide a classification theorem of Schur rings over cyclic groups similar to a theorem of Leung and Man and use this classification to provide a formula for the number of …

On The Combinatorics Of Certain Garside Semigroups, Christopher R. Cornwell

Theses and Dissertations

In his dissertation, F.A. Garside provided a solution to the word and conjugacy problems in the braid group on n-strands, using a particular element that he called the fundamental word. Others have since defined fundamental words in the generalized setting of Artin groups, and even more recently in Garside groups. We consider the problem of finding the number of representations of a power of the fundamental word in these settings. In the process, we find a Pascal-like identity that is satisfied in a certain class of Garside groups.

Sandwich Theorem And Calculation Of The Theta Function For Several Graphs, Marcia Ling Riddle

Theses and Dissertations

This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the "Sandwich Theorem". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal.

First I am going to describe the proof of the …

Bounding The Number Of Graphs Containing Very Long Induced Paths, Steven Kay Butler

Theses and Dissertations

Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths.

In this thesis we show a way to represent such graphs in terms of an array with two colors and a labeled graph. Using this representation and the techniques of Polya counting we will then be able to get upper and lower bounds for graphs containing a long path as an induced subgraph.

In particular, if we let P(n,k) be the number of graphs on n+k vertices which contains P_n, a path on n vertices, as …