On sharp Burkholder–Rosenthal-type inequalities for infinite-degree U-statistics

In this paper, we present a method that allows one to obtain a number of sharp inequalities for expectations of functions of infinite-degree U-statistics. Using the approach, we prove, in particular, the following result: Let D be the class of functions f :R₊→R₊ such that the function f(x+z)−f(x) is concave in xR₊ for all zR₊. Then the following estimate holds: for all fD and all U-statistics ∑_1i1<<ilnY_i1,…,il(X_i1,…,X_il) with nonnegative kernels Y_i1,…,il :R^l→R₊, 1i_kn; i_r≠i_s, r≠s; k,r,s=1,…,l; l=0,…,m, in independent r.v.'s X₁,…,X_n. Similar inequality holds for sums of decoupled U-statistics. The class D is quite wide and includes all nonnegative twice differentiable functions f such that the function f″(x) is nonincreasing in x>0, and, in particular, the power functions f(x)=x^t, 1<t2; the power functions multiplied by logarithm f(x)= (x+x₀)^t ln(x+x₀), 1<t<2, x₀max(e^{(3t2−6t+2)/(t(t−1)(2−t))},1); and the entropy-type functions f(x)=(x+x₀)ln(x+x₀), x₀1. As an application of the results, we determine the best constants in Burkholder–Rosenthal-type inequalities for sums of U-statistics and prove new decoupling inequalities for those objects. The results obtained in the paper are, to our knowledge, the first known results on the best constants in sharp moment estimates for U-statistics of a general type.     

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

We consider the bounded integer knapsack problem (BKP) , subject to: , and x_j{0,1,…,m_j},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n³W²) algorithm for BKP, where W=max_j=1,…,nw_j. The respective complexity of the unbounded case with m_j=∞, for j=1,…,n, is O(n²W²). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1’s and uniform right-hand side.     

Mutually independent hamiltonian cycles for the pancake graphs and the star graphs

A hamiltonian cycle C of a graph G is an ordered set u₁,u₂,…,u_n(G),u₁ of vertices such that u_i≠u_j for i≠j and u_i is adjacent to u_i+1 for every i{1,2,…,n(G)−1} and u_n(G) is adjacent to u₁, where n(G) is the order of G. The vertex u₁ is the starting vertex and u_i is the ith vertex of C. Two hamiltonian cycles C₁=u₁,u₂,…,u_n(G),u₁ and C₂=v₁,v₂,…,v_n(G),v₁ of G are independent if u₁=v₁ and u_i≠v_i for every i{2,3,…,n(G)}. A set of hamiltonian cycles {C₁,C₂,…,C_k} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs P_n and the n-dimensional star graphs S_n. It is proven that IHC(P₃)=1, IHC(P_n)=n−1 if n≥4, IHC(S_n)=n−2 if n{3,4} and IHC(S_n)=n−1 if n≥5.     

LOCAL TIME ANALYSIS OF ADDITIVE LEVY PROCESSES WITH DIFFERENT L(E)VY EXPONENTS

Let X1 XN be independent, classical Levy processes on R^d with Levy exponents ψ1,…, ψN, respectively. The corresponding additive Levy process is defined as the following N-parameter random field on R^d, X（t） △= X1（t1） ＋ ... ＋ XN（tN）, At∈N. Under mild regularity conditions on the ψi＇s, we derive estimate for the local and uniform moduli of continuity of local times of X = {X（t）; t ∈R^N}.     

On the ordering of trees by the Laplacian coefficients

We generalize the results from [X.-D. Zhang, X.-P. Lv, Y.-H. Chen, Ordering trees by the Laplacian coefficients, Linear Algebra Appl. (2009), doi:10.1016/j.laa.2009.04.018] on the partial ordering of trees with given diameter. For two n-vertex trees T₁ and T₂, if c_k(T₁)c_k(T₂) holds for all Laplacian coefficients c_k,k=0,1,…,n, we say that T₁ is dominated by T₂ and write T_1cT₂. We proved that among n vertex trees with fixed diameter d, the caterpillar C_n,d has minimal Laplacian coefficients c_k,k=0,1,…,n. The number of incomparable pairs of trees on 18 vertices is presented, as well as infinite families of examples for two other partial orderings of trees, recently proposed by Mohar. For every integer n, we construct a chain of n-vertex trees of length , such that T₀S_n,T_mP_n and T_icT_i+1 for all i=0,1,…,m-1. In addition, the characterization of the partial ordering of starlike trees is established by the majorization inequalities of the pendent path lengths. We determine the relations among the extremal trees with fixed maximum degree, and with perfect matching and further support the Laplacian coefficients as a measure of branching.     

