K-quasiderivations

A K-quasiderivation is a map which satisfies both the Product Rule and the Chain Rule. In this paper, we discuss several interesting families of K-quasiderivations. We first classify all K-quasiderivations on the ring of polynomials in one variable over an arbitrary commutative ring R with unity, thereby extending a previous result. In particular, we show that any such K-quasiderivation must be linear over R. We then discuss two previously undiscovered collections of (mostly) nonlinear K-quasiderivations on the set of functions defined on some subset of a field. Over the reals, our constructions yield a one-parameter family of K-quasiderivations which includes the ordinary derivative as a special case.     

Dispersing hash functions

We define a family of functions F from a domain U to a range R to be dispersing if for every set S ? U of a certain size and random h ∈ F, the expected value of ∣S∣ – ∣h[S]∣ is not much larger than the expectation if h had been chosen at random from the set of all functions from U to R. We give near‐optimal upper and lower bounds on the size of dispersing families and present several applications where using such a family can reduce the use of random bits compared to previous randomized algorithms. A close relationship between dispersing families and extractors is exhibited. This relationship provides good explicit constructions of dispersing hash functions for some parameters, but in general the explicit construction is left open. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph

The Erd?s‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erd?s‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q^3/2. We also prove that every subset of vertices of size greater than q^2/2 + q^3/2 + O(q) in the Erd?s‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007     

A decision procedure for well-formed linear quantum cellular automata

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n²) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 381–394 (1997)     

STRONGLY SEQUENTIALLY CONTINUOUS FUNCTIONS

Abstract

Given a topological abelian group G, we study the class of strongly sequentially continuous functions on G. Strong sequential continuity is a property intermediate between sequential continuity and uniform sequential continuity, which appeared naturally in the study of smooth functions on Banach spaces. In this paper, we shall mainly concentrate on the gap between strong sequential continuity and uniform sequential continuity. It turns out that if G has some completeness property—for example, if it is completely metrizable—then all strongly sequentially continuous functions on G are uniformly sequentially continuous. On the other hand, we exhibit a large and natural class of groups for which the two notions differ. This class is defined by a property reminiscent of the classical Dirichlet theorem; it includes all dense sugroups of R generated by an increasing sequence of Dirichlet sets, and groups of the form (X, w), where X is a separable Banach space failing the Schur property. Finally, we show that the family of bounded, real-valued strongly sequentially continuous functions on G is a closed subalgebra of l∞(G).     

On Extraneous Fixed-Points of the Basic Family of Iteration Functions

Let K denote either the reals or the complex numbers. Consider the root-finding problem for an analytic function f from K into itself via an iteration function F. An extraneous fixed-point of F is a fixed-point different than a root of f. We prove that all extraneous fixed-points of any member of an infinite family of iteration functions, called the Basic Family in Kalantari et al. (1997). are repulsive. This generalizes a result of Vrscay and Gilbert (1988) who prove the property only for the second member of the family which coincides with the well-known Halley's method. Our result implies that a convergent orbit corresponding to any specific member of the Basic Family will necessarily converge to a zero of f. The Basic Family is a fundamental family with several different representations. It has been rediscovered by several authors using various techniques. The earliest derivation of this family is from an analysis of Schröder (1870). But in fact the Basic Family and its multipoint versions are all derivable from a determinantal generalization of Taylor's theorem (Kalantari (1997)).     

Threshold functions for asymmetric Ramsey properties involving cycles

We consider the binomial random graph G_p and determine a sharp threshold function for the edge-Ramsey property for all l₁,…,l_r, where C^l denotes the cycle of length l. As deterministic consequences of our results, we prove the existence of sparse graphs having the above Ramsey property as well as the existence of infinitely many critical graphs with respect to the property above. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 245–276, 1997     

Properly colored hamilton cycles in edge-colored complete graphs

It is shown that, for ϵ>0 and n>n₀(ϵ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1-1/\sqrt2-\epsilon)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 179–186 (1997)     

Property testers for dense constraint satisfaction programs on finite domains

Many NP‐hard languages can be “decided” in subexponential time if the definition of “decide” is relaxed only slightly. Rubinfeld and Sudan introduced the notion of property testers, probabilistic algorithms that can decide, with high probability, if a function has a certain property or if it is far from any function having this property. Goldreich, Goldwasser, and Ron constructed property testers with constant query complexity for dense instances of a large class of graph problems. Since many graph problems can be viewed as special cases of the Constraint Satisfaction Problem on Boolean domains, it is natural to try to construct property testers for more general cases of the Constraint Satisfaction Problem. In this paper, we give explicit constructions of property testers using a constant number of queries for dense instances of Constraint Satisfaction Problems where the constraints have constant arity and the variables assume values in some domain of finite size. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 14–32, 2002     

C1,α domains and unique continuation at the boundary

It is shown that the square of a nonconstant harmonic function u that either vanishes continuously on an open subset V contained in the boundary of a Dini domain or whose normal derivative vanishes on an open subset V in the boundary of a C^1,1 domain in ℝ^d satisfies the doubling property with respect to balls centered at points Q ∈ V. Under any of the above conditions, the module of the gradient of u is a B₂(dσ)-weight when restricted to V, and the Hausdorff dimension of the set of points {Q ∈ V : ∇u(Q) = 0} is less than or equal to d−2. These results are generalized to solutions to elliptic operators with Lipschitz second-order coefficients and bounded coefficients in the lower-order terms. © 1997 John Wiley & Sons, Inc.     

