Mathematics Commons^™

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.

Uniqueness Of Positive Solutions For A Class Of Elliptic Boundary Value Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

Uniqueness of non-negative solutions conjectured in an earlier paper by Shivaji is proved. Our methods are independent of those of that paper, where the problem was considered only in a ball. Further, our results apply to a wider class of nonlinearities.

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.

The Changing Concept Of Change: The Derivative From Fermat To Weierstrass, Judith V. Grabiner

Pitzer Faculty Publications and Research

Historically speaking, there were four steps in the development of today's concept of the derivative, which I list here in chronological order. The derivative was first used; it was then discovered; it was then explored and developed; and it was finally defined. That is, examples of what we now recognize as derivatives first were used on an ad hoc basis in solving particular problems; then the general concept lying behind them these uses was identified (as part of the invention of calculus); then many properties of the derivative were explained and developed in applications both to …

Who Gave You The Epsilon? The Origins Of Cauchy's Rigorous Calculus, Judith V. Grabiner

Pitzer Faculty Publications and Research

This paper recounts the history of how calculus came to get a rigorous basis in terms of the algebra of inequalities. The result is a brief history of the 150 years from Newton and Leibniz to Cauchy that produced the foundations of analysis.

On Determinism Versus Non-Determinism And Related Problems, Wolfgang J. Paul, Nicholas Pippenger, Endre Szemeredi, William T. Trotter

All HMC Faculty Publications and Research

We show that, for multi-tape Turing machines, non-deterministic linear time is more deterministic Turing machines (that receive their input on their work tape) require time Q(n2) to powerful than deterministic linear time. We also recognize non-palindromes of length n (it is easy to discuss the prospects for extending this result to see that time O(n log n) is. sufficient for a more general Turing machines. non-deterministic machine). 1. Introduction

Reduction Methods Via Minimax, Alfonso Castro

All HMC Faculty Publications and Research

Lecture notes in mathematics originally published in Differential Equations book series.

On Multiple Solutions Of Nonlinear Elliptic Equations With Odd Nonlinearities, Alfonso Castro, J. V. A. Gonçalves

All HMC Faculty Publications and Research

In this paper we stablish results on multiplicity of solutions for the boundary value problem where a e IR and f: R - IR is an odd continuous function.

Sums Of Z-Ideals And Semiprime Ideals, Melvin Henriksen, Frank A. Smith

All HMC Faculty Publications and Research

If B is a ring (or module), and K is an ideal (or submodule) of B, let B(K) = {(a,b) є B x B:a-b є K}. The relationship between ideals (or submodules) of B and those of B(K) is examined carefully, and this construction is used to find a lattice-ordered subring of the ring C(R) of all continuous real-valued functions on the real line R with two z-ideals whose sum is not even semiprime.

Results On Periodic Solutions Of Parabolic Equations Suggested By Elliptic Theory, Alfonso Castro, A. C. Lazer

All HMC Faculty Publications and Research

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 …

Some Properties Of Positive Derivations On F-Rings, Melvin Henriksen, Frank A. Smith

All HMC Faculty Publications and Research

Throughout A denotes an f-ring; that is, a lattice-ordered ring that is a subdirect union of totally ordered rings. We let D(A) denote the set of derivations D: A --> A such that a ≥ 0 implies Da ≥ 0, and we call such derivations positive. In [CDK], P. Coleville, G. Davis, and K. Keimel initiated a study of positive derivations on f-rings. Their main results are (i) D ε D(A) and A archimedean imply D = 0, and (ii) if A has an identity element 1 and a is the supremum of a set …

Algebraic Complexity Theory, Nicholas Pippenger

All HMC Faculty Publications and Research

Algebraic complexity theory, the study of the minimum number of operations sufficient to perform algebraic computations, is surveyed with emphasis on the general theory of bilinear forms and two of its applications: polynomial multiplication and matrix multiplication. Though by no means exhausting algebraic complexity theory, these topics illustrate well its development and its methods, and provide examples of its most striking successes.

Bounds On The Performance Of Protocols For A Multiple-Access Broadcast Channel, Nicholas Pippenger

All HMC Faculty Publications and Research

A general model is presented for synchronous protocols that resolve conflicts among message transmissions to a multiple-access broadcast channel. An information-theoretic method is used now to show that if only finitely many types of conflicts can be distinguished by the protocol, utilization of the channel at rates approaching capacity is impossible. A random-coding argument is used to show that if the number of conflicting transmissions can be determined (which requires distinguishing infinitely many types of conflicts) then utilization of the channel at rates arbitrarily close to capacity can be achieved.

On Periodic Solutions Of Weakly Coupled Systems Of Differential Equations, Alfonso Castro, A. C. Lazer

All HMC Faculty Publications and Research

No abstract provided.

Existence And Uniqueness For A Variational Hyperbolic System Without Resonance, Peter W. Bates, Alfonso Castro

All HMC Faculty Publications and Research

In this paper, we study the existence of weak solutions of the problem

□u + ∇G(u) = f(t,x) ; (t,x) є Ω ≡ (0,π)x(0,π)

u(t,x) = 0 ; (t,x) є ∂Ω

where □ is the wave operator ∂²/∂t² - ∂²/∂x², G: Rⁿ→R is a function of class C² such that ∇G(0) = 0 and f:Ώ→R^n is a continuous function having first derivative with respect to t in (L₂,(Ω))ⁿ and satisfying

f(0,x) = f(π,x) = 0

for all x є [0,π].

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.

Závisí Matematická Pravda Od Času?, Judith V. Grabiner

Pitzer Faculty Publications and Research

This is a Slovak translation of Judith Grabiner's "Is Mathematical Truth Time-Dependent?," published in Volume 81 of American Mathematical Monthly (April 1974).

