Discrete Mathematics and Combinatorics Commons^™

Impartial Geodetic Building Games On Graphs, Bret J. Benesh, Dana C. Ernst, Marie Meyer, Sarah K. Salmon, Nándor Sieben

Mathematics Faculty Publications

A subset of the vertex set of a graph is geodetically convex if it contains every vertex on any shortest path between two elements of the set. The convex hull of a set of vertices is the smallest convex set containing the set. We study variations of two games introduced by Buckley and Harary, where two players take turns selecting previously-unselected vertices of a graph until the convex hull of the jointly-selected vertices becomes too large. The last player to move is the winner. The achievement game ends when the convex hull contains every vertex. In the avoidance game, the …

Id Numbers Of Lobster Graphs, Mark Anthony C. Tolentino, Luis Silvestre Jr, Richwell T. Chan Sim, Amir Jann Erikson Diga, Althea Julia R. Loyola

Mathematics Faculty Publications

No abstract provided.

Optimal Tile-Based Dna Self-Assembly Designs For Lattice Graphs And Platonic Solids, Leyda Almodovar, Joanna Ellis-Monaghan, Amanda Harsy, Cory Johnson, Jessica Sorrells

Mathematics Faculty Publications

A design goal in self-assembly of DNA nanostructures is to find minimal sets of branched junction molecules that will self-assemble into targeted structures. This process can be modeled using techniques from graph theory. This paper is a collection of proofs for a set of DNA complexes which can be represented by specific graphs, namely Platonic solids, square lattice graphs, and triangular lattice graphs. This work supplements the results presented in https://arxiv.org/abs/2108.00035

Quasilinearization Applied To Boundary Value Problems At Resonance For Riemann-Liouville Fractional Differential Equations, Paul W. Eloe, Jaganmohan Jonnalagadda

Mathematics Faculty Publications

The quasilinearization method is applied to a boundary value problem at resonance for a Riemann-Liouville fractional differential equation. Under suitable hypotheses, the method of upper and lower solutions is employed to establish uniqueness of solutions. A shift method, coupled with the method of upper and lower solutions, is applied to establish existence of solutions. The quasilinearization algorithm is then applied to obtain sequences of lower and upper solutions that converge monotonically and quadratically to the unique solution of the boundary value problem at resonance.

Infinite Sets Of Solutions And Almost Solutions Of The Equation N∙M = Reversal(N∙M) Ii, Viorel Nitica, Cem Ekinci

Mathematics Faculty Publications

Motivated by their intrinsic interest and by applications to the study of numeric palindromes and other sequences of integers, we discover a method for producing infinite sets of solutions and almost solutions of the equation N M reversal N M ⋅= ⋅ ( ) , our results are valid in a general numeration base b > 2 .

On Eigenvalue Bounds For The Finite-State Birth-Death Process Intensity Matrix, R.R.P Tan, K Ikeda, Len Patrick Dominic M. Garces

Mathematics Faculty Publications

The paper sets forth a novel eigenvalue interlacing property across the finite-state birth-death process intensity matrix and two clearly identified submatrices as an extension of Cauchy’s interlace theorem for Hermitian matrix eigenvalues. A supplemental proof involving an examination of probabilities acquired from specific movements across states and a derivation of a form for the eigenpolynomial of the matrix through convolution and Laplace transform is then presented towards uncovering a similar characteristic for the general Markov chain transition rate matrix. Consequently, the proposition generates bounds for each eigenvalue of the original matrix, easing numerical computation. To conclude, the applicability of the …

A Zero-Suppressed Binary Decision Diagram Approach For Constrained Path Enumeration, Renzo Roel P. Tan, Jun Kawahara, Agnes Garciano, Immanuel Sin

Mathematics Faculty Publications

Combinatorial optimization over graphs has been the subject of research. Recently, the solution of such problems by enumeration using a compact data structure called the zero-suppressed binary decision diagram was proposed and studied. The paper augments the existing frontier-based search method of construction and puts forth a technique for accommodating additional constraints during computation. The shortest and longest path problems for the Osaka Metro transit network are simultaneously solved as demonstration. Furthermore, a comparison of the approach with a conventional integer programming method is presented towards justifying the effectiveness of the algorithm.

String C-Groups Of Order 1024, Yasushi Gomi, Mark L. Loyola, Ma. Louise Antonette N. De Las Peñas

Mathematics Faculty Publications

This paper determines the nondegenerate string C-groups of order 1024. For groups of rank 3, we use the technique of central extension of string C-groups of order 512. For groups of rank at least 4, we compute for quotients of universal string C-groups.

Classification Of Book Representations Of K6, Dana Rowland

Mathematics Faculty Publications

A book representation of a graph is a particular way of embedding a graph in three dimensional space so that the vertices lie on a circle and the edges are chords on disjoint topological disks. We describe a set of operations on book representations that preserves ambient isotopy, and apply these operations to K6, the complete graph with six vertices. We prove there are exactly 59 distinct book representations for K6, and we identify the number and type of knotted and linked cycles in each representation. We show that book representations of K6 contain between one and seven links, and …

