Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.     

Representations of lattices via neutral elements

For any neutral element a in a bounded latticeL, the mapping x→(x∧,x∨a) representsL as a subdirect product of [0, a]×[a, 1]. It is first shown that for certain neutral elements, the image ofL under this mapping is completely determined by a homomorphism of [0, a] into [a, 1]. Iterating this process, a representation ofL can be obtained as a subdirect product of the intervals [a_i, a_i+1] for any chain 0=a₀1... nn+1=1 where each a_i is such a neutral element relative to [0, a_i+1]. The image in this case is completely determined by a family of homomorphisms π_i,j:A_i →A_j(ii=[a_i, a_i+1].     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

All rationals occur as exponents

For integers n ⩾k⩾ 1 and L ⊃ {0, 1,…, k − 1};, m(n, k, L) denotes the maximum number of k-subsets of an n-set so that the size of the intersection of any two among them is in L. It is proven that for every rational number r ⩾ 1 there is a choice of k and L so that cn^r < m(n, k, L) < dn^r, where c, d depend on k and L but not on n.     

On B(4, 13) 2-Groups

A group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j  | 1 ≤ i, j ≤ n}| ≤k. In this article, we give a complete characterization of B(4, 13) 2-groups, and then obtain a complete characterization of B(4, 13) groups.     

Fractional dimension of partial orders

Given a partially ordered setP=(X, ), a collection of linear extensions {L ₁,L ₂,...,L _r } is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL _i (andy<x in someL _j ). For a positive integerk, we call a multiset {L ₁,L ₂,...,L _t } ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL _i 's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research.     

Annihilators of Skew Derivations with Engel Conditions on Lie Ideals

Let R be a prime ring, L a noncentral Lie ideal of R, and a ∈ R. Set [x, y]₁ = [x, y] = xy ? yx for x, y ∈ R and inductively [x, y]_k = [[x, y]_k?1, y] for k > 1. Suppose that δ is a nonzero σ-derivation of R such that a[δ(x), x]_k = 0 for all x ∈ L, where σ is an automorphism of R and k is a fixed positive integer. Then a = 0 except when char R = 2 and R ? M₂(F), the 2 × 2 matrix ring over a field F.     

On the Expected Number of Shadow Vertices of the Convex Hull of Random Points

Leta₁, . . . ,a_mbe independent random points in ⁿthat are independent and identically distributed spherically symmetrical in ⁿ. Moreover, letXbe the random polytope generated as the convex hull ofa₁, . . . ,a_mand letL_kbe an arbitraryk-dimensional subspace of ⁿwith 2 ≤k≤n− 1. LetX_kbe the orthogonal projection image ofXinL_k. We call those vertices ofXwhose projection images inL_kare vertices ofX_kshadow vertices ofXwith respect to the subspaceL_k. We derive a distribution independent sharp upper bound for the expected number of shadow vertices ofXinL_k.     

Lower bounds for Turán's problem

Turán's problem is to determine the maximum numberT(n,k,t) oft-element subsets of ann-set without a complete sub-hypergraph onk vertices, i.e., allt-subsets of ak-set. It is proved that fora≥1 fixed andt sufficiently largeT(n, t+a,t)>(1-a(a+4+o(1))logt/( _a ^t )( _t ⁿ holds     

Linkage between Adiabatic Invariance and Symmetry of Solutions

In this article, for the symmetric pendulum equation and the symmetric bisuperlinear equation respectively, we show that there are two one-parameter families of solutions, y_s and y_a, so that one is adiabatically symmetric, y_s(?t)=y_s(t)+o(ε^k) for all k≥0, and the other adiabatically antisymmetric, y_a(?t)=?y_a(t)+o(ε^k) for all k≥0. By using the techniques of exponential asymptotics to calculate y′_s(0) and y_a(0), we demonstrate that, in general, they are not genuinely symmetric or antisymmetric, because these quantities are in fact exponentially small. Finally, after establishing a relationship between the total change in the leading-order adiabatic invariant and the quantity y′_s(0) for the family of solutions y_s of the bisuperlinear equation, we are able to reveal explicitly how the behavior of the adiabatic invariant depends on the complex singularities of the equation.      

NON-EMPTY CROSS-2-INTERSECTING FAMILIES OF SUBSETS

Let Cdenote the set of all k-subests of an n-set.Assume Alohtain in Ca,and A lohtain in (A,B) is called a cross-2-intersecting family if |A B≥2 for and A∈A,B∈B.In this paper,the best upper bounds of the cardinalities for non-empty cross-2-intersecting familles of a-and b-subsets are obtained for some a and b,A new proof for a Frankl-Tokushige theorem[6] is also given.     

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.     

