On the smallest limited snake of unit disks

A limited snake of size n is a set of nonoverlapping unit disks D ₁, ..., D _nwith centers c ₁, ..., c _nwhere the distances ¦c _i c _j¦=2 if and only if ¦i–j¦=1, and no disk can touch D ₁ or D _nwithout further common points with D ₁, ..., D _nThe size of the smallest limited snake is proved to be 10.     

Approximation by Fourier sums of classes of functions with several bounded derivatives

An ordered estimate is obtained for the approximation by Fourier sums, in the metric ofd=(d ₁ , ...,d _n ), 1<dj<,j=1, ...,_n of classes of periodic functions of several variables with zero means with respect to all their arguments, having m mixed derivatives of order a¹..., a^m., aⁱ rⁿ. which are bounded in the metrics ofp ⁱ =p ₁ ⁱ , ..., p _n ⁱ , i

j ⁱ <,i=i, ...,n, j=1, ...,n by the constants ₁, ., _m, respectively.Translated from Matematicheskie Zametki, Vol. 23, No. 2, pp. 197–212, February, 1978.     

Packing nearly-disjoint sets

De Bruijn and Erdős proved that ifA ₁, ...,A _k are distinct subsets of a set of cardinalityn, and |A _i ∩A _j |≦1 for 1≦i<j ≦k, andk>n, then some two ofA ₁, ...,A _k have empty intersection. We prove a strengthening, that at leastk /n ofA ₁, ...,A _k are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary. Partially supported by N. S. F. grant No. MCS—8103440     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

On Kendall's Process

LetZ₁, …, Z_nbe a random sample of sizen?2 from ad-variate continuous distribution functionH, and letV_i, nstand for the proportion of observationsZ_j,j≠i, such thatZ_j?Z_icomponentwise. The purpose of this paper is to examine the limiting behavior of the empirical distribution functionK_nderived from the (dependent) pseudo-observationsV_i, n. This random quantity is a natural nonparametric estimator ofK, the distribution function of the random variableV=H(Z), whose expectation is an affine transformation of the population version of Kendall's tau in the cased=2. Since the sample version ofτis related in the same way to the mean ofK_n, Genest and Rivest (1993,J. Amer. Statist. Assoc.) suggested that[formula]be referred to as Kendall's process. Weak regularity conditions onKandHare found under which this centered process is asymptotically Gaussian, and an explicit expression for its limiting covariance function is given. These conditions, which are fairly easy to check, are seen to apply to large classes of multivariate distributions.     

Scheduling jobs on heterogeneous processors

We consider the problem of schedulingn jobs nonpreemptively onm processors to minimize various weighted cost functions of job completion times. The time it takes processorj to process a job is distributed exponentially with rate parameter _j , independent of the other processors. Associated with jobi is a weightw _i . There are no precedence constraints and any job may be processed on any processor. Assume that _{1 2}...µ _m andw ₁w ₂...w _n . Then for certain weighted cost functions, the optimal policy is such that the processors can be partitioned into setsS ₁, ...,S _n+1 such that if the fastest available processor is in setS _i ,i=1, ...,n, then jobi should be assigned to it, and if it isS _n+1, it will never be used. After each assignment the jobs are renumbered (so that jobi+1 becomes jobi if jobi is assigned to a processor). The partitioning is independent of the job weights and the states (busy or idle) of the processors. The optimal policy can be determined in at most max {m, n} steps. If all the weights are identical, the optimal policy reduces to a simple threshold rule such that a job should be assigned to the fastest available processor, sayj, if there are more thanK _j jobs waiting.K _j will depend on ₁, ..., _j but not on _j+1, ...,µ _m . The optimal policy is also individually optimal in the sense that it minimizes the cost for each jobi subject to the constraint that processors will first be offered to the jobs in the order 1, 2, ...,n.We explicitly characterize the optimal policy for several specific examples of cost functions, such as weighted flow time, weighted discounted flowtime, and weighted number of tardy jobs.     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

Smooth convex bodies with proportional projection functions

