Discrete Mathematics and Combinatorics Commons^™

Difference Sets In Abelian 2-Groups, James A. Davis

Department of Math & Statistics Faculty Publications

Examples of difference sets are given for large classes of abelian groups of order 2^{2d + 2}. This fills in the gap of knowledge between Turyn's exponent condition and Dillon's rank condition. Specifically, it is shown thatℤ/(2^d)×ℤ/(2^d+2) andℤ/(2^d+1)×Z/(2^d+1) both admit difference sets, and these have many implications.

Advice For Undergraduates On Special Aspects Of Writing Mathematics, Stephen B. Maurer

Mathematics & Statistics Faculty Works

There are several guides to good mathematical writing for professionals, but few for undergraduates. Yet undergraduates who write mathematics papers need special guidance. For instance, professionals may need help writing clear definitions, but at least they know why explicit definitions are needed and know the basic format. In general, mathematics has many special formats that are not mere technical conventions but instead serve important purposes. Often students are not conscious of these conventions, and they rarely know their purposes. This paper contains a guide for students written in light of these observations.

The Expected Capacity Of Concentrators, Nicholas Pippenger

All HMC Faculty Publications and Research

The expected capacity of a class of sparse concentrators called modular concentrators is determined. In these concentrators, each input is connected to exactly two outputs, each output is connected to exactly three inputs, and the girth (the length of the shortest cycle in the connexion graph) is large. Two definitions of expected capacity are considered. For the first (which is due to Masson and Morris), it is assumed that a batch of customers arrive at a random set of inputs and that a maximum matching of these customers to servers at the outputs is found. The number of unsatisfied requests …

Some Remarks On Reproducing Kernel Krein Spaces, Daniel Alpay

Mathematics, Physics, and Computer Science Faculty Articles and Research

The one-to-one correspondence between positive functions and reproducing kernel Hilbert spaces was extended by L. Schwartz to a (onto, but not one-to-one) correspondence between difference of positive functions and reproducing kernel Krein spaces. After discussing this result, we prove that matrix value function K(z,ω) symmetric and jointly analytic in z and ω in a neighborhood of the origin is the reproducing kernel of a reproducing kernel Krein space. We conclude with an example showing that such a function can be the reproducing kernel of two different Krein spaces.

A Note On Nonabelian (64, 28, 12) Difference Sets, James A. Davis

Department of Math & Statistics Faculty Publications

The existence of difference sets in abelian 2-groups is a recently settled problem [5]; this note extends the abelian constructs of difference sets to nonabelian groups of order 64.

A Note On Intersection Numbers Of Difference Sets, K. T. Arasu, James A. Davis, Dieter Jungnickel, Alexander Pott

Department of Math & Statistics Faculty Publications

We present a condition on the intersection numbers of difference sets which follows from a result of Jungnickel and Pott [3]. We apply this condition to rule out several putative (non-abelian) difference sets and to correct erroneous proofs of Lander [4] for the nonexistence of (352, 27, 2)- and (122, 37, 12)-difference sets.

Random Sequential Absorption On Graphs, Nicholas Pippenger

All HMC Faculty Publications and Research

This paper analyzes a process whereby the vertices of a graph are considered in a random sequence,and each considered vertex is “occupied” unless it or an adjacent vertex has previously been occupied. The process continues until no more vertices can be occupied, at which point the “jamming limit” has been reached. The case in which the graph is regular (so that every vertex has degree $d\geqq 2$ and has “few short cycles” is treated. In particular, the results apply to infinite regular trees, to finite graphs obtained from them by forming quotient graphs, and to random regular graphs.

It is …

Dilatations Des Commutants D'Opérateurs Pour Des Espaces De Krein De Fonctions Analytiques, Daniel Alpay

Mathematics, Physics, and Computer Science Faculty Articles and Research

Let K1 and K2 be two Krein spaces of functions analytic in the unit disk and invariant for the left shift operator R0(R0f(z)=(f(z)−f(0))/z), and let A be a linear continuous operator from K1 into K2 whose adjoint commutes with R0. We study dilations of A which preserve this commuting property and such that the Hermitian forms defined by I−AA∗ and I−BB∗ have the same number of negative squares. We thus obtain a version of the commutant lifting theorem in the framework of Krein spaces of analytic functions. To prove this result we suppose that the graph of the operator A∗, …

Generalized Distance In Graphs, Garry L. Johns

Dissertations

No abstract provided.

Review Of “Constructive Combinatorics” By D. Stanton And D. White, Stephen B. Maurer

Mathematics & Statistics Faculty Works

No abstract provided.

Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger

All HMC Faculty Publications and Research

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n^{1 + 1/k} ( log n )^{1 - 1/k} ).

Keane Leads Us Olympiad Team To 1st Place Tie With Ussr, Stephen B. Maurer