Constructions of infinite graphs with Ramsey property

For every infinite cardinal λ and 2 ≤ n < ω there is a directed graph D of size λ such that D does not contain directed circuits of length ≤n and if its vertices are colored with <λ colors, then there is a monochromatic directed circuit of length n + 1. For every infinite cardinal λ and finite graph X there is a λ-sized graph Y such that if the vertices of Y are colored with <λ colors, then there is a monochromatic induced copy of X. Further, Y does not contain larger cliques or shorter odd circuits than X. The constructions are using variants of Specker-type graphs.     

Graphs with the n‐e.c. adjacency property constructed from resolvable designs

Only recently have techniques been introduced that apply design theory to construct graphs with the n‐e.c. adjacency property. We supply a new random construction for generating infinite families of finite regular n‐e.c. graphs derived from certain resolvable Steiner 2‐designs. We supply an extension of our construction to the infinite case, and thereby give a new representation of the infinite random graph. We describe a family of deterministic graphs in infinite affine planes which satisfy the 3‐e.c. property. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 294–306, 2009     

Well‐Balanced Designs for Data Placement

The problem we consider in this article is motivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement that minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well‐balanced design—that is, a family of blocks—each of size k, such that each j‐element subset of V, , belongs to the same or almost the same number of blocks (difference at most one). The existence of well‐balanced designs is a difficult problem as it contains, as a subproblem, the existence of Steiner systems. We completely solve the case and give bounds and constructions for and some values of v and b.     

The phase transition in inhomogeneous random graphs

The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models. One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007     

Topological Constructions in the o–Graph Calculus

Benedetti and Petronio developed in [1] a so called o–Graph Calculus, where a compact oriented 3–manifold with nonempty boundary could be described by a quadrivalent graph together with some extra structure. In this paper, we will show how topological constructions such as puncturing, connected sums, attaching handles, closing boundary components and product and mapping tori constructions can be translated into the o–graph calculus.     

A New Uniform Convergence for Partial Functions

Suppose X, Y are topological spaces. In this paper maps are not necessarily continuous. A map f from a non-empty subset of X to Y is called a partial map. Partial maps occur as inverse functions in elementary analysis, as solution of ordinary differential equations, as utility functions in mathematical economics, etc. In many applications, X and Y are metric spaces and there is a need to have a uniform convergence on a family of partial functions. Since partial maps do not have a common domain, the usual uniform convergence (u.c.) is not available. Noting that in many situations, all maps of a family under consideration, have a common range, we define a new uniform convergence (n.u.c.) that is complementary to the usual one. This n.u.c. does not preserve continuity but preserves (uniform) openness. Its usefulness stems from the fact that it can be used when u.c. cannot be defined. Moreover, in some situations where both u.c. and n.u.c. are available, the latter satisfies our intuition but not the former. We give applications to ODE's and throw some light on earlier literature.     

Simple Constructions of Almost k-wise Independent Random Variables

We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o(1)) (log log n + k/2 + log k + log 1/?), where ? is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ? < 1/(k log n)). An additional advantage of our constructions is their simplicity.     

Sums of two squares in analytic rings

We study analytic singularities for which every positive semidefinite analytic function is a sum of two squares of analytic functions. This is a basic useful property of the plane, but difficult to check in other cases; in particular, what about , , or ? In fact, the unique positive examples we can find are the Brieskorn singularity, the union of two planes in 3-space and the Whitney umbrella. Conversely, we prove that a complete intersection with that property (other than the seven embedded surfaces already mentioned) must be a very simple deformation of the two latter, namely, In particular, except for the stems and , all singularities are real rational double points. Received April 4, 1997; in final form September 25, 1997     

Improving two theorems of bose on difference families

In [2] R. C. Bose gives a sufficient condition for the existence of a (q, 5, 1) difference family in (GF(q), +)—where q ≡ 1 mod 20 is a prime power — with the property that every base block is a coset of the 5th roots of unity. Similarly he gives a sufficient condition for the existence of a (q, 4, 1) difference family in (GF(q, +)—where q ≡ 1 mod 12 is a prime power — with the property that every base block is the union of a coset of the 3rd roots of unity with zero. In this article we replace the mentioned sufficient conditions with necessary and sufficient ones. As a consequence, we obtain new infinite classes of simple difference families and hence new Steiner 2-designs with block sizes 4 and 5. In particular, we get a (p^4α, 5, 1)-DF for any odd prime p ≡ 2, 3 (mod 5), and a (p^2α, 4, 1)-DF for any odd prime p ≡ 2 (mod 3). © 1995 John Wiley & Sons, Inc.     

Every minor-closed property of sparse graphs is testable

Suppose G is a graph of bounded degree d, and one needs to remove ?n of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is far from the statistics of local neighborhoods around vertices of any planar graph G^′. In fact, a similar result is proved for any minor-closed property of bounded degree graphs.The main motivation of the above result comes from theoretical computer-science. Using our main result we infer that for any minor-closed property P, there is a constant time algorithm for detecting if a graph is “far” from satisfying P. This, in particular, answers an open problem of Goldreich and Ron [STOC 1997] [20], who asked if such an algorithm exists when P is the graph property of being planar. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.