Discrete Mathematics and Combinatorics Commons^™

A Numerical Method For Coefficient Reconstruction Of A Periodic Inverse Source Problem, Robert Ireri

Theses, Dissertations and Capstones

This thesis investigates a numerical method for solving the periodic inverse source problem governed by the Helmholtz equation. The problem involves reconstructing an unknown periodic source term from boundary measurements, which is inherently ill-posed. To address this challenge, we employ a quasi-reversibility method (QRM) combined with a basis function expansion to stabilize the inverse reconstruction. The forward problem is solved using the Lippmann-Schwinger equation, discretized via the trapezoidal rule, and the inverse problem is formulated as a constrained least-squares minimization. The discretized system is efficiently solved using sparse matrix techniques and regularization strategies. Numerical experiments demonstrate the robustness of the …

Discrete Fractional Gompertz Models, Rebecca Oduro

Theses, Dissertations and Capstones

This thesis explores the theory and application of discrete fractional Gompertz models—systems that integrate fractional difference operators into the classical Gompertz growth paradigm. By doing so, these models capture both discrete time steps and the long-range memory effects characteristic of fractional calculus. After outlining the fundamental notions of discrete calculus, discrete fractional sums and differences, and related special functions such as the discrete Mittag–Leffler function, we derive various fractional Gompertz-type equations. We prove the existence and uniqueness of solutions to these fractional difference equations, often employing discrete analogues of standard solution methods like variation of constants. We also investigate the …

Codes From Incidence Matrices Of Hypergraphs, Sudipta Mallik, Bahattin Yildiz

Mathematics Faculty Research

Binary codes are constructed from incidence matrices of hypergraphs. A combinatorial description is given for the minimum distances of such codes via a combinatorial tool called “eonv”. This combinatorial approach provides a faster alternative method of finding the minimum distance, which is known to be a hard problem. This is demonstrated on several classes of codes from hypergraphs. In particular the “eonv” method is used to prove that the minimum distance of codes from incidence matrices of complete 3-partite 3-uniform hypergraphs with partite set size of n is n2. A lower bound on the minimum distances of codes from …

An Approach To Multidimensional Discrete Generating Series, Svetlana S. Akhtamova, Tom Cuchta, Alexander P. Lyapin

Mathematics Faculty Research

We extend existing functional relationships for the discrete generating series associated with a single-variable linear polynomial coefficient difference equation to the multivariable case.

Discrete Complementary Exponential And Sine Integral Functions, Samer Assaf, Tom Cuchta

Mathematics Faculty Research

Discrete analogues of the sine integral and complementary exponential integral functions are investigated. Hypergeometric representation, power series, and Laplace transforms are derived for each. The difficulties in extending these definitions to other common trigonometric integral functions are discussed.

Incidence And Laplacian Matrices Of Wheel Graphs And Their Inverses, Jerad Ipsen, Sudipta Mallik

Mathematics Faculty Research

It has been an open problem to find the Moore-Penrose inverses of the incidence, Laplacian, and signless Laplacian matrices of families of graphs except trees and unicyclic graphs. Since the inverse formulas for an odd unicyclic graph and an even unicyclic graph are quite different, we consider wheel graphs as they are formed from odd or even cycles. In this article we solve the open problem for wheel graphs. This work has an interesting connection to inverses of circulant matrices.

Discrete Polylogarithm Functions, Tom Cuchta, Dallas Freeman

Mathematics Faculty Research

We investigate a discrete analogue of the polylogarithm function. Difference and summation relations are obtained, as well as its connection to the discrete hypergeometric series.

Matrix Tree Theorem For The Net Laplacian Matrix Of A Signed Graph, Sudipta Mallik

Mathematics Faculty Research

For a simple signed graph G with the adjacency matrix A and net degree matrix D±, the net Laplacian matrix is L± = D±−A. We introduce a new oriented incidence matrix N± which can keep track of the sign as well as the orientation of each edge of G. Also L± = N±(N±)T. Using this decomposition, we find the number of both positive and negative spanning trees of G in terms of the principal minors of L± generalizing the Matrix Tree Theorem for an unsigned graph. …

New Formulations Of The Union-Closed Sets Conjecture, Sudipta Mallik