Mathematics & Statistics Faculty Works

No abstract provided.

Camc Examines America, Stephen B. Maurer

Mathematics & Statistics Faculty Works

No abstract provided.

U.S. Team Places Second In International Olympiad, Stephen B. Maurer

Mathematics & Statistics Faculty Works

No abstract provided.

Some Graph-Colouring Theorems With Applications To Generalized Connection Networks, David G. Kirkpatrick, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

With the aid of a new graph-colouring theorem, we give a simple explicit construction for generalized n-connectors with 2k - 1 stages and O( n^{1 + 1 / k} (log n )^{( k - 1)/ 2} ) edges. This is asymptotically the best explicit construction known for generalized connectors.

The Algorithmic Way Of Life Is Best, Stephen B. Maurer , '67

Mathematics & Statistics Faculty Works

No abstract provided.

Review Of "The Future Of College Mathematics" Edited By A. Ralston And G. S. Young, Stephen B. Maurer , '67

Mathematics & Statistics Faculty Works

No abstract provided.

Difference Equations, Isoperimetric Inequality And Transience Of Certain Random Walks, Jozef Dodziuk

Publications and Research

No abstract provided.

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

Derivation And Test Of Predictions Of A Discrete Latent State Model For Signed Number Addition Test Performance, Kentaro Yamamoto

Dissertations and Theses

This study is an investigation of the performance of a discrete latent state model devised by Paulson (1982) to account for signed-number arithmetic test data gathered by Birenbaum and Tatsuoka (1980). One hundred twenty nine students took a test which consists of sixteen item types with four parallel arithmetic items of each type. The present study utilizes the five addition item types of four items each; hence, there are four parallel subtests. Responses to the addition items can be analyzed in terms of two components: the sign component (is the sign correct?), and the absolute value component (is the size …

An Interview With Albert W. Tucker, Stephen B. Maurer, A. W. Tucker

Mathematics & Statistics Faculty Works

The mathematical career of Albert W. Tucker, Professor Emeritus at Princeton University, spans more than 50 years. Best known today for his work in mathematical programming and the theory of games (e.g., the Kuhn-Tucker theorem, Tucker tableaux, and the Prisoner's Dilemma), he was also in his earlier years prominent in topology. Outstanding teacher, administrator and leader, he has been President of the MAA, Chairman of the Princeton Mathematics Department, and course instructor, thesis advisor or general mentor to scores of active mathematicians. He is also known for his views on mathematics education and the proper interplay between teaching and research. …

Some Unusual Locus Problems, Stephen B. Maurer , '67

Mathematics & Statistics Faculty Works

No abstract provided.

Rearrangeable Networks With Limited Depth, Nicholas Pippenger, Andrew C.-C. Yao

All HMC Faculty Publications and Research

Rearrangeable networks are switching systems capable of establishing simultaneous independent communication paths in accordance with any one-to-one correspondence between their n inputs and n outputs. Classical results show that Ω( n log n ) switches are necessary and that O( n log n ) switches are sufficient for such networks. We are interested in the minimum possible number of switches in rearrangeable networks in which the depth (the length of the longest path from an input to an output) is at most k, where k is fixed as n increases. We show that Ω( n^{1 + 1/k} ) switches …

A Classification Of Certain Graphs With Minimal Imperfection Properties, S. H. Whitesides

Dartmouth Scholarship

The family of (α, ω) graphs are of interest for several reasons. For example, any minimal counter-example to Berge's Strong Perfect Graph Conjecture belongs to this family. This paper accounts for all (4, 3) graphs. One of these is not obtainable by existing techniques for generating (α + 1, ω) graphs from (α, ω) graphs.

The King Chicken Theorems, Stephen B. Maurer

Mathematics & Statistics Faculty Works

No abstract provided.

A New Lower Bound For The Number Of Switches In Rearrangeable Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

For the commonest model of rearrangeable networks with $n$ inputs and $n$ outputs, it is shown that such a network must contain at least $6n \log _6 n + O( n )$ switches. Similar lower bounds for other models are also presented.

A Note On The Degree Of Approximation With An Optimal, Discrete Polynomial, J. J. Swetits, B. Wood

Mathematics & Statistics Faculty Publications

A saturation theorem and an asymptotic theorem are proved for an optimal, discrete, positive algebraic polynomial operator. The operator is based on the Gauss-Legendre quadrature formula.

Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder

All HMC Faculty Publications and Research

The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.

An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.

Approximation By Discrete Operators, J. J. Swetits, B. Wood

Mathematics & Statistics Faculty Publications

A discrete, positive, weighted algebraic polynomial operator which is based on Gaussian quadrature is constructed. The operator is shown to satisfy the Jackson estimate and an optimal version is obtained.