Discrete Mathematics and Combinatorics Commons^™

A Hierarchical Graph For Nucleotide Binding Domain 2, Samuel Kakraba

Electronic Theses and Dissertations

One of the most prevalent inherited diseases is cystic fibrosis. This disease is caused by a mutation in a membrane protein, the cystic fibrosis transmembrane conductance regulator (CFTR). CFTR is known to function as a chloride channel that regulates the viscosity of mucus that lines the ducts of a number of organs. Generally, most of the prevalent mutations of CFTR are located in one of two nucleotide binding domains, namely, the nucleotide binding domain 1 (NBD1). However, some mutations in nucleotide binding domain 2 (NBD2) can equally cause cystic fibrosis. In this work, a hierarchical graph is built for NBD2. …

Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just

GS4 Student Scholars Symposium

Pattern packing concerns finding an optimal permutation that contains the maximum number of occurrences of a given pattern and computing the corresponding packing density. In many instances such an optimal permutation can be characterized directly and the number of occurrences of the pattern in interest may be enumerated explicitly. In more complicated patterns a direct characterization may be more challenging, however computational results for long permutations can help provide an indirect characterization of the general form of an optimal permutation. Much work has been done on the study of pattern packing in layered patterns, as the optimal permutation of a …

Two Rosa-Type Labelings Of Uniform K-Distant Trees And A New Class Of Trees, Kimberly Wenger Diller

Honors Projects

A k-distant tree consists of a main path, called the spine, such that each vertex on the spine is joined by an edge to an end-vertex of at most one path on at most k vertices. Those paths, along with the edge joining them to the spine, are called tails. When every vertex on the spine has exactly one incident tail of length k we call the tree a uniform k-distant tree. We show that every uniform k-distant tree admits both a graceful- and an α-labeling.

For a graph G and a positive integer …

Recent Advances In Compressed Sensing: Discrete Uncertainty Principles And Fast Hyperspectral Imaging, Megan E. Lewis

Theses and Dissertations

Compressed sensing is an important field with continuing advances in theory and applications. This thesis provides contributions to both theory and application. Much of the theory behind compressed sensing is based on uncertainty principles, which state that a signal cannot be concentrated in both time and frequency. We develop a new discrete uncertainty principle and use it to demonstrate a fundamental limitation of the demixing problem, and to provide a fast method of detecting sparse signals. The second half of this thesis focuses on a specific application of compressed sensing: hyperspectral imaging. Conventional hyperspectral platforms require long exposure times, which …

Sandpiles, Spanning Trees, And Plane Duality, Melody Chan, Darren B. Glass, Matthew Macauley, David Perkinson, Caryn Werner, Qiaoyu Yang

Math Faculty Publications

Let G be a connected, loopless multigraph. The sandpile group of G is a finite abelian group associated to G whose order is equal to the number of spanning trees in G. Holroyd et al. used a dynamical process on graphs called rotor-routing to define a simply transitive action of the sandpile group of G on its set of spanning trees. Their definition depends on two pieces of auxiliary data: a choice of a ribbon graph structure on G, and a choice of a root vertex. Chan, Church, and Grochow showed that if G is a planar ribbon graph, it …

Periodic Body-And-Bar Frameworks, Ciprian Borcea, Ileana Streinu, Shin-Ichi Tanigawa

Computer Science: Faculty Publications

Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell–Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

Polynomials Occuring In Generating Function Identities For B-Ary Partitions, David Dakota Blair

Graduate Student Publications and Research

Let p_b(n) be the number of integer partitions of n whose parts are powers of b. For each m there is a generating function identity:

f_m(b,q)\sum_{n} p_b(n) q^n = (1-q)^m \sum_{n} p_b(b^m n q)q^n

where n ranges over all integer values. The proof of this identity appears in the doctoral thesis of the author. For more information see http://dakota.tensen.net/2015/rp/.

This dataset is a JSON object with keys m from 1 to 23 whose values are f_m(b,q).

A Plausibly Deniable Encryption Scheme For Personal Data Storage, Andrew Brockmann

HMC Senior Theses

Even if an encryption algorithm is mathematically strong, humans inevitably make for a weak link in most security protocols. A sufficiently threatening adversary will typically be able to force people to reveal their encrypted data. Methods of deniable encryption seek to mend this vulnerability by allowing for decryption to alternate data which is plausible but not sensitive. Existing schemes which allow for deniable encryption are best suited for use by parties who wish to communicate with one another. They are not, however, ideal for personal data storage. This paper develops a plausibly-deniable encryption system for use with personal data storage, …

An Exposition Of Kasteleyn's Solution Of The Dimer Model, Eric Stucky

HMC Senior Theses

In 1961, P. W. Kasteleyn provided a baffling-looking solution to an apparently simple tiling problem: how many ways are there to tile a rectangular region with dominos? We examine his proof, simplifying and clarifying it into this nearly self-contained work.

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.

The Relaxed Edge-Coloring Game And K-Degenerate Graphs, Charles Dunn, David Morawski, Jennifer Firkins Nordstrom

Faculty Publications

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with ∆(F) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆ − j and d ≥ 2j + 2 for 0 ≤ j ≤ ∆ − 1. This both improves and generalizes the result for trees in [10]. More broadly, we generalize the main result in [10] …

Combinatorial Potpourri: Permutations, Products, Posets, And Pfaffians, Norman B. Fox