Mathematics Faculty Research

The union-closed sets conjecture states that if a finite set A of finite sets is union-closed and A ≠ {∅}, then there exists an element in ∪ _{A ∈ A} A that belongs to at least half of the sets in A. We present three new formulations of the union-closed conjecture in terms of matrices, graphs, and hypergraphs.

Discrete Hypergeometric Legendre Polynomials, Tom Cuchta

Mathematics Faculty Research

A discrete analog of the Legendre polynomials defined by discrete hypergeometric series is investigated. The resulting polynomials have qualitatively similar properties to classical Legendre polynomials. We derive their difference equations, recurrence relations, and generating function.

Completing Partial Transversals Of Cayley Tables Of Abelian Groups, Jaromy Kuhl, Donald Mcginn, Michael W. Schroeder

Mathematics Faculty Research

In 2003 Grüttmüller proved that if n ⩾ 3 is odd, then a partial transversal of the Cayley table of ℤₙ with length 2 is completable to a transversal. Additionally, he conjectured that a partial transversal of the Cayley table of ℤₙ with length k is completable to a transversal if and only if n is odd and either n ∈ {k, k + 1} or n ⩾ 3k - 1. Cavenagh, Hämäläinen, and Nelson (in 2009) showed the conjecture is true when k = 3 and n is prime. In this paper, we prove Grüttmüller's conjecture for k = …

Graph Theoretic Aspects Of Minimum Distance And Equivalence Of Binary Linear Codes, Sudipta Mallik, Bahattin Yildiz

Mathematics Faculty Research

A binary linear [2n, n]-code with generator matrix [I_n|A] can be associated with a digraph on n vertices with adjacency matrix A and vice versa. We use this connection to present a graph theoretic formula for the minimum distance of codes with information rate 1/2. We also formulate the equivalence of such codes via new transformations on corresponding digraphs.

On Hamilton Cycle Decompositions Of Complete Multipartite Graphs Which Are Both Cyclic And Symmetric, Fatima A. Akinola

Theses, Dissertations and Capstones

Let G be a graph with v vertices. A Hamilton cycle of a graph is a collection of edges which create a cycle using every vertex. A Hamilton cycle decomposition is cyclic if the set of cycle is invariant under a full length permutation of the vertex set. We say a decomposition is symmetric if all the cycles are invariant under an appropriate power of the full length permutation. Such decompositions are known to exist for complete graphs and families of other graphs. In this work, we show the existence of cyclic n-symmetric Hamilton cycle decompositions of a family …

A Gompertz Distribution For Time Scales, Tom Cuchta, Robert Jon Nichel, Sabrina Streipert

Mathematics Faculty Research

We investigate a family of probability distributions, with three parameters associated with the dynamic Gompertz function. We prove its existence for various parameter sets and discuss the existence of its time scale moments. Afterwards, we investigate the special case of discrete time scales, where it is shown that the discrete Gompertz distribution is a q -geometric distribution of the second kind. Further, we find their q -binomial moments, we bound their expected value, and we show how a classical Gompertz distribution is obtained from them.

On Monochromatic Pairs With Nondecreasing Diameters, Adam O'Neal, Michael W. Schroeder

Mathematics Faculty Research

Let n m r t be positive integers and Δ : [n] → [r]. We say Δ is (m, r, t) - permissible if there exist t disjoint m-sets B₁,…,B_t contained in [n] for which

1. |Δ(B_i)| = 1 for each i = 1,2,…, t.
2. max(B_i) < min(B_i+1) for each i = 1,2,…, t − 1, and
3. max(B_i) − min(B_i) ≤ max(B_i+1) − max(B_i+1) for each i = …

On Monochromatic Sets With Nondecreasing Diameter, Adam O’Neal

Theses, Dissertations and Capstones

Our problem comes from the field of combinatorics known as Ramsey theory. Ramsey theory, in a general sense, is about identifying the threshold for which a family of objects, associated with a particular parameter, goes from never or sometimes satisfying a certain property to always satisfying that property. Research in Ramsey theory has applications in design theory and coding theory. For integers m, r, and t, we say that a set of n integers colored with r colors is (m, r, t)-permissible if there exist t monochromatic subsets B₁, B₂, . . . , B_{t …}