Two Point Boundary Value Problem With Jumping Nonlinearities, Alfonso Castro

All HMC Faculty Publications and Research

We prove that a certain two point BVP with jumping nonlinearities has a solution. Our result generalizes that of [2]. We use variational methods which permit giving a minimax characterization of the solution. Our proof exposes the similarities between the variational behavior of this problem and that of other semilinear problems with noninvertible linear part (see [5]).

On The Evaluation Of Powers And Monomials, Nicholas Pippenger

All HMC Faculty Publications and Research

Let $y_1 , \cdots ,y_p $ be monomials over the indeterminates $x_1 , \cdots ,x_q $. For every $y = (y_1 , \cdots ,y_p )$ there is some minimum number $L(y)$ of multiplications sufficient to compute $y_1 , \cdots ,y_p $ from $x_1 , \cdots ,x_q $ and the identity 1. Let $L(p,q,N)$ denote the maximum of $L(y)$ over all $y$ for which the exponent of any indeterminate in any monomial is at most $N$. We show that if $p = (N + 1^{o(q)} )$ and $q = (N + 1^{o(p)} )$, then $L(p,q,N) = \min \{ p,q\} \log N …

Critical Point Theory And The Number Of Solutions Of A Nonlinear Dirichlet Problem, Alfonso Castro, A. C. Lazer

All HMC Faculty Publications and Research

No abstract provided.

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.

A Semilinear Dirichlet Problem, Alfonso Castro

All HMC Faculty Publications and Research

Let Ω be a bounded region in R^n. In this note we discuss the existence of weak solutions (see [4, Section 2]) of the Dirichlet problem:

Δu(x) + g(x, u(x)) + f(x, u(x), ∇u(x)) = 0 ; x є Ω

u(x) = 0 ; x є ∂Ω

where Δ is the Laplacian operator, g : Ω x R → R and f : Ω x Rⁿ⁺¹ → R are functions satisfying the Caratheodory condition (see [2, Section 3]), and ∇ is the gradient operator.

On The Application Of Coding Theory To Hashing, Nicholas Pippenger

All HMC Faculty Publications and Research

Quick proofs are given for the characterization (due to Schay, Raver, Hanan, and Palermo) of the collision distance of a linear hashing function and for a dual function (called the restriction distance), which relates to the accessibility of addresses by sets of keys and the uniform distribution of sets of keys over addresses.

A Summary Of Results On Order-Cauchy Completions Of Rings And Vector Lattices Of Continuous Functions, Melvin Henriksen

All HMC Faculty Publications and Research

This paper is a summary of joint research by F. Dashiell, A. Hager and the present author. Proofs are largely omitted. A complete version will appear in the Canadian Journal of Mathematics. It is devoted to a study of sequential order-Cauchy convergence and the associated completion in vector lattices of continuous functions. Such a completion for lattices C(X) is related to certain topological properties of the space X and to ring properties of C(X). The appropriate topological condition on the space X equivalent to this type of completeness for the lattice C(X) was first identified for compact spaces X in …

Hammerstein Integral Equations With Indefinite Kernel, Alfonso Castro

All HMC Faculty Publications and Research

This paper deals with the problem of finding solutions of the Hammerstein integral equation. It is shown that this problem can be reduced to the study of the critical points of certain functional defined on L₂(Ω). Existence of a solution of the Hammersteln integral equation is proved. Some other related results of interest are obtained.

Generalized Connectors, Nicholas Pippenger

All HMC Faculty Publications and Research

An $n$-connector is an acyclic directed graph having $n$ inputs and $n$ outputs and satisfying the following condition: given any one-to-one correspondence between inputs and distinct outputs, there exists a set of vertex-disjoint paths that join each input to the corresponding output. It is known that the minimum possible number of edges in an $n$-connector lies between lower and upper bounds that are asymptotic to $3n\log _3 n$ and $6n\log _3 n$ respectively. A generalized $n$-connector satisfies the following stronger condition: given any one-to-many correspondence between inputs and disjoint sets of outputs, there exists a set of vertex-disjoint trees that …

Applying Mathematics Without A License, Melvin Henriksen

All HMC Faculty Publications and Research

A recent educational experience made me realize the extent to which the mathematical community has become fragmented and how this has served to inhibit communication both with others and ourselves.

An Algebraic Characterization Of The Freudenthal Compactification For A Class Of Rimcompact Spaces, Melvin Henriksen

All HMC Faculty Publications and Research

Throughout C(X) will denote the ring of all continuous real-valued functions on a Tychonoff space X, and C*(X) will denote the subring of bounded elements of C(X). The real line is denoted by R, and N denotes the (discrete) subspace of positive integers. A subset S of X such that the map f → f|_s is an epimorphism of C(X) (resp. C*(X)) is said to be C-embedded (resp. C*-embedded) in X. As is well-known, every f Є C*(X) has a unique continuous extension βf over its Stone-Čech compactification βX [GJ, Chapter 6]. That is, X is …

Some Sufficient Conditions For The Jacobson Radical Of A Commutative Ring With Identity To Contain A Prime Ideal, Melvin Henriksen

All HMC Faculty Publications and Research

Throughout, the word "ring" will abbreviate the phrase "commutative ring with identity element 1" unless the contrary is stated explicitly. An ideal I of a ring R is called pseudoprime if ab = 0 implies a or b is in I. This term was introduced by C. Kohls and L. Gillman who observed that if I contains a prime ideal, then I is pseudoprime, but, in general, the converse need not hold. In [9 p. 233], M. Larsen, W. Lewis, and R. Shores ask if whenever the Jacobson radical J(R) of an arithmetical ring is pseudoprime, it follows that J(R) …