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.     

On the length of the tail of a vector space partition

A vector space partition of a finite dimensional vector space V=V(n,q) of dimension n over a finite field with q elements, is a collection of subspaces U₁,U₂,…,U_t with the property that every non zero vector of V is contained in exactly one of these subspaces. The tail of consists of the subspaces of least dimension d₁ in , and the length n₁ of the tail is the number of subspaces in the tail. Let d₂ denote the second least dimension in .Two cases are considered: the integer q^d₂−d₁ does not divide respective divides n₁. In the first case it is proved that if 2d₁>d₂ then n₁≥q^d₁+1 and if 2d₁≤d₂ then either n₁=(q^d₂−1)/(q^d₁−1) or n₁>2q^d₂−d₁. These lower bounds are shown to be tight and the elements in the subspaces in tails of minimal length will constitute a subspace of V of dimension 2d₁ respectively d₂.In case q^d₂−d₁ divides n₁ it is shown that if d₂<2d₁ then n₁≥q^d₂−q^d₁+q^d₂−d₁ and if 2d₁≤d₂ then n₁≥q^d₂. The last bound is also shown to be tight.The results considerably improve earlier found lower bounds on the length of the tail.     

Lower bounds for the cardinality of minimal blocking sets in projective spaces

In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r₂(q) be the number such that q+r₂(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most q^m+q^m−1+…+q+1+r₂(q)·(∑_i=2m−n′^m−1qⁱ) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals q^m+q^m−1+…+q+1+r₂(q)(∑_i=2m−n′^m−1qⁱ). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<q^m+q^m−1+…+q+1+r₂(q)(q^m−1+q^m−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. For q=p^3h, p7 and q not a square we show this assertion for |B|q^m+q^m−1+…+q+1+q^2/3·(q^m−1+…+1).     

Generalizations of Heilbronn’s triangle problem

For given integers d,j≥2 and any positive integers n, distributions of n points in the d-dimensional unit cube [0,1]^d are investigated, where the minimum volume of the convex hull determined by j of these n points is large. In particular, for fixed integers d,k≥2 the existence of a configuration of n points in [0,1]^d is shown, such that, simultaneously for j=2,…,k, the volume of the convex hull of any j points among these n points is Ω(1/n^{(j−1)/(1+|d−j+1|)}). Moreover, a deterministic algorithm is given achieving this lower bound, provided that d+1≤j≤k.     

On the Rate of Approximation of Closed Jordan Curves by Lemniscates

As proved by Hilbert, it is, in principle, possible to construct an arbitrarily close approximation in the Hausdorff metric to an arbitrary closed Jordan curve Γ in the complex plane {z} by lemniscates generated by polynomials P(z). In the present paper, we obtain quantitative upper bounds for the least deviations H _n (Γ) (in this metric) from the curve Γ of the lemniscates generated by polynomials of a given degree n in terms of the moduli of continuity of the conformal mapping of the exterior of Γ onto the exterior of the unit circle, of the mapping inverse to it, and of the Green function with a pole at infinity for the exterior of Γ. For the case in which the curve Γ is analytic, we prove that H _n (Γ) = O(q _n ), 0 ≤ q = q(Γ) < 1, n → ∞.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 861–876.Original Russian Text Copyright ©2005 by O. N. Kosukhin.     

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality isd^O(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set ofnpoints and finding the maximum volume ellipsoid in the intersection ofnhalfspaces.     

Global nonparametric estimation of conditional quantile functions and their derivatives

Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (p − m)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X₁, Y₁), …, (X_n, Y_n), that achieves the optimal nonparametric rate of convergence n^−r in L_q-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)^−r in L_∞-norm restricted to compacts.     

The Fine Structure of the n-Widths of H-Spaces in Lq(−1, 1)

The n-widths of the unit ball A_p of the Hardy space H^p in L_q( −1, 1) are determined asymptotically. It is shown that for 1 ≤ q < p ≤∞ there exist constants k₁ and k₂ such that [formula]≤ d_n(A_p, L_q(−1, 1)),dⁿ(A_p, L_q(−1, 1)), δ_n(A_p, L_q(−1, 1))[formula]where d_n, dⁿ, and δ_n denote the Kolmogorov, Gel′fand and linear n-widths, respectively. This result is an improvement of estimates previously obtained by Burchard and Höllig and by the author.     

On the Multiplicities of the Primitive Idempotents of a Q-Polynomial Distance-regular Graph

Ito, Tanabe and Terwilliger recently introduced the notion of a tridiagonal pair. We apply their results to distance-regular graphs and obtain the following theorem.Theorem Let Γ denote a distance-regular graph with diameter D ≥  3. Suppose Γ is Q -polynomial with respect to the orderingE₀ , E₁, , E_Dof the primitive idempotents. For 0  ≤  i ≤  D, let m_idenote the multiplicity ofE_i . Then (i)m_i − 1 ≤ m_i (1  ≤  i ≤  D / 2),(ii)m_i  ≤ m_D − i (0  ≤  i ≤ D  / 2).By proving the above theorem we resolve a conjecture of Dennis Stanton.     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

Classification of Embeddings of the Flag Geometries of Projective Planes in Finite Projective Spaces, Part 2

The flag geometry Γ=( ,  , I) of a finite projective plane Π of order s is the generalized hexagon of order (s, 1) obtained from Π by putting equal to the set of all flags of Π, by putting equal to the set of all points and lines of Π, and where I is the natural incidence relation (inverse containment), i.e., Γ is the dual of the double of Π in the sense of H. Van Maldeghem (1998, “Generalized Polygons,” Birkhäuser Verlag, Basel). Then we say that Γ is fully and weakly embedded in the finite projective space PG(d, q) if Γ is a subgeometry of the natural point-line geometry associated with PG(d, q), if s=q, if the set of points of Γ generates PG(d, q), and if the set of points of Γ not opposite any given point of Γ does not generate PG(d, q). In two earlier papers we have shown that the dimension d of the projective space belongs to {6, 7, 8}, that the projective plane Π is Desarguesian, and we have classified the full and weak embeddings of Γ (Γ as above) in the case that there are two opposite lines L, M of Γ with the property that the subspace U_L, M of PG(d, q) generated by all lines of Γ meeting either L or M has dimension 6 (which is automatically satisfied if d=6). In the present paper, we partly handle the case d=7; more precisely, we consider for d=7 the case where for all pairs (L, M) of opposite lines of Γ, the subspace U_L, M has dimension 7 and where there exist four lines concurrent with L contained in a 4-dimensional subspace of PG(7, q).     

RELATIVE WIDTH OF SMOOTH CLASSES OF MULTIVARIATE PERIODIC FUNCTIONS WITH RESTRICTIONS ON ITERATED LAPLACE DERIVATIVES IN THE L2-METRIC

For two subsets W and V of a Banach space X, let Kn(W, V, X) denote the relative Kolmogorov n-width of W relative to V defined by Kn (W, V, X) := inf sup Ln f∈W g∈V∩Ln inf ‖f-g‖x,where the infimum is taken over all n-dimensional linear subspaces Ln of X. Let W2(△r) denote the class of 2w-periodic functions f with d-variables satisfying ∫[-π,π]d |△rf(x)|2dx ≤ 1,while △r is the r-iterate of Laplace operator △. This article discusses the relative Kolmogorov n-width of W2(△r) relative to W2(△r) in Lq([-r, πr]d) (1 ≤ q ≤∞), and obtain its weak asymptotic result.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

Nonexistence of [n, 5, d]q Codes Attaining the Griesmer Bound for q4 ?2q2 ?2q+1 ≤ d≤ q4?2q2 ?q

We prove that there does not exist a [q⁴+q³−q²−3q−1, 5, q⁴−2q²−2q+1]_q code over the finite field for q≥ 5. Using this, we prove that there does not exist a [g_q(5, d), 5, d]_q code with q⁴ −2q² −2q +1 ≤ d ≤ q⁴ −2q² −q for q≥ 5, where g_q(k,d) denotes the Griesmer bound.MSC 2000: 94B65, 94B05, 51E20, 05B25     

Tails of Bipartite Distance-regular Graphs

Let Γ denote a bipartite distance-regular graph with diameterD  ≥  4 and valency k ≥  3. Let θ 0  > θ 1  >  >  θD denote the eigenvalues of Γ and let E₀, E₁, , E_Ddenote the associated primitive idempotents. Fix s(1  ≤  s ≤  D −  1 ) and abbreviate E: =  E_s. We say E is a tail whenever the entrywise product E   E is a linear combination of E₀, E and at most one other primitive idempotent of Γ. Letq_ij^{σi + 1 h} (0  ≤ h , i, j ≤  D) denote the Krein parameters of Γ and letΔ denote the undirected graph with vertices 0, 1, , D where two vertices i, j are adjacent whenever i ≠  =  j andq_ij^σi + 1s  ≠  =  0. We show E is a tail if and only if one of (i)–(iii) holds: (i) Δ is a path; (ii) Δ has two connected components, each of which is a path; (iii) D =  6 and Δ has two connected components, one of which is a path on four vertices and the other of which is a clique on three vertices.     

Prophet regions and sharp inequalities for pth absolute moments of martingales

Exact comparisons are made relating E|Y₀|^p, E|Y_n−1|^p, and E(max_j≤n−1 |Y_j|^p), valid for all martingales Y₀,…,Y_n−1, for each p ≥ 1. Specifically, for p > 1, the set of ordered triples {(x, y, z) : X = E|Y₀|^p, Y = E |Y_n−1|^p, and Z = E(max_j≤n−1 |Y_j|^p) for some martingale Y₀,…,Y_n−1} is precisely the set {(x, y, z) : 0≤x≤y≤z≤Ψ_n,p(x, y)}, where Ψ_n,p(x, y) = xψ_n,p(y/x) if x > 0, and = a_n−1,py if x = 0; here ψ_n,p is a specific recursively defined function. The result yields families of sharp inequalities, such as E(max_j≤n−1 |Y_j|^p) + ψ_n,p^*(a) E |Y₀|^p ≤ aE |Y_n−1|^p, valid for all martingales Y₀,…,Y_n−1, where ψ_n,p^* is the concave conjugate function of ψ_n,p. Both the finite sequence and infinite sequence cases are developed. Proofs utilize moment theory, induction, conjugate function theory, and functional equation analysis.     

Unique representation of primitive factors of 2 n −1,n ODD,in certain quadratic forms

Primitive factorsq of 2 ⁿ –1,n odd, are either of the form 8m–1 or 8m+1. In the first case there exists a unique representation ofq in the quadratic forma ²–2b ², (a, b)=1,a andb odd,b<[q/2], and in the latter a unique representation ofq in the quadratic formc ²+2 ^j d², (c, d)=1,c andd odd,j even and 6. Thus the uniqueness ofq=a ²–2b ² orc ²+2 ^j d² exhibits a proof of the primality ofq.A program that determinesa, b, c, andd for anyq not exceeding 16 decimal digits is described, and as an example the 13-digit prime 4432676798593 (a primitive factor of 2⁴⁹–1) is uniquely represented by 1374273²+2¹⁴·12461².     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

A Bose-Burton Theorem for Elliptic Polar Spaces

In bose&burton, Bose and Burton determined the smallest point sets of PG(d, q) that meet every subspace of PG(d, q) of a given dimension c. In this paper an equivalent result for quadrics of elliptic type is obtained. It states the folloing. For 0 c n - 1 the smallest point set of the elliptic quadric Q ^-(2n + 1, q) that meets every singular subspace of dimension c of Q ^-(2n + 1, q) has cardinality (q ⁿ⁺¹ + q ^c )(q ^n-c - 1)/(q - 1). Furthermore, the point sets of the smallest cardinality are classified.     

Cyclic Difference Packing and Covering Arrays

Let n and k be positive integers. Let C_q be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (a_ij) with entries a_ij (0 ≤ i ≤ k−1, 0 ≤ j ≤ n−1) from C_q such that, for any two rows t and h (0 ≤ t < h ≤ k−1), every element of C_q occurs in the difference list at most (at least) once. When q is even, then n ≤ q−1 if a CDPA(k, n; q) with k ≥ 3 exists, and n ≥ q+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right.