Theses and Dissertations--Mathematics

In this dissertation we first examine the descent set polynomial, which is defined in terms of the descent set statistics of the symmetric group. Algebraic and topological tools are used to explain why large classes of cyclotomic polynomials are factors of the descent set polynomial. Next the diamond product of two Eulerian posets is studied, particularly by examining the effect this product has on their cd-indices. A combinatorial interpretation involving weighted lattice paths is introduced to describe the outcome of applying the diamond product operator to two cd-monomials. Then the cd-index is defined for infinite posets, with …

The Game Chromatic Number Of Trees And Forests, Charles Dunn, Victor Larsen, Troy Retter, Kira Lindke, Dustin Toci

Faculty Publications

While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree …

Chromatic Polynomials And Orbital Chromatic Polynomials And Their Roots, Jazmin Ortiz

HMC Senior Theses

The chromatic polynomial of a graph, is a polynomial that when evaluated at a positive integer k, is the number of proper k colorings of the graph. We can then find the orbital chromatic polynomial of a graph and a group of automorphisms of the graph, which is a polynomial whose value at a positive integer k is the number of orbits of k-colorings of a graph when acted upon by the group. By considering the roots of the orbital chromatic and chromatic polynomials, the similarities and differences of these polynomials is studied. Specifically we work toward proving a conjecture …

Deletion-Induced Triangulations, Clifford T. Taylor

Theses and Dissertations--Mathematics

Let d > 0 be a fixed integer and let A ⊆ ℝ^d be a collection of n ≥ d + 2 points which we lift into ℝ^d+1. Further let k be an integer satisfying 0 ≤ k ≤ n-(d+2) and assign to each k-subset of the points of A a (regular) triangulation obtained by deleting the specified k-subset and projecting down the lower hull of the convex hull of the resulting lifting. Next, for each triangulation we form the characteristic vector defined by Gelfand, Kapranov, and Zelevinsky by assigning to each …

Polyhedral Problems In Combinatorial Convex Geometry, Liam Solus

Theses and Dissertations--Mathematics

In this dissertation, we exhibit two instances of polyhedra in combinatorial convex geometry. The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study. The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem.

In the first case, we examine combinatorial and algebraic properties of the Ehrhart h*-polynomial of the r-stable (n,k)-hypersimplices. These are a family of polytopes which form a nested chain of subpolytopes within the (n,k)-hypersimplex. We show that a well-studied unimodular triangulation of the (n,k)-hypersimplex restricts to a …

An Isomorphism Problem In Z2, Matt Noble

Theory & Applications of Graphs

We consider Euclidean distance graphs with vertex set ℚ² or ℤ² and address the possibility or impossibility of finding isomorphisms between such graphs. It is observed that for any distances d₁, d₂ the non-trivial distance graphs G(ℚ², d₁) and G(ℚ², d₂) are isomorphic. Ultimately it is shown that for distinct primes _p1, _p2 the non-trivial distance graphs G(ℤ², √p1) and G(ℤ², √p2) are not isomorphic. We conclude with a few additional questions related to this work.

Operator Calculus Algorithms For Multi-Constrained Paths, Jamila Ben Slimane, Rene' Schott, Ye Qiong Song, G. Stacey Staples, Evangelia Tsiontsiou

SIUE Faculty Research, Scholarship, and Creative Activity

Classical approaches to multi-constrained routing problems generally require construction of trees and the use of heuristics to prevent combinatorial explosion. Introduced here is the notion of constrained path algebras and their application to multi-constrained path problems. The inherent combinatorial properties of these algebras make them useful for routing problems by implicitly pruning the underlying tree structures. Operator calculus (OC) methods are generalized to multiple non-additive constraints in order to develop algorithms for the multi constrained path problem and multi constrained optimization problem. Theoretical underpinnings are developed first, then algorithms are presented. These algorithms demonstrate the tremendous simplicity, flexibility and speed …

Kravchuk Polynomials And Induced/Reduced Operators On Clifford Algebras, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

Kravchuk polynomials arise as orthogonal polynomials with respect to the binomial distribution and have numerous applications in harmonic analysis, statistics, coding theory, and quantum probability. The relationship between Kravchuk polynomials and Clifford algebras is multifaceted. In this paper, Kravchuk polynomials are discovered as traces of conjugation operators in Clifford algebras, and appear in Clifford Berezin integrals of Clifford polynomials. Regarding Kravchuk matrices as linear operators on a vector space V, the action induced on the Clifford algebra over V is equivalent to blade conjugation, i.e., reflections across sets of orthogonal hyperplanes. Such operators also have a natural interpretation in …

Clifford Algebra Decompositions Of Conformal Orthogonal Group Elements, G. Stacey Staples, David Wylie

SIUE Faculty Research, Scholarship, and Creative Activity

Beginning with a finite-dimensional vector space V equipped with a nondegenerate quadratic form Q, we consider the decompositions of elements of the conformal orthogonal group CO_Q(V), defined as the direct product of the orthogonal group O_Q(V) with dilations. Utilizing the correspondence between conformal orthogonal group elements and ``decomposable'' elements of the associated Clifford algebra, Cl_Q(V), a decomposition algorithm is developed. Preliminary results on complexity reductions that can be realized passing from additive to multiplicative representations of invertible elements are also presented with examples. The approach here is …