Constant-sign solutions for systems of singular integral equations of Hammerstein type

We consider the system of Hammerstein integral equations

where T>0 is fixed, ρ_i’s are given functions and the nonlinearities f_i(t,x₁,x₂,…,x_n) can be singular at t=0 and x_j=0 where j{1,2,,n}. Criteria are offered for the existence of constant-sign solutions, i.e., θ_iu_i(t)≥0 for t[0,T] and 1≤i≤n, where θ_i{1,−1} is fixed. The tools used are a nonlinear alternative of Leray–Schauder type, Krasnosel’skii’s fixed point theorem in a cone and Schauder’s fixed point theorem. We also include examples and applications to illustrate the usefulness of the results obtained.     

About equivalent interval colorings of weighted graphs

Given a graph G=(V,E) with strictly positive integer weights ω_i on the vertices iV, a k-interval coloring of G is a function I that assigns an interval I(i){1,…,k} of ω_i consecutive integers (called colors) to each vertex iV. If two adjacent vertices x and y have common colors, i.e. I(i)∩I(j)≠0/ for an edge [i,j] in G, then the edge [i,j] is said conflicting. A k-interval coloring without conflicting edges is said legal. The interval coloring problem (ICP) is to determine the smallest integer k, called interval chromatic number of G and denoted χ_int(G), such that there exists a legal k-interval coloring of G. For a fixed integer k, the k-interval graph coloring problem (k-ICP) is to determine a k-interval coloring of G with a minimum number of conflicting edges. The ICP and k-ICP generalize classical vertex coloring problems where a single color has to be assigned to each vertex (i.e., ω_i=1 for all vertices iV).Two k-interval colorings I₁ and I₂ are said equivalent if there is a permutation π of the integers 1,…,k such that ℓI₁(i) if and only if π(ℓ)I₂(i) for all vertices iV. As for classical vertex coloring, the efficiency of algorithms that solve the ICP or the k-ICP can be increased by avoiding considering equivalent k-interval colorings, assuming that they can be identified very quickly. To this purpose, we define and prove a necessary and sufficient condition for the equivalence of two k-interval colorings. We then show how a simple tabu search algorithm for the k-ICP can possibly be improved by forbidding the visit of equivalent solutions.     

Intersective polynomials and the polynomial Szemerédi theorem

Let be a family of polynomials such that , i=1,…,r. We say that the family P has the PSZ property if for any set with there exist infinitely many such that E contains a polynomial progression of the form {a,a+p₁(n),…,a+p_r(n)}. We prove that a polynomial family P={p₁,…,p_r} has the PSZ property if and only if the polynomials p₁,…,p_r are jointly intersective, meaning that for any there exists such that the integers p₁(n),…,p_r(n) are all divisible by k. To obtain this result we give a new ergodic proof of the polynomial Szemerédi theorem, based on the fact that the key to the phenomenon of polynomial multiple recurrence lies with the dynamical systems defined by translations on nilmanifolds. We also obtain, as a corollary, the following generalization of the polynomial van der Waerden theorem: If are jointly intersective integral polynomials, then for any finite partition of , there exist i{1,…,k} and a,nE_i such that {a,a+p₁(n),…,a+p_r(n)}E_i.     

On some d-dimensional dual hyperovals in

