Discrete Mathematics and Combinatorics Commons^™

On The Mysteries Of Interpolation Jack Polynomials, Havi Ellers

HMC Senior Theses

Interpolation Jack polynomials are certain symmetric polynomials in N variables with coefficients that are rational functions in another parameter k, indexed by partitions of length at most N. Introduced first in 1996 by F. Knop and S. Sahi, and later studied extensively by Sahi, Knop-Sahi, and Okounkov-Olshanski, they have interesting connections to the representation theory of Lie algebras. Given an interpolation Jack polynomial we would like to differentiate it with respect to the variable k and write the result as a linear combination of other interpolation Jack polynomials where the coefficients are again rational functions in k. In this …

Phylogenetic Networks And Functions That Relate Them, Drew Scalzo

Williams Honors College, Honors Research Projects

Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate …

Behind The Tiles: Mathematics Of Carcassonne, Emilia Dewyngaert

Across the Bridge: The Merrimack Undergraduate Research Journal

Carcassonne is a tile-placing game where players take turns choosing a tile from a stack and attempting to create a city, road or a meadow. In addition to this, there is a river expansion pack that has river tiles to be placed. This paper focuses on how many different layouts or configurations of the river expansion pack can be created. It also discusses the Matlab code adapted to create a simulation of possible configurations of the river expansion pack.

Blackjack: The Math Behind The Cards, Hanna Blanchard

Mathematics Senior Capstone Papers

In this paper the reader will learn about the math behind the cards in the game of Blackjack. Blackjack or “21” has been played around the world with various rules and regulations in both professional and informal environments. The ultimate objective of the game is to receive a total card value of 21, or as close to 21 as possible without exceeding it, from the cards in a player’s hand in order to beat the dealer’s total. The goal of this project is to calculate the probabilities of various hands to determine the best strategies to win 21. The probabilities …

The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger

Faculty Publications

In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim(G1+G2)=1+dimG1+dimG2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order N will have dimension N−1. We finish by finding lower and upper bounds on the Knill dimension of a graph in terms of its clique number.

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 …

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 …

From Simplest Recursion To The Recursion Of Generalizations Of Cross Polytope Numbers, Yutong Yang

KSU Journey Honors College Capstones and Theses

My research project involves investigations in the mathematical field of combinatorics. The research study will be based on the results of Professors Steven Edwards and William Griffiths, who recently found a new formula for the cross-polytope numbers. My topic will be focused on "Generalizations of cross-polytope numbers". It will include the proofs of the combinatorics results in Dr. Edwards and Dr. Griffiths' recently published paper. $E(n,m)$ and $O(n,m)$, the even terms and odd terms for Dr. Edward's original combinatorial expression, are two distinct combinatorial expressions that are in fact equal. But there is no obvious algebraic evidence to show that …

Combinatorial Polynomial Hirsch Conjecture, Sam Miller

HMC Senior Theses

The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the …

Gallai-Ramsey Numbers For C7 With Multiple Colors, Dylan Bruce

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H₁, ..., H_k, we write G → (H₁, ..., H_k), or G → (H)_k when H₁ = ··· = H_k = H, if every k-edge-coloring of G contains a monochromatic H_i in color i for some i ∈ …

Distribution Of Permutation Statistics Across Pattern Avoidance Classes, And The Search For A Denert-Associated Condition Equivalent To Pattern Avoidance, Joshua Thomas Agustin Davies

Dissertations, Master's Theses and Master's Reports

We begin with a discussion of the symmetricity of $\maj$ over $\des$ in pattern avoidance classes, and its relationship to $\maj$-Wilf equivalence. From this, we explore the distribution of permutation statistics across pattern avoidance for patterns of length 3 and 4.

We then begin discussion of Han's bijection, a bijection on permutations which sends the major index to Denert's statistic and the descent number to the (strong) excedance number. We show the existence of several infinite families of fixed points for Han's bijection.

Finally, we discuss the image of pattern avoidance classes under Han's bijection, for the purpose of finding …

Planar Graphs, Biplanar Graphs And Graph Thickness, Sean M. Hearon

Electronic Theses, Projects, and Dissertations

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.

Combinatorial Descriptions Of The Crystal Structure On Certain Pbw Bases (Extended Abstract), Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

Lusztig's theory of PBW bases gives a way to realize the infinity crystal for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our …

Generalized Eulerian Numbers And Multiplex Juggling Sequences, Esther M. Banaian

All College Thesis Program, 2016-2019

We consider generalizations of both juggling sequences and non-attacking rook placements. We demonstrate the important connection between these objects, and also propose a generalization of the Eulerian numbers. These generalizations give rise to several interesting counting problems, which we explore.

Fibonomial Tilings And Other Up-Down Tilings, Robert Bennett

HMC Senior Theses

The Fibonomial coefficients are a generalization of the binomial coefficients with a rather nice combinatorial interpretation. While the ordinary binomial coefficients count lattice paths in a grid, the Fibonomial coefficients count the number of ways to draw a lattice path in a grid and then Fibonacci-tile the regions above and below the path in a particular way. We may forgo a literal tiling interpretation and, instead of the Fibonacci numbers, use an arbitrary function to count the number of ways to "tile" the regions of the grid delineated by the lattice path. When the function is a combinatorial sequence such …

Towards A Theory Of Recursive Function Complexity: Sigma Matrices And Inverse Complexity Measures, Bradford M. Fournier

LSU New Orleans Theses and Dissertations