On The Existence Of Partitioned Incomplete Latin Squares With Five Parts, Jaromy Kuhl, Donald Mcginn, Michael W. Schroeder

Mathematics Faculty Research

Let a, b, c, d, e be positive integers such that a ≤ b ≤ c ≤ d ≤ e. Heinrich showed the existence of a partitioned incomplete Latin square (PILS) of type (a, b, c) and (a, b, c, d) if and only if a = b = c and 2a ≥ d. For PILS of type (a,b,c,d,e), it is necessary that a + b + c ≥ e, but not sufficient, and no characterization is currently known. In this talk we provide an additional …

Circulant Matrices And Mathematical Juggling, Richard A. Brualdi, Michael W. Schroeder

Mathematics Faculty Research

Circulants form a well-studied and important class of matrices, and they arise in many algebraic and combinatorial contexts, in particular as multiplication tables of cyclic groups and as special classes of latin squares. There is also a known connection between circulants and mathematical juggling. The purpose of this note is to expound on this connection developing further some of its properties. We also formulate some problems and conjectures with some computational data supporting them.

An Extension Of The Jeu De Taquin, Joanna Mckinney

Theses, Dissertations and Capstones

The Knuth transformations on words, the jeu de taquin moves on tableaux, and the Robinson–Schensted–Knuth algorithm produce the same equivalence classes for words. By observing the connections between these three methods we find and prove there exists connections between the Assaf–Knuth transformations, our extension of the jeu de taquin, and p-RSK. We know there exists an algebraic way to expand Macdonald polynomials in terms of the Schur functions. The form of the expansion implies there should be a combinatorial way to find the expansion. Loehr found a Robinson–Schensted–Knuth like algorithm that works in some cases. By finding an extension of …

A Bijection On Classes Enumerated By The Schröder Numbers, Michael W. Schroeder, Rebecca Smith

Mathematics Faculty Research

