An Almost Accurate Location of the Maximum Stirling Number(s) of the Second Kind

The Stirling number of the second kind S(n, k) is the number of ways of partitioning a set of n elements into k nonempty subsets. It is well known that the numbers S(n, k) are unimodal in k, and there are at most two consecutive values K _n such that (for fixed n) S(n, K _n ) is maximal. We determine asymptotic bounds for K _n , which are unexpectedly good and improve earlier results. The method used here shows a possible strategy for obtaining numerical bounds such that in almost all cases K _n can be uniquely determined.     

On Strong Versions of the Central Limit Theorem

Let S_n be the sum of n i.i.d.r.v. and let 1_(-∞,x)(·) be the indicator function of the interval (-∞, x). Then the sequence 1_{(-∞, x)}(S_n/√n) does not converge for any x. Likewise the arithmetic means of this sequence converge only with probability zero. But the logarithmic means converge with probability one to the standard normal distribution Ø(x). Then for any bounded and a.e. continuous function a(y) the logarithmic means of a(S_n/√n) converge a.s. to a = ∫a(y)dØ(y). The arithmetic means of a(S_nk/√n) converge to the same limit a for all subsequences n_k = [c^k], c > 1.     

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.     

On a problem of rota

Let S(n, k) denote Stirling numbers of the second kind; for each n, let K_n be such that S(n, K_n) ? S(n, k) for all k. Also, let P(n) denote the lattice of partitions of an n-element set. Say that a collection of partitions from P(n) is incomparable if no two are related by refinement. Rota has asked if for all n, the largest possible incomparable collection in P(n) contains S(n, K_n) partitions. In this paper, we construct for all n sufficiently large an incomparable collection in P(n) containing strictly more than S(n, K_n) partitions. We also estimate how large n must be for this construction to work.     

Polynomial interpolation and sums of powers of integers

In this note, we revisit the problem of polynomial interpolation and explicitly construct two polynomials in n of degree k + 1, P_k(n) and Q_k(n), such that P_k(n) = Q_k(n) = f_k(n) for n = 1, 2,…?, k, where f_k(1), f_k(2),…?, f_k(k) are k arbitrarily chosen (real or complex) values. Then, we focus on the case that f_k(n) is given by the sum of powers of the first n positive integers S_k(n) = 1^k + 2^k + ??? + n^k, and show that S_k(n) admits the polynomial representations S_k(n) = P_k(n) and S_k(n) = Q_k(n) for all n = 1, 2,…?, and k ≥ 1, where the first representation involves the Eulerian numbers, and the second one the Stirling numbers of the second kind. Finally, we consider yet another polynomial formula for S_k(n) alternative to the well-known formula of Bernoulli.     

Bounds on the location of the maximum Stirling numbers of the second kind

Let S(n,k) denote the Stirling number of the second kind, and let K_n be such that

S(n,K_n−1)<S(n,K_n)≥S(n,K_n+1).     

Multicolor bipartite Ramsey number of C4 and large Kn,n

Let br_k(C₄;K_{n, n}) be the smallest N such that if all edges of K_{N, N} are colored by k + 1 colors, then there is a monochromatic C₄ in one of the first k colors or a monochromatic K_{n, n} in the last color. It is shown that br_k(C₄;K_{n, n}) = Θ(n²/log²n) for k?3, and br₂(C₄;K_{n, n})≥c(n n/log²n)² for large n. The main part of the proof is an algorithm to bound the number of large K_{n, n} in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011     

A Lower Bound for the Norm of the Minimal Residual Polynomial

Let S be a compact infinite set in the complex plane with 0∉S, and let R _n be the minimal residual polynomial on S, i.e., the minimal polynomial of degree at most n on S with respect to the supremum norm provided that R _n (0)=1. For the norm L _n (S) of the minimal residual polynomial, the limit k(S):=lim_n?￥ⁿ?{L_n(S)}\kappa(S):=\lim_{n\to\infty}\sqrt[n]{L_{n}(S)} exists. In addition to the well-known and widely referenced inequality L _n (S)≥κ(S) ⁿ , we derive the sharper inequality L _n (S)≥2κ(S) ⁿ /(1+κ(S)²ⁿ ) in the case that S is the union of a finite number of real intervals. As a consequence, we obtain a slight refinement of the Bernstein–Walsh lemma.     

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).     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Graphs S(n, k) and a Variant of the Tower of Hanoi Problem

For any n 1 and any k 1, a graph S(n, k) is introduced. Vertices of S(n, k) are n-tuples over {1, 2,. . . k} and two n-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs S(n, 3) are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of S(n, k). Together with a formula for the distance, this result is used to compute the distance between two vertices in O(n) time. It is also shown that for k 3, the graphs S(n, k) are Hamiltonian.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

Generating the kernel of a staircase starshaped set from certain staircase convex subsets

Let S be an orthogonal polygon in the plane. Assume that S is starshaped via staircase paths, and let K be any component of Ker S, the staircase kernel of S, where K ≠ S. For every x in S\K, define W _K (x) = {s: s lies on some staircase path in S from x to a point of K}. There is a minimal (finite) collection W(K) of W _K (x) sets whose union is S. Further, each set W _K (x) may be associated with a finite family U _K (x) of staircase convex subsets, each containing x and K, with ∪{U: U in U _K (x)} = W _K (x). If W(K) = {W _K (x ₁), ..., W _K (x _n )}, then K ⊆ V _K ≡ ∩{U: U in some family U _K (x _i ), 1 ≤ i ≤ n} ⊆ Ker S. It follows that each set V _K is staircase convex and ∪{V _k : K a component of Ker S} = Ker S.     

On the number of line separations of a finite set in the plane

Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S?S′. We let f_k(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of f_k(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on f_k(n) is established. Both are nontrivial and improve bounds known before. In particular, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = Ω(n}\text{log}\text{k)}$ is shown by exhibiting special point-sets which realize that many k-sets. In addition, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = O(nk}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is proved by the study of a combinatorial problem which is of interest in its own right.     

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.     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.     

Some graphs determined by their (signless) Laplacian spectra

Let W _n = K ₁ ? C _n?1 be the wheel graph on n vertices, and let S(n, c, k) be the graph on n vertices obtained by attaching n-2c-2k-1 pendant edges together with k hanging paths of length two at vertex υ ₀, where υ ₀ is the unique common vertex of c triangles. In this paper we show that S(n, c, k) (c ? 1, k ? 1) and W _n are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that S(n, c, k) and its complement graph are determined by their Laplacian spectra, respectively, for c ? 0 and k ? 1.     

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.