This paper develops a data structure based on preimage sets of functions on a finite set. This structure, called the sigma matrix, is shown to be particularly well-suited for exploring the structural characteristics of recursive functions relevant to investigations of complexity. The matrix is easy to compute by hand, defined for any finite function, reflects intrinsic properties of its generating function, and the map taking functions to sigma matrices admits a simple polynomial-time algorithm . Finally, we develop a flexible measure of preimage complexity using the aforementioned matrix. This measure naturally partitions all functions on a finite set by characteristics …

In Honor And Memory Of Professor Lajos Takács, Aliakbar M. Haghighi, Sri G. Mohanty

Applications and Applied Mathematics: An International Journal (AAM)

This issue of AAM is dedicated to honoring and remembering Professor Lajos Takács. While wrapping up the manuscript of my book (co-authored by Dr. Dimitar Mishev): Delayed and Network Queues, I went back to celebrate his 1962 book, Introduction to the Theory of Queues, where he gives an example illustrating a waiting time paradox, where the waiting time of a passenger waiting for a bus at a bus stop is infinite, while, in reality, he will wait a finite unit of time before a bus arrive. I sent Professor Takács an e-mail on December 4, 2015, inquiring if he had …

The Apprentices' Tower Of Hanoi, Cory Bh Ball

Electronic Theses and Dissertations

The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.

A Combinatorial Exploration Of Elliptic Curves, Matthew Lam

HMC Senior Theses

At the intersection of algebraic geometry, number theory, and combinatorics, an interesting problem is counting points on an algebraic curve over a finite field. When specialized to the case of elliptic curves, this question leads to a surprising connection with a particular family of graphs. In this document, we present some of the underlying theory and then summarize recent results concerning the aforementioned relationship between elliptic curves and graphs. A few results are additionally further elucidated by theory that was omitted in their original presentation.

On Representations Of Semigroups Having Hypercube-Like Cayley Graphs, Cody Cassiday, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

The $n-dimensional hypercube, or n-cube, is the Cayley graph of the Abelian group Z₂ⁿ. A number of combinatorially-interesting groups and semigroups arise from modified hypercubes. The inherent combinatorial properties of these groups and semigroups make them useful in a number of contexts, including coding theory, graph theory, stochastic processes, and even quantum mechanics. In this paper, particular groups and semigroups whose Cayley graphs are generalizations of hypercubes are described, and their irreducible representations are characterized. Constructions of faithful representations are also presented for each semigroup. The associated semigroup algebras are realized within the context …

I Don't Play Chess: A Study Of Chess Piece Generating Polynomials, Stephen R. Skoch

Senior Independent Study Theses

This independent study examines counting problems of non-attacking rook, and non-attacking bishop placements. We examine boards for rook and bishop placement with restricted positions and varied dimensions. In this investigation, we discuss the general formula of a generating function for unrestricted, square bishop boards that relies on the Stirling numbers of the second kind. We discuss the maximum number of bishops we can place on a rectangular board, as well as a brief investigation of non-attacking rook placements on three-dimensional boards, drawing a connection to latin squares.

A Study Of Graphical Permutations, Jessica Thune

UNLV Theses, Dissertations, Professional Papers, and Capstones

A permutation π on a set of positive integers {a_1,a_2,...,a_n} is said to be graphical if there exists a graph containing exactly a_i vertices of degree (a_i) for each i. It has been shown that for positive integers with a_1

The Lp Relaxation Orthogonal Array Polytope And Its Permutation Symmetries, Andrew J. Geyer, Dursun A. Bulutoglu, Steven J. Rosenberg

Faculty Publications

Symmetry plays a fundamental role in design of experiments. In particular, symmetries of factorial designs that preserve their statistical properties are exploited to find designs with the best statistical properties. By using a result proved by Rosenberg [6], the concept of the LP relaxation orthogonal array polytope is developed and studied. A complete characterization of the permutation symmetry group of this polytope is made. Also, this characterization is verified computationally for many cases. Finally, a proof is provided.

Permutation Groups And Puzzle Tile Configurations Of Instant Insanity Ii, Amanda N. Justus

Electronic Theses and Dissertations

The manufacturer claims that there is only one solution to the puzzle Instant Insanity II. However, a recent paper shows that there are two solutions. Our goal is to find ways in which we only have one solution. We examine the permutation groups of the puzzle and use modern algebra to attempt to fix the puzzle. First, we find the permutation group for the case when there is only one empty slot at the top. We then examine the scenario when we add an extra column or an extra row to make the game a 4 × 5 puzzle or …

Generalizations Of Pascal's Triangle: A Construction Based Approach, Michael Anton Kuhlmann

UNLV Theses, Dissertations, Professional Papers, and Capstones

The study of this paper is based on current generalizations of Pascal's Triangle, both the expansion of the polynomial of one variable and the multivariate case. Our goal is to establish relationships between these generalizations, and to use the properties of the generalizations to create a new type of generalization for the multivariate case that can be represented in the third dimension.

In the first part of this paper we look at Pascal's original Triangle with properties and classical applications. We then look at contemporary extensions of the triangle to coefficient arrays for polynomials of two forms. The first of …

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar

All HMC Faculty Publications and Research

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root …

Generating Minimal T-Wise Test Suites, Luis C. Gutierrez, Carlos Nieto, Francisco Zapata, Martine Ceberio

COURI Symposium Abstracts, Summer 2012

As the use of computing devices increases every day, users rely on the adequate functioning of software. When software is not tested properly, it can yield erroneous information or a complete failure of the system. The NIST estimates that defective software cost the United States economy close to $60 billion a year. Therefore, there is a need to develop software testing techniques that are time and cost effective. Fully testing software under all possible combinations of parameters values cannot be reduced. However, testing can focus on covering all combinations of subsets of parameters and empirical data shows that doing so …