We consider a sorting machine consisting of two stacks in series where the first stack has the added restriction that entries in the stack must be in decreasing order from top to bottom. The class of permutations sortable by this machine is known to be enumerated by the Schroder numbers. In this paper, we give a bijection between these sortable permutations of length n and Schroder paths of order n − 1: the lattice paths from (0, 0) to (n − 1, n − 1) composed of East steps (1, 0), North steps (0, 1), and Diagonal steps (1, …

Completing Partial Latin Squares With One Nonempty Row, Column, And Symbol, Jaromy Kuhl, Michael W. Schroeder

Mathematics Faculty Research

Let r,c,s ∈{1,2,…,n} and let PP be a partial latin square of order n in which each nonempty cell lies in row r, column c, or contains symbol s. We show that if n ∉ {3, 4, 5} and row r, column c, and symbol s can be completed in P, then a completion of P exists. As a consequence, this proves a conjecture made by Casselgren and Häggkvist. Furthermore, we show exactly when row r, column c, and symbol s can be completed.

The Maximum Multiplicity Of An Eigenvalue Of Symmetric Matrices With A Given Graph, Keivan Hassani Monfared, Sudipta Mallik

Mathematics Faculty Research

For a graph G, M(G) denotes the maximum multiplicity occurring of an eigenvalue of a symmetric matrix whose zero-nonzero pattern is given by edges of G. We introduce two combinatorial graph parameters T^-(G) and T^+(G) that give a lower and an upper bound for M(G) respectively, and we show that these bounds are sharp.

Skew Row-Strict Quasisymmetric Schur Functions, Sarah K. Mason, Elizabeth Niese

Mathematics Faculty Research

Mason and Remmel introduced a basis for quasisymmetric functions known as the row-strict quasisymmetric Schur functions. This basis is generated combinatorially by fillings of composition diagrams that are analogous to the row-strict tableaux that generate Schur functions. We introduce a modification known as Young row-strict quasisymmetric Schur functions, which are generated by row-strict Young composition fillings. After discussing basic combinatorial properties of these functions, we define a skew Young row-strict quasisymmetric Schur function using the Hopf algebra of quasisymmetric functions and then prove this is equivalent to a combinatorial description. We also provide a decomposition of the skew Young row-strict …

New Combinatorial Formulations Of The Shuffle Conjecture, Nicholas A. Loehr, Elizabeth Niese

Mathematics Faculty Research

The shuffle conjecture (due to Haglund, Haiman, Loehr, Remmel, and Ulyanov) provides a combinatorial formula for the Frobenius series of the diagonal harmonics module DH_n, which is the symmetric function∇(e_n). This formula is a sum over all labeled Dyck paths of terms built from combinatorial statistics called area, dinv, and IDes. We provide three new combinatorial formulations of the shuffle conjecture based on other statistics on labeled paths, parking functions, and related objects. Each such reformulation arises by introducing an appropriate new definition of the inverse descent set. Analogous results are proved for the higher-order shuffle …

A New Recursion For Three-Column Combinatorial Macdonald Polynomials, Elizabeth Niese

Mathematics Faculty Research

The Hilbert series of the Garsia–Haiman module M_μ can be described combinatorially as the generating function of certain fillings of the Ferrers diagram of μ where μ is an integer partition of n . Since there are n ! fillings that generate , it is desirable to find recursions to reduce the number of fillings that need to be considered when computing combinatorially. In this paper, we present a combinatorial recursion for the case where μ is an n by 3 rectangle. This allows us to reduce the number of fillings under consideration from (3n)! to (3n)!/(3!ⁿn!).

A Bijective Proof Of A Factorization Formula For Specialized Macdonald Polynomials, Nicholas A. Loehr, Elizabeth Niese

Mathematics Faculty Research

Let μ and ν = (ν 1, . . . , ν k ) be partitions such that μ is obtained from ν by adding m parts of sizer. Descouens and Morita proved algebraically that the modified Macdonald polynomials

H~μ(X;q,t)

satisfy the identity

H~μ=H~νH~(r^m)

when the parameter t is specialize to an mth root of unity. Descouens, Morita, and Numata proved this formula bijectively when r ≤ ν k and

r∈{1,2}.

This note gives a bijective proof of the formula for all r ≤ ν k .

Cyclic Matching Sequencibility Of Graphs, Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder

Mathematics Faculty Research

We define the cyclic matching sequencibility of a graph to be the largest integer d such that there exists a cyclic ordering of its edges so that every d consecutive edges in the cyclic ordering form a matching. We show that the cyclic matching sequencibility of K_2m and K_2m+1 equals m − 1.

Alternative Proofs On The Indices Of Cacti And Unicyclic Graphs With N Vertices, Sudipta Mallik

Mathematics Faculty Research

Let H_n be the cactus obtained from the star K_1,n—1 by adding _└ n—1/2_┘ independent edges between pairs of pendant vertices. Let K₁,⁺_n—1 be the unicyclic graph obtained from the star by appending one edge. In this paper we give alternative proofs of the following results: Among all cacti with n vertices, H_n is the unique cactus whose spectral radius is maximal, and among all unicyclic graphs with n vertices, K₁,⁺_n—1 is the unique unicyclic graph whose spectral radius is maximal. We also prove …

Convergence Analysis Of Mcmc Method In The Study Of Genetic Linkage With Missing Data, Diana Fisher

Theses, Dissertations and Capstones

Computational infeasibility of exact methods for solving genetic linkage analysis problems has led to the development of a new collection of stochastic methods, all of which require the use of Markov chains. The purpose of this work is to investigate the complexities of missing data in pedigree analysis using the Monte Carlo Markov Chain (MCMC) method as compared to the exact results. Also, we attempt to determine an association between missing data in a familial pedigree and the convergence to stationarity of a descent graph Markov chain implemented in the stochastic method for parametric linkage analysis.

In particular, we will …

Reduction Of The Gibbs Phenomenon Via Interpolation Using Chebyshev Polynomials, Filtering And Chebyshev-Pade' Approximations, Rob-Roy L. Mace

Theses, Dissertations and Capstones

In this manuscript, we will examine several methods of interpolation, with an emphasis on Chebyshev polynomials and the removal of the Gibbs Phenomenon. Included as an appendix are the author’s Mat- Lab implementations of Lagrange, Chebyshev, and rational interpolation methods.