The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

On the moments of some first passage times for sums of dependent random variables

Let S_n,n = 1, 2, …, denote the partial sums of integrable random variables. No assumptions about independence are made. Conditions for the finiteness of the moments of the first passage times N(c) = min {n: S_n>ca(n)}, where c ≥ 0and a(y) is a positive continuous function on [0, ∞), such that a(y) = o(y)as y → ∞, are given. With the further assumption that a(y) = yP,0 ≤ p < 1, a law of large numbers and the asymptotic behaviour of the moments when c → ∞ are obtained. The corresponding stopped sums are also studied.     

Class Partition Algebras as Centralizer Algebras of Wreath Products

In this article, we study an important subalgebra of the tensor product partition algebra P _k (x)? P _k (y), denoted by P _k (x, y) and called “Class Partition Algebra.” We show that the algebra P _k (n, m) is the centralizer algebra of the wreath product S _m ? S _n . Furthermore, the algebra P _k (x, y) and the tensor product partition algebra P _k (x)? P _k (y) are subalgebras of the G-colored partition algebra P _k (x;G) and G-vertex colored partition algebra P _k (x, G) respectively, for every group G with |G|=y ≥ 2k.     

On exponential sums over primes in short intervals

Let Λ(n) be the von Mangoldt function, x real and y small compared with x. This paper gives a non-trivial estimate on the exponential sum over primes in short intervals S₂(x,y;a)=?_{x < n ￡ x+y}L(n)e(n² a)S_2(x,y;{\alpha})=\sum_{x < n \le x+y}\Lambda(n)e(n^2 {\alpha}) for all α ∈ [0,1] whenever x^\frac23+e ￡ y ￡ xx^{\frac{2}{3}+{\varepsilon}}\le y \le x . This result is as good as what was previously derived from the Generalized Riemann Hypothesis.     

Approximations of Two-Place Functions by Finite Sums of Terms with Separable Variables

It is known that if a smooth function h in two real variables x and y belongs to the class Σ_n of all sums of the form Σⁿ_k=1ƒ_k(x) g_k(y), then its (n + 1)th order "Wronskian" det[h_xⁱy^j]ⁿ_i,j=0 is identically equal to zero. The present paper deals with the approximation problem h(x, y) Σⁿ_k=1ƒ_k(x) g_k(y) with a prescribed n, for general smooth functions h not lying in Σ_n. Two natural approximation sums T=T(h) Σ_n, S=S(h) Σ_n are introduced and the errors |h-T|, |h-S| are estimated by means of the above mentioned Wronskian of the function h. The proofs utilize the technique of ordinary linear differential equations.     

On fair parametric rational cubic curves

First we derive conditions that a parametric rational cubic curve segment, with a parameter, interpolating to plane Hermite data {(x _i ^(k) ,y _i ^(k) ),i = 0, 1;k = 0, 1} contains neither inflection points nor singularities on its segment. Next we numerically determine the distribution of inflection points and singularities on a segment which gives conditions that aC ² parametric rational cubic curve interpolating to dataS = {(x _i ^(k) ,y _i ^(k) ), 0 i n} is free of inflection points and singularities. When the parametric rational cubic curve reduces to the well-known parametric cubic one, we obtain a theorem on the distribution of the inflection points and singularities on the cubic curve segment which has been widely used for finding aC ¹ fair parametric cubic curve interpolating toS.     

Some notes on Hermite-Fejer type interpolation

Let S_n(f,x) be the Hermite-Fejér type interpolation satisfying S_n(f,x_k)=f(x_k), S′_n(f,x_k)=0, k=1,2,…,n and S_n(f,y_i)=f(y_i), j=1,2,…,m. For m=0, let H_n(f,x)≔S_n(f,x). This paper investigates relationship between S_n(f,x) and H_n(f,x), as well as, the saturation of S_n(f,x).     

On a function associated with the Bessel functions

Summary Defining the function Δn, 1,k;x(J) asΔn, 1,k;x(J)=J _n+1(x)−J _n(x)J _n+k+1(x) associated with the Bessel functionJ _n(x), we derive a series of products of Bessel functions for Δ_{n, f, k, x} (J). Whenk=1,k;x (J) becomes Turàn expression for Bessel functions. Some consequences have been pointed out.

---

Riassunto Definita la Δ_{n, f, k, x} (J) come Δ_{n, f, k, x}, (J)=J _n+1(x)J _n+k(x)-J _n(_n+k+1)(x) associata alla funzioneJ _n(x) di Bessel, si ricava una serie di prodotti di funzioni di Bessel per Δ_{n, f, k, x}, (J). 3 Quandok=1, Δ_{n, f, k, x}, (J) diventa una espressione di Turàn per le funzioni di 2 Bessel, vengono inoltre indicate alcune altre conseguenze.

     

A Nim-like Game and Dynamic Recurrence Relations

