Identifying defective sets using queries of small size

We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set $X$ of $n$ elements we want to identify an unknown subset $Y$ of $X$, which is known to have exactly $d$ elements, by means of testing, for as few as possible subsets $A$ of $X$, whether $A$ intersects $Y$ or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number $k$. Our main results are nearly tight bounds on the minimum number of tests necessary when $d$ and $k$ are fixed and $n$ is large enough.     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.     

All q m -ary Cyclic Codes with Cyclic q-ary Image Are Known

We give a simpler presentation of recent work byLeonard, Séguin and Tang-Soh-Gunawan. Our methodsimply as a new result that even in the repeated-root casethere are no more q ^m -arycyclic codes with cyclic q-ary image than thosegiven by Séguin.     

(n + 1)-ary derivations of semisimple Filippov algebras

The structure of generalized and (n+1)-ary derivations of simple and semisimple finite-dimensional Filippov algebras over an algebraically closed field of characteristic zero is described. An example of a semisimple ternary Mal’tsev algebra is given which is not a Filippov algebra and admits a nontrivial 4-ary derivation.     

On sets of type (q + 1, n)2 in finite three-dimensional projective spaces

It is proved that a k–set of type (q + 1, n)₂ in PG(3, q) either is a plane or it has size k ≥ (q + 1)² and a characterization of some sets of size (q + 1)² is given.     

Bargaining sets with small coalitions

We study two alternative definitions of the bargaining set in large (atomless) economies; the local bargaining by MasColell (1989) and the global bargaining set by Vind (1992). We alter these definitions to limit the size of the permitted size of the involved coalitions. It turns out that the local bargaining set becomes very large, whereas the global bargaining set is unaltered.     

Three-dimensional sets with small sumset

We describe the structure of three dimensional sets of lattice points, having a small doubling property. Let be a finite subset of ℤ³ such that dim = 3. If and , then lies on three parallel lines. Moreover, for every three dimensional finite set that lies on three parallel lines, if , then is contained in three arithmetic progressions with the same common difference, having together no more than terms. These best possible results confirm a recent conjecture of Freiman and cannot be sharpened by reducing the quantity υ or by increasing the upper bounds for .     

Sequences with small subsum sets

A conjecture of Gao and Leader, recently proved by Sun, states that if is a sequence of length n in a finite abelian group of exponent n, then either some subsequence of X sums to zero or the set of all sums of subsequences of X has cardinality at least 2n−1. This conjecture turns out to be a simple consequence of a theorem of Olson and White; we investigate generalizations that are not implied by this theorem. In particular, we prove the following result: if is a sequence of length n, the terms of which generate a finite abelian group of rank at least 3, then either some subsequence of X sums to zero or the set of all sums of subsequences of X has cardinality at least 4n−5.     

Ultrafilters with small generating sets

It is consistent, relative to ZFC, that the minimum number of subsets ofω generating a non-principal ultrafilter is strictly smaller than the dominating number. In fact, these two numbers can be any two prescribed regular cardinals. Both authors received partial support from NSF grants.     

Nonadaptive search problem with sets of equal sum

Consider the set A={1,2,3,…,2 ⁿ }, n≥3 and let x∈ A be unknown element. For given natural number S we are allowed to ask whether x belongs to a subset B of A such that the sum of the elements of B equals S. We investigate for which S it is possible to find x using a nonadaptive search.     

Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.     

Geometric and pseudo-geometric graphs (q2+1,q+1,1)

Let ₀ be a particular vertex of a strongly regular graph G with parameters v, n₁, p ₁₁ ¹ p ₁₁ ¹ . Let A be the adjacency matrix of G, and B the submatrix of A whose rows correspond to the vertices of G adjacent to ₀ and whose columns correspond to the vertices of G nonadjacent to ₀. Then the designD(₀) with incidence matrix B has the parameters v=n₁ b=v-n₁–1, r=n₁–p^11/1–1, k = p ₁₁ ² . In this paper we study the connection between G andD(₀) when the graph G is geometric or pseudo-geometric (q²+1,q+1,1).The research of this author was supported by the National Science Foundation Grant No. GP 23520 and the U.S. Air Force Office of Scientific Research under Grant No. AFOSR-68-1415C.The research of this author was supported by the National Science Foundation Grant No. GP 17172, while he was visiting professor at Stanford University.     

On sets with small doubling property

Suppose that G is an arbitrary Abelian group and A is any finite subset G. A set A is called a set with small sumset if, for some number K, we have |A + A| ≤ K|A|. The structural properties of such sets were studied in the papers of Freiman, Bilu, Ruzsa, Chang, Green, and Tao. In the present paper, we prove that, under certain constraints on K, for any set with small sumset, there exists a set Λ, Λ ? _? K log |A|, such that |A ν Λ| ? |A|/K ^1/2+? , where ? > 0. In contrast to the results of the previous authors, our theorem is nontrivial even for a sufficiently large K. For example, for K we can take |A| ^η , where η > 0. The method of proof used by us is quite elementary.