Discrete Mathematics and Combinatorics Commons^™

An Alternate Approach To Alternating Sums: A Method To Die For, Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu

Computer Science: Faculty Publications

A multi-graph G on n vertices is (k,ℓ)-sparse if every subset of n^′⩽n vertices spans at most kn^′-ℓ edges. G is tight if, in addition, it has exactly kn-ℓ edges. For integer valuesk and ℓ∈[0,2k), we characterize the (k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)-pebble games. [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.

The 99th Fibonacci Identity, Arthur T. Benjamin, Alex K. Eustis '06, Sean S. Plott '08

All HMC Faculty Publications and Research

We provide elementary combinatorial proofs of several Fibonacci and Lucas number identities left open in the book Proofs That Really Count [1], and generalize these to Gibonacci sequences G_n that satisfy the Fibonacci recurrence, but with arbitrary real initial conditions. We offer several new identities as well.

[1] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions, 27, Mathematical Association of America, Washington, DC, 2003

A Combinatorial Approach To Fibonomial Coefficients, Arthur T. Benjamin, Sean S. Plott '08

All HMC Faculty Publications and Research

A combinatorial argument is used to explain the integrality of Fibonomial coefficients and their generalizations. The numerator of the Fibonomial coeffcient counts tilings of staggered lengths, which can be decomposed into a sum of integers, such that each integer is a multiple of the denominator of the Fibonomial coeffcient. By colorizing this argument, we can extend this result from Fibonacci numbers to arbitrary Lucas sequences.

Paint It Black -- A Combinatorial Yawp, Arthur T. Benjamin, Jennifer J. Quinn, James A. Sellers, Mark A. Shattuck

All HMC Faculty Publications and Research

No abstract provided in this paper.

Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince

Faculty Publications & Research

Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that …

Distribution Of The Number Of Encryptions In Revocation Schemes For Stateless Receivers, Christopher Eagle, Zhicheng Gao, Mohamed Omar, Daniel Panario, Bruce Richmond

All HMC Faculty Publications and Research

We study the number of encryptions necessary to revoke a set of users in the complete subtree scheme (CST) and the subset-difference scheme (SD). These are well-known tree based broadcast encryption schemes. Park and Blake in: Journal of Discrete Algorithms, vol. 4, 2006, pp. 215--238, give the mean number of encryptions for these schemes. We continue their analysis and show that the limiting distribution of the number of encryptions for these schemes is normal. This implies that the mean numbers of Park and Blake are good estimates for the number of necessary encryptions used by these schemes.

On KS,T-Minors In Graphs With Given Average Degree, A. V. Kostochka, N. Prince

Faculty Publications & Research

Let D(H) be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on D(H) for almost all graphs H and proved that for 'balanced' H random graphs provide extremal examples and determine the extremal function. Examples of 'unbalanced graphs' are complete bipartite graphs K_s,t for a fixed s and large t. Myers proved upper bounds on D(K_s,t ) and made a conjecture on the order of magnitude of D(K_s,t ) for a fixed s and …

N- Linear Algebra Of Type I And Its Applications, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

With the advent of computers one needs algebraic structures that can simultaneously work with bulk data. One such algebraic structure namely n-linear algebras of type I are introduced in this book and its applications to n-Markov chains and n-Leontief models are given. These structures can be thought of as the generalization of bilinear algebras and bivector spaces. Several interesting n-linear algebra properties are proved. This book has four chapters. The first chapter just introduces n-group which is essential for the definition of nvector spaces and n-linear algebras of type I. Chapter two gives the notion of n-vector spaces and several …

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.

A Characterization Of Schur Multipliers Between Character-Automorphic Hardy Spaces, Daniel Alpay, M. Mboup

Mathematics, Physics, and Computer Science Faculty Articles and Research

We give a new characterization of character-automorphic Hardy spaces of order 2 and of their contractive multipliers in terms of de Branges Rovnyak spaces. Keys tools in our arguments are analytic extension and a factorization result for matrix-valued analytic functions due to Leech.

G-Perfect Nonlinear Functions, James A. Davis, Laurent Poinsot

Department of Math & Statistics Faculty Publications

Perfect nonlinear functions are used to construct DES-like cryptosystems that are resistant to differential attacks. We present generalized DES-like cryptosystems where the XOR operation is replaced by a general group action. The new cryptosystems, when combined with G-perfect nonlinear functions (similar to classical perfect nonlinear functions with one XOR replaced by a general group action), allow us to construct systems resistant to modified differential attacks. The more general setting enables robust cryptosystems with parameters that would not be possible in the classical setting. We construct several examples of G-perfect nonlinear functions, both Z₂ -valued and Z^{a …}

Intrinsic Linking And Knotting Are Arbitrarily Complex, Erica Flapan, Blake Mellor, Ramin Naimi

Mathematics, Statistics and Data Science Faculty Works

We show that, given any n and α, every embedding of any sufficiently large complete graph in R³ contains an oriented link with components Q₁, ..., Q_n such that for every i≠j, $|\lk(Q_i,Q_j)|\geq\alpha$ and |a₂(Qi)|≥α, where a₂(Q_i) denotes the second coefficient of the Conway polynomial of Q_i.

Weight Systems For Milnor Invariants, Blake Mellor

Mathematics, Statistics and Data Science Faculty Works

We use Polyak's skein relation to give a new proof that Milnor's string link homotopy invariants are finite type invariants, and to develop a recursive relation for their associated weight systems. We show that the obstruction to the triviality of these weight systems is the presence of a certain kind of spanning tree in the intersection graph of a chord diagram.

Rational Functions Associated To The White Noise Space And Related Topics, Daniel Alpay, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

Motivated by the hyper-holomorphic case we introduce and study rational functions in the setting of Hida’s white noise space. The Fueter polynomials are replaced by a basis computed in terms of the Hermite functions, and the Cauchy-Kovalevskaya product is replaced by the Wick product.

On The Reproducing Kernel Hilbert Spaces Associated With The Fractional And Bi-Fractional Brownian Motions, Daniel Alpay, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

We present decompositions of various positive kernels as integrals or sums of positive kernels. Within this framework we study the reproducing kernel Hilbert spaces associated with the fractional and bi-fractional Brownian motions. As a tool, we define a new function of two complex variables, which is a natural generalization of the classical Gamma function for the setting we consider.

Decomposition, Packings And Coverings Of Complete Digraphs With A Transitive-Triple And A Pendant Arc., Janice Gail Lewenczuk

Electronic Theses and Dissertations

In the study of design theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K₃∪{e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings and coverings of the complete digraph with each of the six transitive triples with a pendant arc.

Packings And Coverings Of Various Complete Digraphs With The Orientations Of A 4-Cycle., Melody Elaine Cooper

Electronic Theses and Dissertations

There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs D_v, packing and covering complete bipartite digraphs, D_m,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C₄, X, and Y.

Chromatic Number Of The Alphabet Overlap Graph, G(2, K , K-2)., Jerry Brent Farley

Electronic Theses and Dissertations

A graph G(a, k, t) is called an alphabet overlap graph where a, k, and t are positive integers such that 0 ≤ t < k and the vertex set V of G is defined as, V = {v : v = (v₁v₂...v_k); v_i ∊ {1, 2, ..., a}, (1 ≤ i ≤ k)}. That is, each vertex, v, is a word of length k over an alphabet of size a. There exists an edge between two vertices u, …

Recounting Determinants For A Class Of Hessenberg Matrices, Arthur T. Benjamin, Mark A. Shattuck

All HMC Faculty Publications and Research

We provide combinatorial interpretations for determinants which are Fibonacci numbers of several recently introduced Hessenberg matrices. Our arguments make use of the basic definition of the determinant as a signed sum over the symmetric group.

Solution To Problem 1751, A Combinatorial Identity, Arthur T. Benjamin, Andrew Carman '09

All HMC Faculty Publications and Research

A combinatorial proof to Iliya Bluskov's proposed Problem 1751.

The Discrete Logarithm Problem And Ternary Functional Graphs, Max F. Brugger, Christina A. Frederick

Mathematical Sciences Technical Reports (MSTR)

Encryption is essential to the security of transactions and communications, but the algorithms on which they rely might not be as secure as we all assume. In this paper, we investigate the randomness of the discrete exponentiation function used frequently in encryption. We show how we used exponential generating functions to gain theoretical data for mapping statistics in ternary functional graphs. Then, we compare mapping statistics of discrete exponentiation functional graphs, for a range of primes, with mapping statistics of the respective ternary functional graphs.

Decompositions, Packings, And Coverings Of Complete Directed Gaphs With A 3-Circuit And A Pendent Arc., Chrys Gwellem

Electronic Theses and Dissertations

In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K₃ ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings, and coverings of the complete digraph with the two 3-circuit with a pendant arc orientations.

Tricyclic Steiner Triple Systems With 1-Rotational Subsystems., Quan Duc Tran

Electronic Theses and Dissertations

A Steiner triple system of order v, denoted STS(v), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic STS(v) when one of the cycles is of length one. In this case, the STS(v) will contain a subsystem which admits an automorphism consisting of a fixed point and a single cycle. The subsystem is said to be 1-rotational.

Characterizing Sparse Graphs By Map Decompositions, Ruth Haas, Audrey Lee, Ileana Streinu, Louis Theran

Mathematics Sciences: Faculty Publications

A map is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into k edge-disjoint maps after: (1) the addition of any ℓ edges; (2) the addition of some ℓ edges. These graphs are identified with classes of sparse graphs; the results are also given in matroidal terms.

Proof Of The Barker Array Conjecture, James A. Davis, Jonathan Jedwab, Ken W. Smith

Department of Math & Statistics Faculty Publications

Using only elementary methods, we prove Alquaddoomi and Scholtz’s conjecture of 1989, that no s × t Barker array having s, t > 1 exists except when s = t = 2.

Nonlinear Dynamics In Combinatorial Games: Renormalizing Chomp, Eric J. Friedman, Adam S. Landsberg

WM Keck Science Faculty Papers

We develop a new approach to combinatorial games that reveals connections between such games and some of the central ideas of nonlinear dynamics: scaling behaviors, complex dynamics and chaos, universality, and aggregation processes. We take as our model system the combinatorial game Chomp, which is one of the simplest in a class of "unsolved" combinatorial games that includes Chess, Checkers, and Go. We discover that the game possesses an underlying geometric structure that "grows" (reminiscent of crystal growth), and show how this growth can be analyzed using a renormalization procedure adapted from physics. In effect, this methodology allows one to …

Closed-Neighborhood Anti-Sperner Graphs, John P. Mcsorley, Alison Marr, Thomas D. Porter, Walter D. Wallis

Articles and Preprints

For a simple graph G let N_G[u] denote the closed-neighborhood of vertex u ∈ V (G). Then G is closed-neighborhood anti-Sperner (CNAS) if for every u there is a v ∈ V (G)\{u} with N_G [u] ⊆ N_G [v] and a graph H is closed-neighborhood distinct (CND) if every closed-neighborhood is distinct, i.e., if N_H[u] ≠ N_H[v] when u ≠ v, for all u and v ∈ V (H).

In this paper we …

Alliance Partitions In Graphs., Jason Lachniet

Electronic Theses and Dissertations

For a graph G=(V,E), a nonempty subset S contained in V is called a defensive alliance if for each v in S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. If there are strictly more vertices from the closed neighborhood of v in S as in V-S, then S is a strong defensive alliance. A (strong) defensive alliance is called global if it is also a dominating set of G. The alliance partition number (respectively, strong …