The nim-like game 〈n, f; X, Y〉 is defined by an integer n ≥ 2 a constraint function f, and two players and X and Y. Players X and Y alternate taking coins from a pile of n coins, with X taking the first turn. The winner is the one who takes the last coin. On the kth turn, a player may remove t_k coins, where 1 ≤ t₁ ≤ n ? 1 and 1 ≤ t_k ≤ max{1, f(t_k?1) for k > 1. Let the set S_f = {1} ∪ {n| there is a winning strategy for Y in the nim-like game 〈n, f; X, Y〉}. In this paper, an algorithm is provided to construct the set S_f = {a₁, a₂,…} in an increasing sequence when the function f(x) is monotonic. We show that if the function f(x) is linear, then there exist integers n₀ and m such that a_n+1 = a_n + a_n?m for n > n₀ and we give upper and lower bounds for m (dependent on f. A duality is established between the asymptotic order of the sequence of elements in S_f and the degree of the function f(x). A necessary and sufficient condition for the sequence {a₀, a₁, a₂,…} of elements in S_f to satisfy a regular recurrence relation is described as well.     

Rado Numbers fora(x+y)=bz

In the case of existence the smallest numberN=Ra_kis called a Rado number if it is guaranteed that anyk-coloring of the numbers 1, 2, …, Ncontains a monochromatic solution of a given system of linear equations. We will determine Ra_k(a, b) for the equationa(x+y)=bzifb=2 andb=a+1. Also, the case of monochromatic sequences {x_n} generated bya(x_n+x_n+1)=bx_n+2 is discussed.     

Packing and covering constants for certain families of trees. I

If ? denotes a family of rooted trees, let p_k(n) and c_k(n) denote the average value of the k-packing and k-covering numbers of trees in ? that have n nodes. We assume, among other things, that the generating function y of trees in ? satisfies a relation of the type y = x?(y) for some power series ?. We show that the limits of p_k(n)/n and c_k(n)/n as n → ∞ exist and we describe how to evaluate these limits.     

On the noise sensitivity of monotone functions

It is known that for all monotone functions f : {0, 1}ⁿ → {0, 1}, if x ∈ {0, 1}ⁿ is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability ? = n^?α, then P[f(x) ≠ f(y)] < cn^?α+1/2, for some c > 0. Previously, the best construction of monotone functions satisfying P[f_n(x) ≠ f_n(y)] ≥ δ, where 0 < δ < 1/2, required ? ≥ c(δ)n^?α, where α = 1 ? ln 2/ln 3 = 0.36907 …, and c(δ) > 0. We improve this result by achieving for every 0 < δ < 1/2, P[f_n(x) ≠ f_n(y)] ≥ δ, with:

• ? = c(δ)n^?α for any α < 1/2, using the recursive majority function with arity k = k(α);
• ? = c(δ)n^?1/2log^tn for t = log₂ = .3257 …, using an explicit recursive majority function with increasing arities; and
• ? = c(δ)n^?1/2, nonconstructively, following a probabilistic CNF construction due to Talagrand.

We also study the problem of achieving the best dependence on δ in the case that the noise rate ? is at least a small constant; the results we obtain are tight to within logarithmic factors. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 333–350, 2003     

On the weak non-defectivity of veronese embeddings of projective spaces

Fix integers n, x, k such that n≥3, k>0, x≥4, (n, x)≠(3, 4) and k(n+1)<( _n ^n+x ). Here we prove that the order x Veronese embedding ofP ⁿ is not weakly (k−1)-defective, i.e. for a general S⊃P ⁿ such that #(S) = k+1 the projective space | I _2S (x)| of all degree t hypersurfaces ofP ⁿ singular at each point of S has dimension ( _n ^/n+x )−1− k(n+1) (proved by Alexander and Hirschowitz) and a general F∈| I _2S (x)| has an ordinary double point at each P∈ S and Sing (F)=S. The author was partially supported by MIUR and GNSAGA of INdAM (Italy).     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

An optimal version of an inequality involving the third symmetric means

Let (GA) _n ^[k](a), A _n (a), G _n (a) be the third symmetric mean of k degree, the arithmetic and geometric means of a ₁, …, a _n (a _i > 0, i = 1, …, n), respectively. By means of descending dimension method, we prove that the maximum of p is k−1/n−1 and the minimum of q is n/n−1(k−1/k) ^k/n so that the inequalities {fx505-1} hold.     

Beyond quenching for singular reaction-diffusion problems

Let f(u) be twice continuously differentiable on [0, c]) for some constant c such that f(0) > 0,f′ ? 0,f″ ? 0, and lim_u→cf(u) = ∞. Also, let χ(S) be the characteristic function of the set S. This article studies all solutions u with non-negative u_t, in the region where u < c and with continuous u_x for the problem: u_xx – u_t = ? f(u)χ({u < c}), 0 < x < a, 0 < t < ∞, subject to zero initial and first boundary conditions. For any length a larger than the critical length, it is shown that if ∫f(u) du < ∞, then as t tends to infinity, all solutions tend to the unique steady-state profile U(x), which can be computed by a derived formula; furthermore, increasing the length a increases the interval where U(x) ? c by the same amount. For illustration, examples are given.     

On the mean value of the function $$ {\bar{S}_k}(n) $$

An asymptotic formula is constructed for the mean value of the function [`(S)]_k(n) {\bar{S}_k}(n) dual to the Smarandache function S _k (n). The O- and Ω-estimates for the second moment of the remainder are obtained.     

Toeplitz–Schur Multipliers of the Class Sp(L2G) for p< 1

We study Toeplitz–Schur multipliers of the Schatten–von Neumann class S _p for 0 < p < 1. We describe all functions F on an arbitrary commutative locally compact group G satisfying the following condition: for any integral operator in S _p with kernel function k(x,y), the kernel function F(x-y)k(x)k(y) defines also an integral operator in S _p. Bibliography: 4 titles.