For a convex body K ⊂ ℝⁿ and i ∈ {1, …, n − 1}, the function assigning to any i-dimensional subspace L of ℝⁿ, the i-dimensional volume of the orthogonal projection of K to L, is called the i-th projection function of K. Let K, K ₀ ⊂ ℝⁿ be smooth convex bodies with boundaries of class C ² and positive Gauss-Kronecker curvature and assume K ₀ is centrally symmetric. Excluding two exceptional cases, (i, j) = (1, n − 1) and (i, j) = (n − 2, n − 1), we prove that K and K ₀ are homothetic if their i-th and j-th projection functions are proportional. When K ₀ is a Euclidean ball this shows that a convex body with C ² boundary and positive Gauss-Kronecker with constant i-th and j-th projection functions is a Euclidean ball. The second author was supported in part by the European Network PHD, FP6 Marie Curie Actions, RTN, Contract MCRN-511953.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,x _k teX such thatx _i teE _j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday     

The solution of graham’s greatest common divisor problem

The following conjecture of R. L. Graham is verified: Ifn≧n ₀, wheren ₀ is an explicitly computable constant, then for anyn distinct positive integersa ₁,a ₂, ...,a _n we have a _i /(a _i ,a _j ) ≧ ≧n, and equality holds only in two trivial cases. Here (a _i ,a _j ) stands for the greatest cnmmon divisor ofa _i anda _j .     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Balancing vectors in the max norm

Let v₁, ..., v _n be vectors inR ⁿ of max norm at most one. It is proven that there exists a choice of signs for which all partial sums have max norm at mostKn ^1/2. It is further shown that such a choice of signs must be anticipatory—there is no way to choose thei-th sign without knowledge of v _j forj>i.     

Multiplicative isometries on the Smirnov class

We show that T is a surjective multiplicative (but not necessarily linear) isometry from the Smirnov class on the open unit disk, the ball, or the polydisk onto itself, if and only if there exists a holomorphic automorphism Φ such that T(f)=f ○ Φ for every class element f or T(f) = [`(f<sup>°</sup> [`(j)] )]\overline {f^\circ \bar \varphi } for every class element f, where the automorphism Φ is a unitary transformation in the case of the ball and Φ(z ₁, ..., z _n ) = (l₁ z_i1 ,...,l_n z_in )(\lambda _1 z_{i_1 } ,...,\lambda _n z_{i_n } ) for |λ _j | = 1, 1 ≤ j ≤ n, and (i ₁; ..., i _n )is some permutation of the integers from 1through n in the case of the n-dimensional polydisk.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

Asymptotic Behavior of the Maximum of Sums of I.I.D. Random Variables along Monotone Blocks

Let {X_i, Y_i}_i=1,2,... be an i.i.d. sequence of bivariate random vectors with P(Y₁ = y) = 0 for all y. Put M_n(j) = max_0≤k≤n-j (X_k+1 + ... X_k+j)I_k,j, where I_k,k+j = I{Y_k+1 < ⋯ < Y_k+j} denotes the indicator function for the event in brackets, 1 ≤ j ≤ n. Let L_n be the largest index l ≤ n for which I_k,k+l = 1 for some k = 0, 1, ..., n - l. The strong law of large numbers for “the maximal gain over the longest increasing runs,” i.e., for M_n(L_n) has been recently derived for the case where X₁ has a finite moment of order 3 + ε, ε > 0. Assuming that X₁ has a finite mean, we prove for any a = 0, 1, ..., that the s.l.l.n. for M(L_n - a) is equivalent to EX ₁ ^3+a I{X₁ > 0} < ∞. We derive also some new results for the a.s. asymptotics of L_n. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 311, 2004, pp. 179–189.     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

Full ideals of polynomial rings

An idealI of the ringK[x ₁, ...,x _n ] of polynomials over a fieldK inn indeterminates is a full ideal ifI is closed under substitution,f I,g ₁...g_n K[x ₁, ...,x _n ] implyf(g ₁, ...,g _n ) I. In this paper we continue the investigation of full ideals ofK[x ₁, ...,x _n ]. In particular we determine several classes of full ideals ofK[x, y] (K a finite field) and investigate properties of these classes.The first author gratefully acknowledges support from theDeutsche Forschungsgemeinschaft     

Fast formula of a reliability ofm-consecutive-k-out-of-n:F system with cyclek

Anm-consecutive-k-out-of-n:F system is a system ofn linearly arranged components which fails if and only if at leastm non-overlapping sequences ofk components fail, when there arek distinct components with failure probabilitiesq _i fori=1,...,k and where the failure probability of thej-th component (j=rk+i (1 ≤i ≤k) isq _j =q _i , we call this system by anm-consecutive-k-out-of-n:F system with cycle (or period)k. In this paper we give a formula of the failure probability ofm-consecutive-k-out-of-n:F system with cyclek via the failure probability of consecutive-k-out-of-n:F system.