Let d≥3. Let H be a d+1-dimensional vector space over GF(2) and {e₀,…,e_d} be a specified basis of H. We define Supp(t){e_t1,…,e_tl}, a subset of a specified base for a non-zero vector t=e_t1++e_tl of H, and Supp(0)0/. We also define J(t)Supp(t) if |Supp(t)| is odd, and J(t)Supp(t){0} if |Supp(t)| is even.For s,tH, let {a(s,t)} be elements of H(HH) which satisfy the following conditions: (1) a(s,s)=(0,0), (2) a(s,t)=a(t,s), (3) a(s,t)≠(0,0) if s≠t, (4) a(s,t)=a(s^′,t^′) if and only if {s,t}={s^′,t^′}, (5) {a(s,t)|tH} is a vector space over GF(2), (6) {a(s,t)|s,tH} generate H(HH). Then, it is known that S{X(s)|sH}, where X(s){a(s,t)|tH{s}}, is a dual hyperoval in PG(d(d+3)/2,2)=(H(HH)){(0,0)}.In this note, we assume that, for s,tH, there exists some x_s,t in GF(2) such that a(s,t) satisfies the following equation: Then, we prove that the dual hyperoval constructed by {a(s,t)} is isomorphic to either the Huybrechts’ dual hyperoval, or the Buratti and Del Fra’s dual hyperoval.     

Strong Haagerup inequalities with operator coefficients

We prove a Strong Haagerup inequality with operator coefficients. If for an integer d, denotes the subspace of the von Neumann algebra of a free group F_I spanned by the words of length d in the generators (but not their inverses), then we provide in this paper an explicit upper bound on the norm on , which improves and generalizes previous results by Kemp–Speicher (in the scalar case) and Buchholz and Parcet–Pisier (in the non-holomorphic setting). Namely the norm of an element of the form ∑_{i=(i1,…,id)}a_iλ(g_i1g_id) is less than , where M₀,…,M_d are d+1 different block-matrices naturally constructed from the family (a_i)_iI^d for each decomposition of I^dI^l×I^d−l with l=0,…,d. It is also proved that the same inequality holds for the norms in the associated non-commutative L_p spaces when p is an even integer, pd and when the generators of the free group are more generally replaced by *-free -diagonal operators. In particular it applies to the case of free circular operators. We also get inequalities for the non-holomorphic case, with a rate of growth of order d+1 as for the classical Haagerup inequality. The proof is of combinatorial nature and is based on the definition and study of a symmetrization process for partitions.     

On the Positivity of the Fundamental Polynomials for Generalized Hermite–Fejér Interpolation on the Chebyshev Nodes

It is shown that the fundamental polynomials for (0, 1, …, 2m+1) Hermite–Fejér interpolation on the zeros of the Chebyshev polynomials of the first kind are non-negative for −1x1, thereby generalising a well-known property of the original Hermite–Fejér interpolation method. As an application of the result, Korovkin's 10theorem on monotone operators is used to present a new proof that the (0, 1, …, 2m+1) Hermite–Fejér interpolation polynomials offC[−1, 1], based onnChebyshev nodes, converge uniformly tofasn→∞.     

Determinants involving q-Stirling numbers

Let S[i,j] denote the q-Stirling numbers of the second kind. We show that the determinant of the matrix (S[s+i+j,s+j])_0i,jn is given by the product

Full-size image

. We give two proofs of this result, one bijective and one based upon factoring the matrix. We also prove an identity due to Cigler that expresses the Hankel determinant of q-exponential polynomials as a product. Lastly, a two variable version of a theorem of Sylvester and an application are presented.     

Generating random correlation matrices based on partial correlations

A d-dimensional positive definite correlation matrix R=(ρ_ij) can be parametrized in terms of the correlations ρ_i,i+1 for i=1,…,d-1, and the partial correlations ρ_{ij|i+1,…j-1} for j-i2. These parameters can independently take values in the interval (-1,1). Hence we can generate a random positive definite correlation matrix by choosing independent distributions F_ij, 1i<jd, for these parameters. We obtain conditions on the F_ij so that the joint density of (ρ_ij) is proportional to a power of det(R) and hence independent of the order of indices defining the sequence of partial correlations. As a special case, we have a simple construction for generating R that is uniform over the space of positive definite correlation matrices. As a byproduct, we determine the volume of the set of correlation matrices in -dimensional space. To prove our results, we obtain a simple remarkable identity which expresses det(R) as a function of ρ_i,i+1 for i=1,…,d-1, and ρ_{ij|i+1,…j-1} for j-i2.     

Linked graphs with restricted lengths