Very Asymmetric Marking Games

We investigate a competitive version of the coloring number of a graph G = (V, E). For a fixed linear ordering L of V let s (L) be one more than the maximum outdegree of G when G is oriented so that x ← y if x < _L y. The coloring number of G is the minimum of s (L) over all such orderings. The (a, b)-marking game is played on a graph G = (V, E) as follows. At the start all vertices are unmarked. The players, Alice and Bob, take turns playing. A play consists of Alice marking a unmarked vertices or Bob marking b unmarked vertices. The game ends when there are no remaining unmarked vertices. Together the players create a linear ordering L of V defined by x < y if x is marked before y. The score of the game is s (L). The (a, b)-game coloring number of G is the minimum score that Alice can obtain regardless of Bob’s strategy. The usual (1, 1)-marking game is well studied and there are many interesting results. Our main result is that if G has an orientation with maximum outdegree k then the (k, 1)-game coloring number of G is at most 2k + 2. This extends a fundamental result on the (1, 1)-game coloring number of trees. We also construct examples to show that this bound is tight for many classes of graphs. Finally we prove bounds on the (a, 1)-game coloring number when a < k.     

Spectral parameter power series for arbitrary order linear differential equations

Let L be the n‐th order linear differential operator Ly=?₀y⁽ⁿ⁾+?₁y^(n?1)+?+?_ny with variable coefficients. A representation is given for n linearly independent solutions of Ly=λry as power series in λ, generalizing the SPPS (spectral parameter power series) solution that has been previously developed for n=2. The coefficient functions in these series are obtained by recursively iterating a simple integration process, beginning with a solution system for λ=0. It is shown how to obtain such an initializing system working upwards from equations of lower order. The values of the successive derivatives of the power series solutions at the basepoint of integration are given, which provides a technique for numerical solution of n‐th order initial value problems and spectral problems.     

The asymptotic formula in Waring’s problem for one square and seventeen fifth powers

Let R _k,s (n) denote the number of solutions of the equation n = x² + y₁^k + y₂^k + ?+ y_s^k{n= x^2 + y_1^k + y_2^k + \cdots + y_s^k} in natural numbers x, y ₁, . . . , y _s . By a straightforward application of the circle method, an asymptotic formula for R _k,s (n) is obtained when k ≥ 3 and s ≥ 2 ^k–1 + 2. When k ≥ 6, work of Heath-Brown and Boklan is applied to establish the asymptotic formula under the milder constraint s ≥ 7 · 2 ^k–4 + 3. Although the principal conclusions provided by Heath-Brown and Boklan are not available for smaller values of k, some of the underlying ideas are still applicable for k = 5, and the main objective of this article is to establish an asymptotic formula for R _5,17(n) by this strategy.     

Quadrature based collocation methods for integral equations of the first kind

Problem of solving integral equations of the first kind, ò_a^b k(s, t) x(t) dt = y(s), s ? [a, b]\int_a^b k(s, t) x(t)\, dt = y(s),\, s\in [a, b] arises in many of the inverse problems that appears in applications. The above problem is a prototype of an ill-posed problem. Thus, for obtaining stable approximate solutions based on noisy data, one has to rely on regularization methods. In practice, the noisy data may be based on a finite number of observations of y, say y(τ ₁), y(τ ₂), ..., y(τ _n ) for some τ ₁, ..., τ _n in [a, b]. In this paper, we consider approximations based on a collocation method when the nodes τ ₁, ..., τ _n are associated with a convergent quadrature rule. We shall also consider further regularization of the procedure and show that the derived error estimates are of the same order as in the case of Tikhonov regularization when there is no approximation of the integral operator is involved.     

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

Approximation ofk-Monotone Functions

It is shown that an algebraic polynomial of degree k−1 which interpolates ak-monotone functionfatkpoints, sufficiently approximates it, even if the points of interpolation are close to each other. It is well known that this result is not true in general for non-k-monotone functions. As an application, we prove a (positive) result on simultaneous approximation of ak-monotone function and its derivatives inL_p, 0<p<1, metric, and also show that the rate of the best algebraic approximation ofk-monotone functions (with bounded (k−2)nd derivatives inL_p, 1<p<∞, iso(n^−k/p).     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

The asymptotic behavior of nonoscillatory solutions of nonlinear neutral type difference equations

In this paper, the authors study the asymptotic behavior of solutions of second-order neutral type difference equations of the form

Δ²(y_n+py_n−k)+f(n,y_n−ℓ)=0,n