Impartial Avoidance And Achievement Games For Generating Symmetric And Alternating Groups, Bret J. Benesh, Dana C. Ernst, Nándor Sieben

Mathematics Faculty Publications

Anderson and Harary introduced two impartial games on finite groups. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly-selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. We determine the nim-numbers, and therefore the outcomes, of these games for symmetric and alternating groups.

Impartial Avoidance Games For Generating Finite Groups, Bret J. Benesh, Dana C. Ernst, Nándor Sieben

Mathematics Faculty Publications

We study an impartial avoidance game introduced by Anderson and Harary. The game is played by two players who alternately select previously unselected elements of a finite group. The first player who cannot select an element without making the set of jointly-selected elements into a generating set for the group loses the game. We develop criteria on the maximal subgroups that determine the nim-numbers of these games and use our criteria to study our game for several families of groups, including nilpotent, sporadic, and symmetric groups.

Some Properties Of The Exchange Operator With Respect To Structured Matrices Defined By Indefinite Scalar Product Spaces, Hanz Martin C. Cheng, Roden Jason David

Mathematics Faculty Publications

The properties of the exchange operator on some types of matrices are explored in this paper. In particular, the properties of exc(A,p,q), where A is a given structured matrix of size (p+q)Ã(p+q) and exc : M ÃNÃN â M is the exchange operator are studied. This paper is a generalization of one of the results in [N.J. Higham. J-orthogonal matrices: Properties and generation. SIAM Review, 45:504â519, 2003.].

Finite Factors Of Bernoulli Schemes And Distinguishing Labelings Of Directed Graphs, Andrew Lazowski, Stephen M. Shea

Mathematics Faculty Publications

A labeling of a graph is a function from the vertices of the graph to some finite set. In 1996, Albertson and Collins defined distinguishing labelings of undirected graphs. Their definition easily extends to directed graphs. Let G be a directed graph associated to the k -block presentation of a Bernoulli scheme X . We determine the automorphism group of G , and thus the distinguishing labelings of G . A labeling of G defines a finite factor of X . We define demarcating labelings and prove that demarcating labelings define finitarily Markovian finite factors of X . We use …

On A Pair Of Identities From Ramanujan's Lost Notebook, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

Using a pair of two variable series-product identities recorded by Ramanujan in the lost notebook as inspiration, we find some new identities of similar type. Each identity immediately implies an infinite family of Rogers-Ramanujan type identities, some of which are well-known identities from the literature. We also use these identities to derive some general identities for integer partitions.

Polynomial Generalizations Of Two-Variable Ramanujan Type Identities, James Mclaughlin, Andrew V. Sills

Mathematics Faculty Publications

No abstract provided.

The Graph Distance Game, Wayne Goddard, Anne Sinko, Peter J. Slater, Honghai Xu

Mathematics Faculty Publications

In the graph distance game, two players alternate in constructing a maximal path. The objective function is the distance between the two endpoints of the path, which one player tries to maximize and the other tries to minimize. In this note, we examine the distance game for various graphs, and provide general bounds, exact results for special graphs, and an algorithm for trees. Computer calculations suggest interesting conjectures for grids.

A New Summation Formula For Wp-Bailey Pairs, James Mclaughlin

Mathematics Faculty Publications

No abstract provided.

Hybrid Proofs Of The Q-Binomial Theorem And Other Identities, Dennis Eichhorn, James Mclaughlin, Andrew V. Sills

Mathematics Faculty Publications

No abstract provided.

Some Implications Of Chu's 10Ψ10 Generalization Of Bailey's 6Ψ6 Summation Formula, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

Lucy Slater used Bailey's 6Ã6 summation formula to derive the Bailey pairs she used to construct her famous list of 130 identities of the Rogers-Ramanujan type.

In the present paper we apply the same techniques to Chu's 10Ã10 generalization of Bailey's formula to produce quite general Bailey pairs. Slater's Bailey pairs are then recovered as special limiting cases of these more general pairs.

In re-examining Slater's work, we find that her Bailey pairs are, for the most part, special cases of more general Bailey pairs containing one or more free parameters. Further, we also find new …

Lifting Bailey Pairs To Wp-Bailey Pairs, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

A pair of sequences (αn(a,k,q),βn(a,k,q)) such that α0(a,k,q)=1 and βn(a,k,q)=∑nj=0(k/a;q)n−j(k;q)n+j(q;q)n−j(aq;q)n+jαj(a,k,q) is termed aWP-Bailey Pair . Upon setting k=0 in such a pair we obtain a Bailey pair. In the present paper we consider the problem of “lifting” a Bailey pair to a WP-Bailey pair, and use some of the new WP-Bailey pairs found in this way to derive some new identities between basic hypergeometric series and new single-sum and double-sum identities of the Rogers–Ramanujan–Slater type.

