The statistics of words on rings

We analyze sequences of letters on a ring. Our objective is to determine the statistics of the occurrences of a set of r‐letter words when the sequence is chosen as a periodic Markov chain of order ≤ r ? 1. We first obtain a generating function for the associated probability distribution and then display its Poisson limit. For an i.i.d. letter sequence, correction terms to the Poisson limit are given. Finally, we indicate how a hidden Markov chain fits into this scheme. © 2005 Wiley Periodicals, Inc.     

Cores in random hypergraphs and Boolean formulas

We describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the appearance of a k‐core in a random r‐uniform hypergraph for all r, k ≥ 2, r + k > 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r‐SAT, r ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On r-quick limit sets for empirical and related processes based on mixing random variables

The r-quick limit points of normalized sample paths and empirical distribution functions of mixing processes are characterized. An r-quick version of Bahadur-Kiefer-type representation for sample quantiles is established, which yields the r-quick limit points of quantile processes. These results are applied to linear functions of order statistics. Some results on r-quick convergence of certain Gaussian processes are also established.     

Extremes in autoregressive processes with uniform marginal distributions

Chernick (1981) derives a limit theorem for the maximum term for a class of first order autoregressive processes with uniform marginal distributions. The parameter for these processes is equal to 1/r where r is an integer, r 2. Based on this limit theorem, the asymptotic distribution of the minimum term and the joint asymptotic distribution of the maximum and minimum terms in the sequence are obtained. Since the condition D′(u_n) of Leadbetter (1974) fails, the condition of Davis (1979), D′(v_n, u_n), also fails. Negatively correlated uniform sequences are shown to exist. Asymptotic distributions for the maximum and minimum terms in the sequence are derived and it is shown that the maximum and minimum are not asymptotically independent.     

The asymptotic distribution of long cycles in random regular graphs

The asymptotic distribution of the number of cycles of length l in a random r‐regular graph is determined. The length of the cycles is defined as a function of the number of vertices n, thus l=l(n), and the length satisfies l(n)→∞ as n→∞. The limiting distribution turns out to depend on whether l(n)/n→0 or l(n)/n→q, 0<q<1 as n→∞. In the first case the limit distribution is a weighted sum of Poisson variables while in the other case the limit distribution is similar to the limit distribution of Hamiltonian cycles in a random r‐regular graph. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15: 43–92, 1999     

Expansions for von Mises functionals

Summary Berry-Esseen results and expansions are derived for the distribution function of von Mises functionals of order r under moment conditions and conditions on the smoothness of the limit distribution.The results apply to goodness-of-fit statistics — as well as to the central limit theorem in L ^2p,p2, the rate of convergence being O(n ^–1) for centered balls, provided a fourth moment exists.Research sponsored in part under Office of Naval Research. Contract Number N00014-80-C-0163.     

Limiting angles of Γ-martingales

Suppose that M is a complete, simply connected Riemannian manifold of non-positive sectional curvature with dimension m≥ 3 and that, outside a fixed compact set, the sectional curvatures are bounded above by −c ₁/{r ² ln r} and below by −c ₂ r ², where c ₁ and c ₂ are two positive constants and r is the geodesic distance from a fixed point. We show that, when κ≥ 1 satisfies certain conditions, the angular part of a κ-quasi-conformal Γ-martingale on M tends to a limit as time tends to infinity and the closure of the support of the distribution of this limit is the entire sphere at infinity. This improves both a result of Le for Brownian motion and also results concerning the non-existence of κ-quasi-conformal harmonic maps from certain types of Riemannian manifolds into M. Received: 19 September 1997     

On vertical skew symmetric almost contact 3-structures

We consider a (2m + 3)-dimensional Riemannian manifold M(ξ _r, η^r, g ) endowed with a vertical skew symmetric almost contact 3-structure. Such manifold is foliated by 3-dimensional submanifolds of constant curvature tangent to the vertical distribution and the square of the length of the vertical structure vector field is an isoparametric function. If, in addition, M(ξ _r, η^r, g ) is endowed with an f -structure φ, M, turns out to be a framed f−CR-manifold. The fundamental 2-form Ω associated with φ is a presymplectic form. Locally, M is the Riemannian product of two totally geodesic submanifolds, where is a 2m-dimensional Kaehlerian submanifold and is a 3-dimensional submanifold of constant curvature. If M is not compact, a class of local Hamiltonians of Ω is obtained.     

Almost all regular graphs are hamiltonian

In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r-regular graphs are hamiltonian for any fixed r ? 3, by an analysis of the distribution of 1-factors in random regular graphs. Moreover, almost all such graphs are r-edge-colorable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colorable for fixed r ? 3. © 1994 John Wiley & Sons, Inc.     

A Lower Bound of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> Norms in the CLT for Strongly Mixing Random Variables

We derive a lower bound of L _p norms, 1 ⩽ p ⩽ ∞, in the central limit theorem for strongly mixing random variables X ₁,..., X _n with under the boundedness condition ℙ{|X _i | ⩽ M} = 1 with a nonrandom constantM > 0 and condition ∑ _r⩾1 r ²α(r) < ∞, where α(r) are the Rosenblatt strong mixing coefficients. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 4, pp. 587–602, October–December, 2005.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

Discretization of Compact Riemannian Manifolds Applied to the Spectrum of Laplacian

