Bounds on absorption times of directionally biased random sequences

A sequence of random variables X₀,X₁, … with values in {0, 1, …, n} representing a general finite-state stochastic process with absorbing state 0 is said to be directionally biased towards 0, if, for all j > 0, ϵ_j: = inf_k>0 {j − E[X_k | X_k−1 = j]} > 0. For such sequences, let t be the expected value of the time to absorption at 0. For a fixed set of biases, the least upper bound for this time can be computed with an algorithm requiring O(n²) steps. Simple upper bounds are described. In particular, t ≤ E[b_x0], where b_i = Σ_j≤i 1/¯ϵ_j and ¯ϵ_j = min_l≥j {ϵ_l}. If all ϵ_j ≤ ϵ_{j + 1} (so ¯ϵ_j = ϵ_j) and ϵ_n < 1, this bound for t is the best possible. For certain finite stochastic processes which we term conditionally independent of X₀ = i, b(i) bounds the expected time given X₀ = i. Similar results are given for lower bounds. The results of this paper were designed to be a useful tool for determining rates of convergence of stochastic optimization algorithms. © 1996 John Wiley & Sons, Inc.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Small deviations of the maximal element of a sequence of weighted independent random variables

Consider a sequence {X _i } of independent copies of a nonnegative random variable X and let M = sup _{j ≥ 1}λ _j X _j , where {λ _j } is a nonincreasing sequence of positive numbers for which P(M < ∞) = 1. The asymptotic behavior of -logP(M < r) as r → 0 is studied.     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

Bipartite Graphs Whose Edge Algebras Are Complete Intersections

Let R be a monomial subalgebra of k[x₁,…,x_N] generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x₁,…,x_N and whose edges are {(x_i, x_j)|x_ix_j  R}. Conversely, for any graph G with vertices {x₁,…,x_N} we define the edge algebra associated with G as the subalgebra of k[x₁,…,x_N] generated by the monomials {x_ix_j|(x_i, x_j) is an edge of G}. We denote this monomial algebra by k[G]. This paper describes all bipartite graphs whose edge algebras are complete intersections.     

On metric spaces with the properties of de Groot and Nagata in dimension one

A metric space (X,d) has the de Groot property GPn if for any points x₀,x₁,…,xn+2∈X there are positive indices i,j,k?n+2 such that i≠j and d(xi,xj)?d(x₀,xk). If, in addition, k∈{i,j} then X is said to have the Nagata property NPn. It is known that a compact metrizable space X has dimension dim(X)?n iff X has an admissible GPn-metric iff X has an admissible NPn-metric.We prove that an embedding f:(0,1)→X of the interval (0,1)⊂R into a locally connected metric space X with property GP₁ (resp. NP₁) is open, provided f is an isometric embedding (resp. f has distortion Dist(f)=‖fLip_‖⋅‖f−1Lip_‖<2). This implies that the Euclidean metric cannot be extended from the interval [−1,1] to an admissible GP₁-metric on the triode T=[−1,1]∪[0,i]. Another corollary says that a topologically homogeneous GP₁-space cannot contain an isometric copy of the interval (0,1) and a topological copy of the triode T simultaneously. Also we prove that a GP₁-metric space X containing an isometric copy of each compact NP₁-metric space has density ?c.     

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     

On Hong’s conjecture for power LCM matrices

A set S={x ₁,...,x _n } of n distinct positive integers is said to be gcd-closed if (x _i , x _j ) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x _i , x _j ] ^t ) defined on any gcd-closed set S={x ₁,...,x _n } is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x ₁,...,x _n } such that the power LCM matrix ([x _i , x _j ] ^t ) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2.     

Oberwolfach rectangular table negotiation problem

We completely solve certain case of a “two delegation negotiation” version of the Oberwolfach problem, which can be stated as follows. Let H(k,3) be a bipartite graph with bipartition X={x₁,x₂,…,x_k},Y={y₁,y₂,…,y_k} and edges x₁y₁,x₁y₂,x_ky_k−1,x_ky_k, and x_iy_i−1,x_iy_i,x_iy_i+1 for i=2,3,…,k−1. We completely characterize all complete bipartite graphs K_n,n that can be factorized into factors isomorphic to G=mH(k,3), where k is odd and mH(k,3) is the graph consisting of m disjoint copies of H(k,3).     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

Clustering of linearly interacting diffusions and universality of their long-time limit distribution

Let K⊂ℝ ^d (d≥ 1) be a compact convex set and Λ a countable Abelian group. We study a stochastic process X in K ^Λ, equipped with the product topology, where each coordinate solves a SDE of the form dX _i (t) = ∑ _j a(j−i) (X _j (t) −X _i (t))dt + σ (X _i (t))dB _i (t). Here a(·) is the kernel of a continuous-time random walk on Λ and σ is a continuous root of a diffusion matrix w on K. If X(t) converges in distribution to a limit X(∞) and the symmetrized random walk with kernel a _S (i) = a(i) + a(−i) is recurrent, then each component X _i (∞) is concentrated on {x∈K : σ(x) = 0 and the coordinates agree, i.e., the system clusters. Both these statements fail if a _S is transient. Under the assumption that the class of harmonic functions of the diffusion matrix w is preserved under linear transformations of K, we show that the system clusters for all spatially ergodic initial conditions and we determine the limit distribution of the components. This distribution turns out to be universal in all recurrent kernels a _S on Abelian groups Λ. Received: 10 May 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000     

A parallel selection algorithm

The problem of selecting thekth largest or smallest element of {x _i +y _j |x _i X andy _j Y i,j} whereX=(x ₁,x ₂, ..,x _n ) andY=(y ₁,y ₂, ...,y _n ) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n ^1+1/) processors is presented where is a pre-assigned constant lying between 1 and 2.     

Estimation of the Location of the Maximum of a Regression Function Using Extreme Order Statistics

In this paper, we consider the problem of approximating the location,x₀∈C, of a maximum of a regresion function,θ(x), under certain weak assumptions onθ. HereCis a bounded interval inR. A specific algorithm considered in this paper is as follows. Taking a random sampleX₁, …, X_nfrom a distribution overC, we have (X_i, Y_i), whereY_iis the outcome of noisy measurement ofθ(X_i). Arrange theY_i's in nondecreasing order and take the average of ther X_i's which are associated with therlargest order statistics ofY_i. This average,x₀, will then be used as an estimate ofx₀. The utility of such an algorithm with fixed r is evaluated in this paper. To be specific, the convergence rates ofx₀tox₀are derived. Those rates will depend on the right tail of the noise distribution and the shape ofθ(·) nearx₀.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

A determinantal description of GCD-closed sets and k-sets

Let S={x ₁,x ₂,…,x_n } be a naturally ordered set of distinct positive integers. S is called a k-set if k= gcd(x_i ,x_j ) for x_i ≠x_j any in S. In this paper k-sets are characterized by certain conditions on the determinants of some matrices associated with S.     

Exact laws for sums of ratios of order statistics from the Pareto distribution

Consider independent and identically distributed random variables {X _nk, 1 ≤ k ≤ m, n ≤ 1} from the Pareto distribution. We select two order statistics from each row, X _n(i) ≤ X _n(j), for 1 ≤ i < j ≤ = m. Then we test to see whether or not Laws of Large Numbers with nonzero limits exist for weighted sums of the random variables R _ij = X _n(j)/X _n(i).     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.