A new lower bound for Snake-in-the-Box Codes

In this paper we give a new lower bound on the length of Snake-in-the-Box Codes, i.e., induced cycles in thed-dmensional cube. The bound is a linear function of the number of vertices of the cube and improves the boundc·2 ^d /d, wherec is a constant, proved by Danzer and Klee.     

A new upper bound for the length of snakes

Ad-dimensional circuit code of spreads is a simple circuitC in the graph of thed-dimen sional unit cube with the property that for any verticesx andy ofC which differ in exactlyr co-ordinates,r<s, there exists a path fromx toy consisting ofr edges ofC. This property is useful for detecting and limiting errors. In this paper we give a new upper bound for the maximum length of ad-dimensional circuit code of spread 2.     

An efficient control variate method for pricing variance derivatives

This paper studies the pricing of variance swap derivatives with stochastic volatility by the control variate method. A closed form solution is derived for the approximate model with deterministic volatility, which plays the key role in the paper, and an efficient control variate technique is therefore proposed when the volatility obeys the log-normal process. By the analysis of moments for the underlying processes, the optimal volatility function in the approximate model is constructed. The numerical results show the high efficiency of our method; the results coincide with the theoretical results. The idea in the paper is also applicable for the valuation of other types of variance swap, options with stochastic volatility and other financial derivatives with multi-factor models.     

Extremal problems,partition theorems,symmetric hypergraphs

We compare extremal theorems such as Turán’s theorem with their corresponding partition theorems such as Ramsey’s theorem. We derive a general inequality involving chromatic number and independence number of symmetric hypergraphs. We give applications to Ramsey numbers and to van der Waerden numbers.     

Authentication schemes from actions on graphs, groups, or rings

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others.     

Data compression and histograms

Summary In this paper, the relationship between code length and the selection of the number of bins for a histogram density is considered for a sequence of iid observations on [0,1]. First, we use a shortest code length criterion to select the number of bins for a histogram. A uniform almost sure asymptotic expansion for the code length is given and it is used to prove the asymptotic optimality of the selection rule. In addition, the selection rule is consistent if the true density is uniform [0,1]. Secondly, we deal with the problem: what is the best achievable average code length with underlying density functionf? Minimax lower bounds are derived for the average code length over certain smooth classes of underlying densitiesf. For the smooth class with bounded first derivatives, the rate in the lower bound is shown to be achieved by a code based on a sequence of histograms whose number of bins is changed predictively. Moreover, this best code can be modified to ensure that the almost sure version of the code length has asymptotically the same behavior as its expected value, i.e., the average code length.Research supported in part by NSF grant DMS-8701426Research supported in part by NSF grant DMS-8802378     

Riffle shuffles,cycles, and descents

We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS _n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.     

Analytical methods for an elliptic singular perturbation problem in a circle

We consider an elliptic perturbation problem in a circle by using the analytical solution that is given by a Fourier series with coefficients in terms of modified Bessel functions. By using saddle point methods we construct asymptotic approximations with respect to a small parameter. In particular we consider approximations that hold uniformly in the boundary layer, which is located along a certain part of the boundary of the domain.     

Covering the hypercube with a bounded number of disjoint snakes

We present a construction of an induced cycle in then-dimensional hypercubeI[n] (n2), and a subgroup _n ofI[n] considered as the group ₂ ⁿ , such that | _n |16 and the induced cycle uses exactly one element of every coset of _n . This proves that for anyn2 the vertices ofI[n] can be covered using at most 16 vertex-disjoint induced cycles.     

Conservative weightings and ear-decompositions of graphs

A subsetJ of edges of a connected undirected graphG=(V, E) is called ajoin if |CJ||C|/2 for every circuitC ofG. Answering a question of P. Solé and Th. Zaslavsky, we derive a min-max formula for the maximum cardinality of a joint ofG. Namely, =(+|V|–1)/2 where denotes the minimum number of edges whose contraction leaves a factor-critical graph.To study these parameters we introduce a new decomposition ofG, interesting for its own sake, whose building blocks are factor-critical graphs and matching-covered bipartite graphs. We prove that the length of such a decomposition is always and show how an optimal join can be constructed as the union of perfect matchings in the building blocks. The proof relies on the Gallai-Edmonds structure theorem and gives rise to a polynomial time algorithm to construct the optima in question.     

A maximum principle for node voltages in finitely structured,transfinite, electrical networks

Transfinite electrical networks have unique finite-powered voltage-current regimes given in terms of branch voltages and branch currents, but they do not in general possess unique node voltages. However, if their structures are sufficiently restricted, those node voltages will exist and will satisfy a maximum principle much like that which holds for ordinary infinite electrical networks. The structure that is imposed in order to establish these results generalized the idea of local-finiteness. Other properties that do not hold in general for transfinite networks but do hold under the imposed structure are Kirchhoff's current laws for nodes of any ranks and the permissibility of connecting pure voltage sources to such nodes. This work lays the foundation for a theory of transfinite random walks, which will be the subject of a subsequent work.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

Perfect couples of graphs

