Discrete Mathematics and Combinatorics Commons^™

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.

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 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.

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 …