Spaces with large projection constants

For every prime numberk, we give an explicit construction of a complexk-dimensional spaceX _k with projection constantγ(X _k ) = √k − 1/√k + 1/k. Moreover, there are realk-dimensional spacesX _k withγ(x _K ) ≧ √k − 1 for a subsequence of integersk. Hence in both casesγ(X _k )/√k → 1 which is the maximal possible value sinceγ(X _k ) ≦ √k is generally true.     

Generating-Tree Isomorphisms for Pattern-Avoiding Involutions

We show that for k ≥ 5 and the permutations τ _k = (k − 1)k(k − 2). . .312 and J _k = k(k − 1). . .21, the generating tree for involutions avoiding the pattern τ _k is isomorphic to the generating tree for involutions avoiding the pattern J _k . This implies a family of Wilf equivalences for pattern avoidance by involutions.     

Generalization of the fricke theorem on entire functions of finite index

We prove that, for every sequence (a _k) of complex numbers satisfying the conditions Σ(1/|a _k |) < ∞ and |a _k+1| − |a _k | ↗ ∞ (k → ∞), there exists a continuous functionl decreasing to 0 on [0, + ∞] and such thatf(z) = Π(1 −z/|a _k |) is an entire function of finitel-index.     

Sum Complexes—a New Family of Hypertrees

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k−1)-dimensional skeleton and \binomn-1k\binom{n-1}{k} facets such that H _k (X;ℚ)=0. Here we introduce the following family of simplicial complexes. Let n,k be integers with k+1 and n relatively prime, and let A be a (k+1)-element subset of the cyclic group ℤ _n . The sum complex X _A is the pure k-dimensional complex on the vertex set ℤ _n whose facets are σ⊂ℤ _n such that |σ|=k+1 and ∑ _x∈σ x∈A. It is shown that if n is prime, then the complex X _A is a k-hypertree for every choice of A. On the other hand, for n prime, X _A is k-collapsible iff A is an arithmetic progression in ℤ _n .     

Minimum nastiness curve fitting

The ‘nastiness’ of a function φ(x) is defined. We then discuss minimum nastiness interpolation to a set of given points (x _k, φ_k), as well as minimum nastiness curve fitting, where the given valuesφ _k have errorsδ _k.     

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β _k is computed as a convex combination of b_k^HS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and b_k^DY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. b_k^C = (1-q_k)b_k^HS + q_k b_k^DY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ _k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s _k , y _k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B _k + 1 s _k  = z _k , where z_k = y_k +(h_k / || s_k ||² )s_kz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, h_k = 2( f_k -f_k+1 )+( g_k +g_k+1 )^Ts_k\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s _k  = x _k + 1 − x _k and y _k  = g _k + 1 − g _k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α _k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s _k , y _k ) satisfies the classical secant condition B _k + 1 s _k  = y _k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).     

The Subadditive Ergodic Theorem and generic stretching factors for free group automorphisms

Let F _k be a free group of rank k ≥ 2 with a fixed set of free generators. We associate to any homomorphism φ from F _k to a group G with a left-invariant semi-norm a generic stretching factor, λ(φ), which is a noncommutative generalization of the translation number. We concentrate on the situation where φ: F _k → Aut(X) corresponds to a free action of F _k on a simplicial tree X, in particular, where φ corresponds to the action of F _k on its Cayley graph via an automorphism of F _k . In this case we are able to obtain some detailed “arithmetic” information about the possible values of λ = λ(φ). We show that λ ≥ 1 and is a rational number with 2kλ ∈ ℤ[1/(2k − 1)] for every φ ∈ Aut(F _k ). We also prove that the set of all λ(φ), where φ varies over Aut(F _k ), has a gap between 1 and 1+(2k−3)/(2k ²−k), and the value 1 is attained only for “trivial” reasons. Furthermore, there is an algorithm which, when given φ, calculates λ(φ). The second and the third author were supported by the NSF grant DMS#0404991 and the NSA grant DMA#H98230-04-1-0115.     

S-forcing,I. A “black-box” theorem for morasses,with applications to super-Souslin trees

We formulate, for regular μ>ω, a “forcing principle” S_μ which we show is equivalent to the existence of morasses, thus providing a new and systematic method for obtaining applications of morasses. Various examples are given, notably that for infinitek, if 2 ^k =k ⁺ and there exists a (k ⁺, 1)-morass, then there exists ak ⁺⁺-super-Souslin tree: a normalk ⁺⁺ tree characterized by a highly absolute “positive” property, and which has ak ⁺⁺-Souslin subtree. As a consequence we show that CH+SH_{ℵ 2}⟹ℵ₂ is (inaccessible)^L. This author thanks the US-Israel Binational Science Foundation for partial support of this research.     

Hypergraphs with independent neighborhoods

