Error-correcting nonadaptive group testing with d-disjunct matrices

d-disjunct matrices constitute a basis for nonadaptive group testing (NGT) algorithms and binary d-superimposed codes. The rows of a d-disjunct matrix represent the tests in a NGT algorithm which identifies up to d defects in a population. The columns of a d-disjunct matrix represent binary d-superimposable codewords. A d-disjunct matrix μ is called d^e-disjunct if given any d + 1 columns of μ with one designated, there are e + 1 rows with a 1 in the designated column and a 0 in each of the other d columns. d^e-disjunct matrices form a basis for e error-correcting NGT algorithms. In this paper, we construct d^e-disjunct matrices. In so doing, we simultaneously construct e error-correcting binary d-superimposed codes. The results of this paper can be used to construct pooling designs for the screening recombinant DNA libraries. Such screenings are a major component of the Human Genome Project.     

Ramsey linear families and generalized subdivided graphs

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V₁, V₂,…, V_a such that for each i at most d vertices in V₁ … V_i have neighbors in V_i+1 and r(K_k, V_i) p | V(G) |, where V_i denotes the subgraph of G induced by V_i. Then there exists a number c depending only on p, d, and k such that r(K_k, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.     

Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs

Let S₁ and S₂ be two (k-1)-subsets in a k-uniform hypergraph H. We call S₁ and S₂ strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S₁ ∩ e ≠∅ and S₂ ∩ e ≠∅ or e ⊆ S₁ ∪ S₂ or e ⊇ S₁ ∪ S₂, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k²-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.     

A note on the stationarity of a threshold first-order bilinear process

In the present note we study the threshold first-order bilinear model

X(t)=aX(t−1)+(b₁1_{X(t−1)<c}+b₂1_{X(t−1)c})X(t−1)e(t−1)+e(t), tεN

where {e(t), tεN} is a sequence of i.i.d. absolutely continuous random variables, X(0) is a given random variable and a, b₁, b₂ and c are real numbers. Under suitable conditions on the coefficients and lower semicontinuity of the densities of the noise sequence, we provide sufficient conditions for the existence of a stationary solution process to the present model and of its finite moments of order p.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次.图G的(s,t)-松弛强边着色指数,记作x'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值.在图G中...     

Largest signless Laplacian spectral radius of uniform supertrees with diameter and pendent edges (vertices)

Let \mathbb{S}(m; d; k) be the set of k-uniform supertrees with m edges and diameter d; and S₁(m; d; k) be the k-uniform supertree obtained from a loose path u₁; e₁; u₂; e₂,..., u_d; e_d; u_d+1 with length d by attaching m — d edges at vertex u_{\lfloor d/2\rfloor +1}: In this paper, we mainly determine S₁(m; d; k) with the largest signless Laplacian spectral radius in \mathbb{S}(m; d; k) for 3≤d≤m –1: We also determine the supertree with the second largest signless Laplacian spectral radius in \mathbb{S}(m; 3; k): Furthermore, we determine the unique k-uniform supertree with the largest signless Laplacian spectral radius among all k-uniform supertrees with n vertices and pendent edges (vertices).     

Magic Labeling of Disjoint Union Graphs

Let G be a graph with vertex set V (G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,|E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+|E(G)|)/2·d(v), where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V (G),|{e:e ∈ E_v, f(e) ≤ Δ/2}|=|{e:e ∈ E_v, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.     

The connectivity of a graph on uniform points on [0,1]

A random graph G_n(x) is constructed on independent random points U₁,…,U_n distributed uniformly on [0,1]^d, d1, in which two distinct such points are joined by an edge if the l_∞-distance between them is at most some prescribed value 0<x<1. The connectivity distance c_n, the smallest x for which G_n(x) is connected, is shown to satisfy

(1)

For d2, the random graph G_n(x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: c_n/d_n→1, a.s., as n→∞, where d_n is the largest nearest-neighbor link, the smallest x for which G_n(x) has no isolated vertices.     

Duality in Padé-type approximation

Padé and Padé-type approximants are usually defined by replacing the function (1 − xt)⁻¹ by its Hermite (that is confluent) interpolation polynomial and then applying the functional c defined by c(xⁱ) = c_i where the c_i's are the coefficients of the series to be approximated. In this paper the functional d which, applied to (1 − xt)⁻¹, gives the same Padé or Padé-type approximant as before is studied. It can be considered as the dual of the interpolation operator applied to the functional c.     

On the number of flats spanned by a set of points in PG(d, q)

It is shown that for fixed 1 r s < d and > 0, if X PG(d, q) contains (1 + )q^s points, then the number of r-flats spanned by X is at least c()q^{(r+1)(s+1−r)}, i.e. a positive fraction of the number of r-flats in PG(s + 1,q).     

Budget constrained minimum cost connected medians

Several practical instances of network design and location theory problems require the network to satisfy multiple constraints. In this paper, we study a graph-theoretic problem that aims to simultaneously address a network design task and a location-theoretic constraint. The Budget Constrained Connected Median Problem is the following: We are given an undirected graph G=(V,E) with two different edge-weight functions c (modeling the construction or communication cost) and d (modeling the service distance), and a bound B on the total service distance. The goal is to find a subtree T of G with minimum c-cost c(T) subject to the constraint that the sum ∑_vVTdist_d(v,T) of the service distances of all the remaining nodes vVT does not exceed the specified budget B. Here, the service distance dist_d(v,T) denotes the shortest path distance of v to a vertex in T with respect to d. This problem has applications in optical network design and the efficient maintenance of distributed databases.

We formulate this problem as a bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem which demonstrate that our performance ratios are close to best possible.     

Interval orders based on weak orders

One definition of an interval order is as an order isomorphic to that of a family of nontrivial intervals of a linearly ordered set with [a,b] < [c,d] if b c. Fishburn's theorem states that an order is an interval order if and only if it has no four-element restriction isomorphic to the ordered set (shown in Fig. 1) “ ”. We show that an order is isomorphic to a family of nontrivial intervals of a weak order, ordered as above, if and only if it has no restriction to one of the four ordered sets (shown in Fig. 2) “ ”, a six-element crown or a six-element fence.     

On size, circumference and circuit removal in 3-connected matroids

This paper proves several extremal results for 3-connected matroids. In particular, it is shown that, for such a matroid M, (i) if the rank r(M) of M is at least six, then the circumference c(M) of M is at least six and, provided |E(M)|4r(M)−5, there is a circuit whose deletion from M leaves a 3-connected matroid; (ii) if r(M)4 and M has a basis B such that Me is not 3-connected for all e in E(M)−B, then |E(M)|3r(M)−4; and (iii) if M is minimally 3-connected but not hamiltonian, then |E(M)|3r(M)−c(M).     

The relation of the d-orthogonal polynomials to the Appell polynomials

We are dealing with the concept of d-dimensional orthogonal (abbreviated d-orthogonal) polynomials, that is to say polynomials verifying one standard recurrence relation of order d + 1. Among the d-orthogonal polynomials one singles out the natural generalizations of certain classical orthogonal polynomials. In particular, we are concerned, in the present paper, with the solution of the following problem (P): Find all polynomial sequences which are at the same time Appell polynomials and d-orthogonal. The resulting polynomials are a natural extension of the Hermite polynomials.

A sequence of these polynomials is obtained. All the elements of its (d + 1)-order recurrence are explicitly determined. A generating function, a (d + 1)-order differential equation satisfied by each polynomial and a characterization of this sequence through a vectorial functional equation are also given. Among such polynomials one singles out the d-symmetrical ones (Definition 1.7) which are the d-orthogonal polynomials analogous to the Hermite classical ones. When d = 1 (ordinary orthogonality), we meet again the classical orthogonal polynomials of Hermite.     

Valuations defined by Ostrowski nets

Ostrowski proved that if v is a valuation on an algebraically closed field F and if w is a valuation extending v to the field F (x) of rational functions over F, then w is defined by a transcendental pseudo-convergent net (that is, an Ostrowski net) or w is a Rella extension of v centered about x − c for some c in F. In this paper, valuations on the field of rational functions over an arbitrary field determined by Ostrowski nets, along with the topologies they generate, are investigated.     

Strong approximation for cross-covariances of linear variables with long-range dependence

Suppose {_k, −∞ < k < ∞} is an independent, not necessarily identically distributed sequence of random variables, and {c_j}^∞_j=0, {d_j}^∞_j=0 are sequences of real numbers such that Σ_jc²_j < ∞, Σ_jd²_j < ∞. Then, under appropriate moment conditions on {_k, −∞ < k < ∞}, y_k Σ^∞_j=0c_jk-j, z_k Σ^∞_j=0d_jk-j exist almost surely and in ⁴ and the question of Gaussian approximation to S_[t]Σ^[t]_k=1 (y_k z_k − E{y_k z_k}) becomes of interest. Prior to this work several related central limit theorems and a weak invariance principle were proven under stationary assumptions. In this note, we demonstrate that an almost sure invariance principle for S_[t], with error bound sharp enough to imply a weak invariance principle, a functional law of the iterated logarithm, and even upper and lower class results, also exists. Moreover, we remove virtually all constraints on _k for “time” k ≤ 0, weaken the stationarity assumptions on {_k, −∞ < k < ∞}, and improve the summability conditions on {c_j}^∞_j=0, {d_j}^∞_j=0 as compared to the existing weak invariance principle. Applications relevant to this work include normal approximation and almost sure fluctuation results in sample covariances (let d_j = c_j-m for j ≥ m and otherwise 0), quadratic forms, Whittle's and Hosoya's estimates, adaptive filtering and stochastic approximation.     

An extended result of Kleitman and Saks concerning binary trees

In a recent paper, D.J. Kleitman and M.E. Saks gave a proof of Huang's conjecture on alphabetic binary trees.

Given a set E = {e_i}, I = 0, 1, 2, …, m and assigned positive weights to its elements and supposing the elements are indexed such that w(e₀) ≤ w(e₁) ≤ … ≤w (e_m), where w(e_i) is the weight of e_i, we call the following sequence E^* a ‘saw-tooth’ sequence

E^*=(e₀,e_m,e₁,…,e_j,e_m−j,…).

Huang's conjecture is: E^* is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and log₂(m + 1) ≤L≤m.     

Induced subgraphs of given sizes

We say (n, e) → (m, f), an (m, f) subgraph is forced, if every n-vertex graph of size e has an m-vertex spanned subgraph with f edges. For example, as Turán proved, (n,e)→(k,(^k₂)) for e> t_{k − 1}(n) and (n,e) (^k₂)), otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open.     

Characterization of Laborde-Mulder graphs (extended odd graphs)

The identification of diametrical vertices in the d-dimensional hypercube (d 3) leads to a (0, 2)-graph of degree d on 2^d−1 vertices and of diameter d/2 namely the extended odd graph (or Laborde-Mulder graph) for odd values of d, and the half-cube for even values of d. In this paper we prove that the diameter of a (0, 2)-graph of degree d on 2^d−1 vertices is at least d/2 , and when d is odd the equality holds if and only if the graph is a Laborde-Mulder graph.     

Convolution integral equations with Gegenbauer function kernel

In this paper we develop a concise and transparent approach for solving Mellin convolution equations where the convolutor is the product of an algebraic function and a Gegenbauer function. Our method is primarily based on

1. the use of fractional integral/differential operators;

2. a formula for Gegenbauer functions which is a fractional extension of the Rodrigues formula for Gegenbauer polynomials (see Theorem 3);

3. an intertwining relation concerning fractional integral/differential operators (see Theorem 1), which in the integer case reads (d/dx)²ⁿ⁺¹ = (x⁻¹ d/dx)ⁿx²ⁿ⁺¹(x⁻¹ d/dx)ⁿ⁺¹.

Thus we cover most of the known results on this type of integral equations and obtain considerable extensions. As a special illustration we present the Gegenbauer transform pair associated to the Radon transformation.