A graph G is k-linked if G has at least 2k vertices, and for every sequence x₁,x₂,…,x_k,y₁,y₂,…,y_k of distinct vertices, G contains k vertex-disjoint paths P₁,P₂,…,P_k such that P_i joins x_i and y_i for i=1,2,…,k. Moreover, the above defined k-linked graph G is modulo (m₁,m₂,…,m_k)-linked if, in addition, for any k-tuple (d₁,d₂,…,d_k) of natural numbers, the paths P₁,P₂,…,P_k can be chosen such that P_i has length d_i modulo m_i for i=1,2,…,k. Thomassen showed that, for each k-tuple (m₁,m₂,…,m_k) of odd positive integers, there exists a natural number f(m₁,m₂,…,m_k) such that every f(m₁,m₂,…,m_k)-connected graph is modulo (m₁,m₂,…,m_k)-linked. For m₁=m₂=…=m_k=2, he showed in another article that there exists a natural number g(2,k) such that every g(2,k)-connected graph G is modulo (2,2,…,2)-linked or there is XV(G) such that |X|4k−3 and G−X is a bipartite graph, where (2,2,…,2) is a k-tuple.We showed that f(m₁,m₂,…,m_k)max{14(m₁+m₂++m_k)−4k,6(m₁+m₂++m_k)−4k+36} for every k-tuple of odd positive integers. We then extend the result to allow some m_i be even integers. Let (m₁,m₂,…,m_k) be a k-tuple of natural numbers and ℓk such that m_i is odd for each i with ℓ+1ik. If G is 45(m₁+m₂++m_k)-connected, then either G has a vertex set X of order at most 2k+2ℓ−3+δ(m₁,…,m_ℓ) such that G−X is bipartite or G is modulo (2m₁,…,2m_ℓ,m_ℓ+1,…,m_k)-linked, where

Our results generalize several known results on parity-linked graphs.     

Positive periodic solutions of higher-dimensional functional difference equations with a parameter

By using Krasnoselskii's fixed point theorem and upper and lower solutions method, we find some sets of positive values λ determining that there exist positive T-periodic solutions to the higher-dimensional functional difference equations of the form where A(n)=diag[a₁(n),a₂(n),…,a_m(n)], h(n)=diag[h₁(n),h₂(n),…,h_m(n)], a_j,h_j :Z→R⁺, τ :Z→Z are T -periodic, j=1,2,…,m, T1, λ>0, x :Z→R^m, f :R₊^m→R₊^m, where R₊^m={(x₁,…,x_m)^TR^m, x_j0, j=1,2,…,m}, R⁺={xR, x>0}.     

On multipartite posets

A poset P=(X,) is m-partite if X has a partition X=X₁X_m such that (1) each X_i forms an antichain in P, and (2) xy implies xX_i and yX_j where i<j. In this article we derive a tight asymptotic upper bound on the order dimension of m-partite posets in terms of m and their bipartite sub-posets in a constructive and elementary way.     

On Equivalence of Moduli of Smoothness

It is known that iffW^k_p, thenω_m(f, t)_ptω_m−1(f′, t)_p…. Its inverse with any constants independent offis not true in general. Hu and Yu proved that the inverse holds true for splinesSwith equally spaced knots, thusω_m(S, t)_ptω_m−1(S′, t)_pt²ω_m−2(S″, t)_p…. In this paper, we extend their results to splines with any given knot sequence, and further to principal shift-invariant spaces and wavelets under certain conditions. Applications are given at the end of the paper.     

Group actions and invariants in algebras of generic matrices

We show that the fixed elements for the natural GL_m-action on the universal division algebra UD(m,n) of m generic n×n-matrices form a division subalgebra of degree n, assuming n3 and 2mn²−2. This allows us to describe the asymptotic behavior of the dimension of the space of SL_m-invariant homogeneous central polynomials p(X₁,…,X_m) for n×n-matrices. Here the base field is assumed to be of characteristic zero.     

Delay optimization of linear depth boolean circuits with prescribed input arrival times

We consider boolean circuits C over the basis Ω={,} with inputs x₁, x₂,…,x_n for which arrival times are given. For 1in we define the delay of x_i in C as the sum of t_i and the number of gates on a longest directed path in C starting at x_i. The delay of C is defined as the maximum delay of an input.Given a function of the form

f(x₁,x₂,…,x_n)=g_n−1(g_n−2(…g₃(g₂(g₁(x₁,x₂),x₃),x₄)…,x_n−1),x_n)