For each k ≥ 2, let ρ _k ∈ (0, 1) be the largest number such that there exist k-uniform hypergraphs on n vertices with independent neighborhoods and (ρ _k + o(1))( _k ⁿ ) edges as n → ∞. We prove that ρ _k = 1 − 2logk/k + Θ(log log k/k) as k → ∞. This disproves a conjecture of Füredi and the last two authors.     

An Eberhard-Like Theorem for Pentagons and Heptagons

Eberhard proved that for every sequence (p _k ), 3≤k≤r, k≠6, of nonnegative integers satisfying Euler’s formula ∑ _k≥3(6−k)p _k =12, there are infinitely many values p ₆ such that there exists a simple convex polyhedron having precisely p _k faces of size k for every k≥3, where p _k =0 if k>r. In this paper we prove a similar statement when nonnegative integers p _k are given for 3≤k≤r, except for k=5 and k=7 (but including p ₆). We prove that there are infinitely many values p ₅,p ₇ such that there exists a simple convex polyhedron having precisely p _k faces of size k for every k≥3. We derive an extension to arbitrary closed surfaces, yielding maps of arbitrarily high face-width. Our proof suggests a general method for obtaining results of this kind.     

Selection from poisson processes

Summary There are givenk Poisson processes with mean arrival times 1/λ₁,...1/λ _k . Let λ_[1]≦λ_[2]≦...≦λ_[k] denote the ordered set of values λ₁...,λ_[k]. We consider three procedures for selecting the process corresponding to λ_[k]. The processes are observed until there areN arrivals from any of the given processes, when the processes are observed continuously, or until there are at leastN arrivals, when the processes are observed at successive intervals of time whereN is a pre-determined positive integer. In the continuous case, the process for which theNth arrival time is shortest, is selected. In the discrete case, the selection involves certain randomization. Given (λ_[k]/λ_[k-1])≧0>1, it is shown that the probability of a correct selection (Pcs) is minimized whenθλ_[1]=θλ_[2]=...=θλ_[k-1]=θλ_[k]=θλ, say. The Pcs for this configuration is independent of λ for two of the given procedures, and monotone increasing in λ for the third. The value ofN is determined by a lower bound placed on the value of the Pcs. The problem of selecting from given Poisson processes for the discrete case is related to the problem of selecting from given Poisson populations. An application of the given procedures to a problem of selecting the “most probable event” from a multinomial population, is considered.     

Generalized absolutely monotone functions

The concept of absolutely monotone functions is generalized by replacing the conditionsφ ^(k)(t)≧0,k=0, 1, … by an infinite sequence of differential inequalitiesφ(t)≧0,L _kφ(t)≧0,k=1, 2, …, where theL _k are differential operators of a special type. It is shown that these functions have a valid series expansion in terms of basic functions associated with the operatorsL _k.     

Ideal einstein,conformally flat and semi-symmetric immersions

Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR ^m (ε) of constant sectional curvature ε satisfies a basic inequality δ(n ₁,…,n _k )≤c(n ₁,…,n _k )H ²+b(n ₁,…,n _k )ε, whereH is the mean curvature of the immersion, andc(n ₁,…,n _k ) andb(n ₁,…,n _k ) are constants depending only onn ₁,…,n _k ,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n ₁,…,n _k ). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n ₁+…+n _k +1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n ₁+…+n _k +2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms. The author was supported by the NSFC and RFDP.     

On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

The continuity of superposition operators on some sequence spaces defined by moduli

Let λ and μ be solid sequence spaces. For a sequence of modulus functions Φ = (ϕ k) let λ(Φ) = {x = (x _k ): (ϕk(|x _k |)) ∈ λ}. Given another sequence of modulus functions Ψ = (ψ_k), we characterize the continuity of the superposition operators P _f from λ(Φ) into μ (Ψ) for some Banach sequence spaces λ and μ under the assumptions that the moduli ϕk (k ∈ ℕ) are unbounded and the topologies on the sequence spaces λ(Φ) and μ(Ψ) are given by certain F-norms. As applications we consider superposition operators on some multiplier sequence spaces of Maddox type. This research was supported by Estonian Science Foundation Grant 5376.     

Mirror symmetry for Del Pezzo surfaces: Vanishing cycles and coherent sheaves

We study homological mirror symmetry for Del Pezzo surfaces and their mirror Landau-Ginzburg models. In particular, we show that the derived category of coherent sheaves on a Del Pezzo surface X _k obtained by blowing up ℂℙ² at k points is equivalent to the derived category of vanishing cycles of a certain elliptic fibration W _k :M _k →ℂ with k+3 singular fibers, equipped with a suitable symplectic form. Moreover, we also show that this mirror correspondence between derived categories can be extended to noncommutative deformations of X _k , and give an explicit correspondence between the deformation parameters for X _k and the cohomology class [B+iω]∈H ²(M _k ,ℂ).     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.