For κ ⩾ 0 and r₀ > 0 let ℳ(n, κ, r₀) be the set of all connected, compact n-dimensional Riemannian manifolds (Mⁿ, g) with Ricci (M, g) ⩾ −(n−1) κ g and Inj (M) ⩾ r₀. We study the relation between the kth eigenvalue λ_k(M) of the Laplacian associated to (Mⁿ,g), Δ = −div(grad), and the kth eigenvalue λ_k(X) of a combinatorial Laplacian associated to a discretization X of M. We show that there exist constants c, C > 0 (depending only on n, κ and r₀) such that for all M ∈ ℳ(n, κ, r₀) and X a discretization of for all k < |X|. Then, we obtain the same kind of result for two compact manifolds M and N ∈ ℳ(n, κ, r₀) such that the Gromov–Hausdorff distance between M and N is smaller than some η > 0. We show that there exist constants c, C > 0 depending on η, n, κ and r₀ such that for all . Mathematics Subject Classification (2000): 58J50, 53C20 Supported by Swiss National Science Foundation, grant No. 20-101 469     

Proof Of A Conjecture Of Erdős On Triangles In Set-Systems

A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element. Analogous results are obtained for nonuniform families.     

A numerical method for computing radially symmetric solutions of a dissipative nonlinear modified Klein‐Gordon equation

In this article we develop a finite‐difference scheme to approximate radially symmetric solutions of a dissipative nonlinear modified Klein‐Gordon equation subject to smooth initial conditions ? and ψ in an open sphere D around the origin, with constant internal and external damping coefficients—β and γ, respectively—, and nonlinear term of the form G′(w) = w^p, with p > 1 an odd number. The functions ? and ψ are radially symmetric in D, and ?, ψ, r?, and rψ are assumed to be small at infinity. We prove that our scheme is consistent order ??(Δt²) + ??(Δr²) for G′ identically equal to zero and provide a necessary condition for it to be stable order n. Part of our study will be devoted to compare the physical effects of β and γ. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

On the stationary quasi-Newtonian flow obeying a power-law

We investigate in this paper existence of a weak solution for a stationary incompressible Navier-Stokes system with non-linear viscosity and with non-homogeneous boundary conditions for velocity on the boundary. Our concern is with the viscosity obeying the power-law dependence ν(ξ) = ∣Tr(ξξ*)∣^r/2?1, r < 2, on shear stress ξ. It is corresponding to most quasi-Newtonian flows with injection on the boundary. Since for r ? 2 the inertial term precludes any a priori estimate in general, we suppose the Reynolds number is not too large. Using the specific algebraic structure of the Navier-Stokes system we prove existence of at least one approximate solution. The constructed approximate solution turns out to be uniformly bounded in W^1,r (Omega;)ⁿ and using monotonicity and compactness we successfully pass to the limit for r ≥ 3n/(n + 2). For 3n/(n + 2) > r > 2n/(n + 2) our construction gives existence of at least one very weak solution. Furthermore, for r ≥ 3n/(n + 2) we prove that all weak solutions lying in the ball in W of radius smaller than critical are equal. Finally, we obtain an existence result for the flow through a thin slab.     

Unit-distance graphs,graphs on the integer lattice and a Ramsey type result

Summary Let (R ², 1) denote the graph withR ² as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R ², 1) is still open; however,(R ², 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R ², 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z ²,r, ) denote a graph with vertex setZ ² and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r – ,r + ]. A simple graph is faithfully -recurring inZ ² if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z ²,r, ) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R ², 1) if and only ifG is faithfully -recurring inZ ². In this paper we prove that(Z ²,r, ) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ ² either there exists a monochromatic pair of vertices with their distance in the closed interval [r – ,r + ] or there exists a set of three vertices closest to each other with three distinct colors.     

Positive Harmonic Functions for Semi-Isotropic Random Walks on Trees, Lamplighter Groups, and DL-Graphs

We determine all positive harmonic functions for a large class of “semi-isotropic” random walks on the lamplighter group, i.e., the wreath product ℤ_q≀ℤ, where q≥2. This is possible via the geometric realization of a Cayley graph of that group as the Diestel–Leader graph . More generally, (q,r≥2) is the horocyclic product of two homogeneous trees with respective degrees q+1 and r+1, and our result applies to all -graphs. This is based on a careful study of the minimal harmonic functions for semi-isotropic walks on trees. Mathematics Subject Classifications (2000) 60J50, 05C25, 20E22, 31C05, 60G50. Supported by European Commission, Marie Curie Fellowship HPMF-CT-2002-02137.     

Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems

We consider semidefinite monotone linear complementarity problems (SDLCP) in the space ⁿ of real symmetric n×n-matrices equipped with the cone ⁿ₊ of all symmetric positive semidefinite matrices. One may define weighted (using any Mⁿ₊₊ as weight) infeasible interior point paths by replacing the standard condition XY=rI, r>0, (that defines the usual central path) by (XY+YX)/2=rM. Under some mild assumptions (the most stringent is the existence of some strictly complementary solution of (SDLCP)), these paths have a limit as r0, and they depend analytically on all path parameters (such as r and M), even at the limit point r=0.Mathematics Subject Classification (1991): 90C33, 65K05     

The basic theory of infinite time register machines

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all P¹₁{\Pi^1_1} sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ? r{n \in r} with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs.     

On the number of certain subgraphs contained in graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess ₁≧s ₂≧…≧s _r>r, provided (s ₁−s _r)²<s ₁+s _r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l ^k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.