Some More Identities Of Rogers-Ramanujan Type, Douglas Bowman, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

In this we paper we prove several new identities of the Rogers-Ramanujan-Slater type. These identities were found as the result of computer searches. The proofs involve a variety of techniques, including series-series identities, Bailey pairs, a theorem of Watson on basic hypergeometric series, generating functions and miscellaneous methods.

Combinatorics Of Ramanujan-Slater Type Identities, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

We provide the missing member of a family of four q-series identities related to the modulus 36, the other members having been found by Ramanujan and Slater. We examine combinatorial implications of the identities in this family, and of some of the identities we considered inIdentities of the Ramanujan-Slater type related to the moduli 18 and 24.

Rogers-Ramanujan Computer Searches, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

We describe three computer searches (in PARI/GP, Maple, and Mathematica, respectively) which led to the discovery of a number of identities of Rogers–Ramanujan type and identities of false theta functions.

Queen's Domination Using Border Squares And (A,B)-Restricted Domination, Anne Sinko, Peter J. Slater

Mathematics Faculty Publications

In this paper we introduce a variant on the long studied, highly entertaining, and very difficult problem of determining the domination number of the queen's chessboard graph, that is, determining how few queens are needed to protect all of the squares of a k by k chessboard. Motivated by the problem of minimum redundance domination, we consider the problem of determining how few queens restricted to squares on the border can be used to protect the entire chessboard. We give exact values of "border-queens" required for the k by k chessboard when 1≤k≤13. For the general case, we …

Ramanujan-Slater Type Identities Related To The Moduli 18 And 24, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

We present several new families of Rogers–Ramanujan type identities related to the moduli 18 and 24. A few of the identities were found by either Ramanujan, Slater, or Dyson, but most are believed to be new. For one of these families, we discuss possible connections with Lie algebras. We also present two families of related false theta function identities.

Rogers-Ramanujan-Slater Type Identities, James Mclaughlin, Andrew V. Sills, Peter Zimmer

Mathematics Faculty Publications

In this survey article, we present an expanded version of Lucy Slater’s famous list of identities of the Rogers-Ramanujan type, including identities of similar type, which were discovered after the publication of Slater’s papers, and older identities (such as those in Ramanujan’s lost notebook) which were not included in Slater’s papers. We attempt to supply the earliest known reference for each identity. Also included are identities of false theta functions, along with their relationship to Rogers Ramanujan type identities. We also describe several ways in which pairs/larger sets of identities may be related, as well as dependence relationships between identities.

Efficient Domination In Knights Graphs, Anne Sinko, Peter J. Slater

Mathematics Faculty Publications

The influence of a vertex set S ⊆V(G) is I(S) = Σ_v∈S(1 + deg(v)) = Σ_v∈S |N[v]|, which is the total amount of domination done by the vertices in S. The efficient domination number F(G) of a graph G is equal to the maximum influence of a packing, that is, F(G) is the maximum number of vertices one can dominate under the restriction that no vertex gets dominated more than once.

In …

On Classifying Finite Edge Colored Graphs With Two Transitive Automorphism Groups, Thomas Q. Sibley

Mathematics Faculty Publications

This paper classifies all finite edge colored graphs with doubly transitive automorphism groups. This result generalizes the classification of doubly transitive balanced incomplete block designs with λ=1 and doubly transitive one-factorizations of complete graphs. It also provides a classification of all doubly transitive symmetric association schemes.

A Theorem On Divergence In The General Sense For Continued Fractions, Douglas Bowman, James Mclaughlin

Mathematics Faculty Publications

If the odd and even parts of a continued fraction converge to different values, the continued fraction may or may not converge in the general sense. We prove a theorem which settles the question of general convergence for a wide class of such continued fractions. We apply this theorem to two general classes of q continued fraction to show, that if G(q) is one of these continued fractions and |q| > 1, then either G(q) converges or does not converge in the general sense. We also show that if the odd and even parts of the continued fraction K∞n=1an/1 converge to …

On The Divergence Of The Rogers-Ramanujan Continued Fraction On The Unit Circle, Douglas Bowman, James Mclaughlin

Mathematics Faculty Publications

This paper is an intensive study of the convergence of the Rogers-Ramanujan continued fraction. Let the continued fraction expansion of any irrational number t ∈ (0, 1) be denoted by [0, a1(t), a2(t), · · · ] and let the i-th convergent of this continued fraction expansion be denoted by ci(t)/di(t). Let S = {t ∈ (0, 1) : ai+1(t) ≥ φ di(t) infinitely often}, where φ = (√ 5 + 1)/2. Let YS = {exp(2πit) : t ∈ S}. It is shown that if y ∈ YS then the Rogers-Ramanujan continued fraction, R(y), diverges at y. S is an …