We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812.     

Large deviations for a reaction diffusion model

Summary We obtain large deviation estimates for the empirical measure of a class of interacting particle systems. These consist of a superposition of Glauber and Kawasaki dynamics and are described, in the hydrodynamic limit, by a reaction diffusion equation. We extend results of Kipnis, Olla and Varadhan for the symmetric exclusion process, and provide an approximation scheme for the rate functional. Some physical implications of our results are briefly indicated.     

Generalized lipschitz conditions and riesz derivatives on the space of bessel potentials Lp α

In the foregoing Note (this Journal Vol.I.p. 75-99) the space of n-dimensional Bessel potentials L^p _x was deseribed in terms of generalized Lipschitz conditions of f or its Riesz transform for 0<∝≦2 The still open case ∝>1 is treated in the first half of this paper, firstly by introducing appropriate iterates of the cited conditions, secondly by using derivatives of f and its Riesz transform, in particular the Laplacian △ and the gradient of the Riesz transformation(▽,R and by applying the former results In Section 6 a definition of a Riesz derivative of order ∝ is given and based upon the concept: Integrate f(m-α)-times in the sense of Riesz and then differentiate [d]m-times (by considering the limit of suitable difference quotients of f). Necessary and sufficient conditions for the existence of these Riesz derivatives are obtained All results also hold in the non-reflexive spaces[d]     

The integrable nonlinear degenerate diffusion equationu t=[f(u)u x −1 x and its relatives

The nonlinear diffusion equationu _t=[f(u)g(u _x )] arises in recent models of turbulent transport and of stress dissipation in rock blasting. A Lie point symmetry analysis produces many similarity reductions of exponential and power-law forms, and reveals that for all choices off the equation is always integrable wheng(u _x )=1/u _x . We identify the functionsf(u) which guarantee equivalence to the linear heat equation. For all other choices off, the linear canonical form leads to a self-adjoint differential equation by separation of variablesx andt. We construct a number of explicit solutions with simple boundary conditions, which illustrate behavior in the vicinity of the degenerate region withu _x =. If zero flux and constant concentration are maintained on free boundaries, then steep concentration gradients may evolve from smooth initial conditions. For other boundary conditions, unlike the examples of strong degeneracy, smoothing will occur at initial step discontinuities.     

Semi-linear Liouville theorems in the Heisenberg group via vector field methods

We consider a global Liouville type theorem for semi-linear elliptic equation on Heisenberg group. Our main idea is the method of integration by parts for a “vector field” analogous to the quantity in Gidas and Spruck (1981) [5].     

A lower bound for the spectral radius of a digraph

We show that the spectral radius ρ(D) of a digraph D with n vertices and c₂ closed walks of length 2 satisfies Moreover, equality occurs if and only if D is the symmetric digraph associated to a -regular graph, plus some arcs that do not belong to cycles. As an application of this result, we construct new sharp upper bounds for the low energy of a digraph, which extends Koolen and Moulton bounds of the energy to digraphs.     

A Lax equivalence theorem for stochastic differential equations

In this paper, a stochastic mean square version of Lax’s equivalence theorem for Hilbert space valued stochastic differential equations with additive and multiplicative noise is proved. Definitions for consistency, stability, and convergence in mean square of an approximation of a stochastic differential equation are given and it is shown that these notions imply similar results as those known for approximations of deterministic partial differential equations. Examples show that the assumptions made are met by standard approximations.     

Interfaces and typical Gibbs configurations for one-dimensional Kac potentials

Summary We consider a one dimensional Ising spin system with a ferromagnetic Kac potential J(|r|),J having compact support. We study the system in the limit, »0, below the Lebowitz-Penrose critical temperature, where there are two distinct thermodynamic phases with different magnetizations. We prove that the empirical spin average in blocks of size ^–1 (for any positive ) converges, as »0, to one of the two thermodynamic magnetizations, uniformly in the intervals of size ^–p , for any given positivep1. We then show that the intervals where the magnetization is approximately constant have lengths of the order of exp(c ^–1),c>0, and that, when normalized, they converge to independent variables with exponential distribution. We show this by proving large deviation estimates and applying the Ventsel and Friedlin methods to Gibbs random fields. Finally, if the temperature is low enough, we characterize the interface, namely the typical magnetization pattern in the region connecting the two phases.The research has been partially supported by CNR, GNFM, GNSM and by grant SC1CT91-0695 of the Commission of European Communities     

Hammersley's interacting particle process and longest increasing subsequences

Summary In a famous paper [8] Hammersley investigated the lengthL _n of the longest increasing subsequence of a randomn-permutation. Implicit in that paper is a certain one-dimensional continuous-space interacting particle process. By studying a hydrodynamical limit for Hammersley's process we show by fairly “soft” arguments that limn ^′1/2 EL _n =2. This is a known result, but previous proofs [14, 11] relied on hard analysis of combinatorial asymptotics. Research supported by NSF Grant MCS 92-24857 and the Miller Institute for Basic Research in Science Research supported by NSF Grant DMS92-04864