Discrete Mathematics and Combinatorics Commons^™

A Stirling Encounter With Harmonic Numbers, Arthur T. Benjamin, Gregory O. Preston '01, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Orthogonal Arrays Of Strength Three From Regular 3-Wise Balanced Designs, Charles J. Colbourn, D. L. Kreher, John P. Mcsorley, D. R. Stinson

Articles and Preprints

The construction given in Kreher, J Combin Des 4 (1996) 67 is extended to obtain new infinite families of orthogonal arrays of strength 3. Regular 3-wise balanced designs play a central role in this construction.

Applications Of Graph Theory To Separability, Stephen Young

Mathematical Sciences Technical Reports (MSTR)

Let S be a surface with a triangular tiling T. Let R be a reflection a side of one of the triangles; so that R is an orientation reversing isometry of the surface. Define M = {s in S |S : Rs = s}. We then say that the surface S separates along the reflection R if S-R has two components. This paper considers the applications of graph theoretic methods to determining whether a reflection is separating or not and compares the algorithmic efficiency of these methods to the current known methods.

Enumeration Of Matchings In The Incidence Graphs Of Complete And Complete Bipartite Graphs, Nicholas Pippenger

All HMC Faculty Publications and Research

If G = (V, E) is a graph, the incidence graphI(G) is the graph with vertices I ∪ E and an edge joining v ∈ V and e ∈ E when and only when v is incident with e in G. For G equal to K_n (the complete graph on n vertices) or K_n,n (the complete bipartite graph on n + n vertices), we enumerate the matchings (sets of edges, no two having a vertex in common) in I(G), both exactly (in terms of generating …

A Note On Interpolation In The Generalized Schur Class. I. Applications Of Realization Theory, Daniel Alpay, T. Constantinescu, A. Dijksma, J. Rovnyak, A. Dijksma

Mathematics, Physics, and Computer Science Faculty Articles and Research

Realization theory for operator colligations on Pontryagin spaces is used to study interpolation and factorization in generalized Schur classes. Several criteria are derived which imply that a given function is almost the restriction of a generalized Schur function. The role of realization theory in coefficient problems is also discussed; a solution of an indefinite Carathéodory-Fejér problem is obtained, as well as a result that relates the number of negative (positive) squares of the reproducing kernels associated with the canonical coisometric, isometric, and unitary realizations of a generalized Schur function to the number of negative (positive) eigenvalues of matrices derived from …

Some Extensions Of Loewner's Theory Of Monotone Operator Functions, Daniel Alpay, Vladimir Bolotnikov, A. Dijksma, J. Rovnyak, A. Dijksma

Mathematics, Physics, and Computer Science Faculty Articles and Research

Several extensions of Loewner’s theory of monotone operator functions are given. These include a theorem on boundary interpolation for matrix-valued functions in the generalized Nevanlinna class. The theory of monotone operator functions is generalized from scalar- to matrix-valued functions of an operator argument. A notion of -monotonicity is introduced and characterized in terms of classical Nevanlinna functions with removable singularities on a real interval. Corresponding results for Stieltjes functions are presented.

On Minimal Regular Graphs With Given Constraintsm, Che Sheng Gan

Student Works (2000-2009)

A classical question in graph theory has been the search of cages. The problem of determining the smallest (r,g)-cage is unsolved for most pairs of (r,g) and is extremely hard in the general case. Finding the crossing number of a graph is another challenging problem in graph theory. The crossing numbers of very few classes of graphs arc known. In this thesis, we would like to (a) investigate those smallest regular graphs with given girths and having small crossing numbers. In particular, we investigate those smallest regular graphs with given girths and crossing number c, for c ∈ {0, 1, …

Enumeration Of Equicolourable Trees, Nicholas Pippenger

All HMC Faculty Publications and Research

A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by …

Nested Balanced Incomplete Block Designs, J. P. Morgan, D. A. Preece, D. H. Rees

Mathematics & Statistics Faculty Publications

If the blocks of a balanced incomplete block design (BIBD) with v treatments and with parameters (v; b₁;r;k₁) are each partitioned into sub-blocks of size k₂, and the b₂ =b₁k₁=k2 sub-blocks themselves constitute a BIBD with parameters (v; b₂;r;k₂), then the system of blocks, sub-blocks and treatments is, by de4nition, a nested BIBD (NBIBD). Whist tournaments are special types of NBIBD with k₁ =2k₂= 4. Although NBIBDs were introduced in the statistical literature in 1967 and have subsequently received occasional attention there, …

The Multiplicities Of A Dual-Thin Q-Polynomial Association Scheme, Bruce E. Sagen, John S. Caughman Iv

Mathematics and Statistics Faculty Publications and Presentations

Let Y=(X,{Ri}1≤i≤D) denote a symmetric association scheme, and assume that Y is Q-polynomial with respect to an ordering E₀,...,E_D of the primitive idempotents. Bannai and Ito conjectured that the associated sequence of multiplicities mi (0≤i≤D) of Yis unimodal. Talking to Terwilliger, Stanton made the related conjecture that mi≤mi+1 and mi≤mD−i for i<D/2. We prove that if Y is dual-thin in the sense of Terwilliger, then the …

Wholes And Parts In General Systems Methodology, Martin Zwick

Complex Systems Faculty Publications and Presentations

Reconstructability analysis (RA) decomposes wholes, namely data in the form either of set-theoretic relations or multivariate probability distributions, into parts, namely relations or distributions involving subsets of variables. Data is modeled and compressed by variablebased decomposition, by more general state-based decomposition, or by the use of latent variables. Models, which specify the interdependencies among the variables, are selected to minimize error and complexity.

Phased Tilings And Generalized Fibonacci Identities, Arthur T. Benjamin, Jennifer J. Quinn, Francis E. Su

All HMC Faculty Publications and Research

Fibonacci numbers arise in the solution of many combinatorial problems. They count the number of binary sequences with no consecutive zeros, the number of sequences of 1's and 2's which sum to a given number, and the number of independent sets of a path graph. Similar interpretations exist for Lucas numbers. Using these interpretations, it is possible to provide combinatorial proofs that shed light on many interesting Fibonacci and Lucas identities (see [1], [3]). In this paper we extend the combinatorial approach to understand relationships among generalized Fibonacci numbers.

Given G₀ and G₁ a generalized Fibonacci sequence G …

Random Approaches To Fibonacci Identities, Arthur T. Benjamin, Gregory M. Levin, Karl Mahlburg '01, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Counting On Continued Fractions, Arthur T. Benjamin, Francis E. Su, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

A Group Theoretic Tabu Search Approach To The Traveling Salesman Problem, Shane N. Hall

Theses and Dissertations

The traveling salesman problem (TSP) is a combinatorial optimization problem that is mathematically modeled as a binary integer program. The TSP is a very important problem for the operations research academician and practitioner. This research demonstrates a Group Theoretic Tabu Search (GTTS) Java algorithm for the TSP. The tabu search metaheuristic continuously finds near-optimal solutions to the TSP under various different implementations. Algebraic group theory offers a more formal mathematical setting to study the TSP providing a theoretical foundation for describing tabu search. Specifically, this thesis uses the Symmetric Group on n letters, S(n), which is the set of all …

Directed Graphs, Stephen B. Maurer , '67

Mathematics & Statistics Faculty Works

No abstract provided.

Recounting Fibonacci And Lucas Identities, Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Peak-To-Mean Power Control In Ofdm, Golay Complementary Sequences, And Reed–Muller Codes, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

We present a range of coding schemes for OFDM transmission using binary, quaternary, octary, and higher order modulation that give high code rates for moderate numbers of carriers. These schemes have tightly bounded peak-to-mean envelope power ratio (PMEPR) and simultaneously have good error correction capability. The key theoretical result is a previously unrecognized connection between Golay complementary sequences and second-order Reed–Muller codes over alphabets ℤ_2^h. We obtain additional flexibility in trading off code rate, PMEPR, and error correction capability by partitioning the second-order Reed–Muller code into cosets such that codewords with large values of PMEPR are isolated. …

A Short Proof That ‘Proper = Unit’, Kenneth P. Bogart, Douglas B. West

Dartmouth Scholarship

A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.

Automorphic Subsets Of The N-Dimensional Cube Are Translations Of Cwatsets, Matthew Lepinski

Mathematical Sciences Technical Reports (MSTR)

It is known that automorphic subsets are generalizations of cwatsets. In this paper we show that an automorphic subset is the translation of some cwatset, and therefore that each automorphic subset is internally isomorphic to a cwatset.

Unevening The Odds Of "Even Up", Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Single-Change Circular Covering Designs, John P. Mcsorley

Articles and Preprints

A single-change circular covering design (scccd) based on the set [v] = {1, . . . ,v} with block size k is an ordered collection of b blocks, B = {B₁, . . . ,B_b}, each B_i ⊂ [v], which obey: (1) each block differs from the previous block by a single element, as does the last from the first, and, (2) every pair of [v] is covered by some Bi. The object is to minimize b for a fixed v and k. …

Some Recent Developments In Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

There are five known parameter families for (v, k, λ, n)- difference sets satisfying gcd(v, n)>1: the Hadamard, McFarland, Spence, Davis-Jedwab, and Chen families. The authors recently gave a recursive unifying construction for difference sets from the first four families which relies on relative difference sets. We give an overview of this construction and show that, by modifying it to use divisible difference sets in place of relative difference sets, the recent difference set discoveries of Chen can be brought within the unifying framework. We also demonstrate the recursive use of an auxiliary construction for …

A Unified Approach To Difference Sets With Gcd(V, N) > 1, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

The five known families of difference sets whose parameters (v, k, λ; n) satisfy the condition gcd(v,n) > 1 are the McFarland, Spence, Davis-Jedwab, Hadamard and Chen families. We survey recent work which uses recursive techniques to unify these difference set families, placing particular emphasis on examples. This unified approach has also proved useful for studying semi-regular relative difference sets and for constructing new symmetric designs.

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

New Semiregular Divisible Difference Sets, James A. Davis

Department of Math & Statistics Faculty Publications

We modify and generalize the construction by McFarland (1973) in two different ways to construct new semiregular divisible difference sets (DDSs) with λ₁≠0. The parameters of the DDS fall into a family of parameters found in Jungnickel (1982), where his construction is for divisible designs. The final section uses the idea of a K-matrix to find DDSs with a nonelementary abelian forbidden subgroup.

Counting Structures In The Möbius Ladder, John P. Mcsorley

Articles and Preprints

The Möbius ladder, M_n, is a simple cubic graph on 2n vertices. We present a technique which enables us to count exactly many different structures of M_n, and somewhat unifies counting in M_n. We also provide new combinatorial interpretations of some sequences, and ask some questions concerning extremal properties of cubic graphs.

Proper And Unit Bitolerance Orders And Graphs, Kenneth P. Bogart, Garth Isaak

Dartmouth Scholarship

We say any order ≺ is a tolerance order on a set of vertices if we may assign to each vertex x an interval I_x of real numbers and a real number t_x called a tolerance in such a way that x ≺ y if and only if the overlap of I_x and I_y is less than the minimum of t_x and t_y and the center of I_x is less than the center of I_y. An order is a bitolerance order if and only if there are intervals I_x and …

Hadamard Difference Sets In Nonabelian 2-Groups With High Exponent, James A. Davis, Joel E. Iiams

Department of Math & Statistics Faculty Publications

Nontrivial difference sets in groups of order a power of 2 are part of the family of difference sets called Hadamard difference sets. In the abelian case, a group of order 2^{2t + 2} has a difference set if and only if the exponent of the group is less than or equal to 2^{t + 2}. In a previous work (R. A. Liebler and K. W. Smith, in “Coding Theory, Design Theory, Group Theory: Proc. of the Marshall Hall Conf.,” Wiley, New York, 1992), the authors constructed a difference set in a nonabelian group of order …

A Unifying Construction For Difference Sets, James A. Davis, Jonathan Jedwab

Department of Math & Statistics Faculty Publications

We present a recursive construction for difference sets which unifies the Hadamard, McFarland, and Spence parameter families and deals with all abelian groups known to contain such difference sets. The construction yields a new family of difference sets with parameters (v, k, λ,n)=(2^2d+4(2^2d+2−1)/3, 2^2d+1(2^2d+3+1)/3, 2^2d+1(2^2d+1+1)/3, 2^4d+2) for d⩾0. The construction establishes that a McFarland difference set exists in an abelian group of order 2^{2 …}