Disjoint systems

A disjoint system of type (?, ?, k, n) is a collection ?? = {??₁,…, ??_m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair ??_i and ??_j of distinct members of ?? and for every A ? ??_i there exists a B ? ??_j that does not intersect A. Let D_n (?, ?, k) denote the maximum possible cardinality of a disjoint system of type (?, ?, k, n). It is shown that for every fixed k ? 2,. This settles a problem of Ahlswede, Cai, and Zhang. Several related problems are considered as well.     

Infinite spectra in the first order theory of graphs

The psectrum Spec(A) of a sentenceA is, roughly, the set of those a for whichA has a threshold function at or nearp=n ^–a . Examples are given ofA with infinite spectra and with spectra of order type ⁱ for arbitraryi.     

Embedding theorem ofZ-graded Lie superalgebras

The embedding theorem ofZ-graded Lie superalgebras is given and proved. As a subsidiary result it is proved that a transitiveZ-graded restricted lie superalgebm must be isomorphic toW(m,n, 1) if the dimension ofG _i satisfies a certain condition. Project supported by the National Natural Science Foundation of China and the Science of the University Doctoral Program of CNEC.     

On characterizing supremum andl p -efficient facility designs

Define a design to be any planar setD of known areaa, but of unknown shape and location; more generally, a design can be any set inR ^d of measurea. For example, a design might be one floor of a warehouse, or a sports arena of known seating capacity. Suppose that the design has, say,m users, or evaluators, with user/evaluatori having a design disutility functionu _i , 1im, which can be defined for all points in the plane independently of the designs of interest. Given any designD, denote byG _i (D) the disutility ofD to user/evaluatori where, by definition,G _i (D) is the supremum ofu _i over the setD, 1im. LetG(D) be the vector with entriesG _i (D), 1im, and define a design to be efficient if it solves the vector minimization problem obtained using the set of vectors {G(D):D a design}. Given mild assumptions about the disutility functions, and a slight refinement of the design definition to rule out certain pathologies, we present necessary and sufficient conditions for a design to be efficient, and study properties of efficient designs. In the final section, we extend the analysis to more generall _p -measures of design disutility.This research was supported in part by the Interuniversity College for PhD studies in Management Sciences, Brussels, Belgium; by the Army Research Office, Triangle Park, North Carolina; by a National Academy of Sciences-National Research Council Postdoctorate Associateship; and by the Operations Research Division, National Bureau of Standards, Washington, DC. The authors would like to thank Dr. A. J. Goldman for his many constructive suggestions, and Dr. A. Veinott for suggesting the problems considered in Section 3.     

On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

Let ₁,..., _m bem simple Jordan curves in the plane, and letK ₁,...,K _m be their respective interior regions. It is shown that if each pair of curves _i , _j ,i j, intersect one another in at most two points, then the boundary ofK= _i ^=1m K _i contains at most max(2,6m – 12) intersection points of the curves ₁, and this bound cannot be improved. As a corollary, we obtain a similar upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets. Following a basic approach suggested by Lozano Perez and Wesley, this can be applied to planning a collision-free translational motion of a convex polygonB amidst several (convex) polygonal obstaclesA ₁,...,A _m . Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log² n), wheren is the total number of corners of theA _i 's.Work on this paper by the second author has been supported in part by a grant from the Bat-Sheva Fund at Israel. Work by the fourth author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.     

The exact density function of the ratio of two dependent linear combinations of chi-square variables

A computable expression is derived for the raw moments of the random variableZ=N/D whereN= ₁ ⁿ m _iX_i+ _n ^+1s m _iX_i,D= _n ^+1s l _iX_i+ _s ^+1r n _iX_i, and theX _i's are independently distributed central chi-square variables. The first four moments are required for approximating the distribution ofZ by means of Pearson curves. The exact density function ofZ is obtained in terms of sums of generalized hypergeometric functions by taking the inverse Mellin transform of theh-th moment of the ratioN/D whereh is a complex number. The casen=1,s=2 andr=3 is discussed in detail and a general technique which applies to any ratio having the structure ofZ is also described. A theoretical example shows that the inverse Mellin transform technique yields the exact density function of a ratio whose density can be obtained by means of the transformation of variables technique. In the second example, the exact density function of a ratio of dependent quardratic forms is evaluated at various points and then compared with simulated values.     

On distance-regular graphs with fixed valency

We prove the following result. Let be a finite distance-regular graph. Letc _i ,a _i ,b _i be the intersection numbers of. If is not an ordinaryn-gon, then the number of (c _i ,a _i ,b _i ) such thatc _i =b _i is bounded by a certain function of the valencyk, say 10k2 ^k .Supported in part by N.S.F. grant MCS-830826. Also supported by Senior Visiting Scientist Grant of the British S.E.R.C. GR/C/97491 to visit Q.M.C. (University of London) 1984/5.Dedicated to Professor Hirosi Nagao on his 60th birthday     

Non-broken circuits of reflection groups and factorization inD n

The set of non-broken circuits of a reflection group W, denoted NBC(W), appears as a basis of the Orlik-Solomon algebra ofW. The factorization of their enumerating polynomial with respect to their cardinality involves the exponentsd _i-1 ofW. A simple explanation of this factorization is known only for the symmetric groupsS _n (Whitney [13]) and for the hyperoctahedral groupsB _n (Lehrer [7]). In this paper, we present an elementary proof of the fact that the set NBC(W) of any refection groupW is in bijection with the group elements ofW. We give a simple characterization of the non-broken circuits of the Weyl groups of typeD _n and we use this characterization to prove the factorization of their enumerating polynomial. Work partially supported by FGIA from ASU. Work partially supported by NSERC (Canada).     

Efficiency in integral facility design problems

An example of design might be a warehouse floor (represented by a setS) of areaA, with unspecified shape. Givenm warehouse users, we suppose that useri has a known disutility functionf _isuch thatH _i(S), the integral off _iover the setS (for example, total travel distance), defines the disutility of the designS to useri. For the vectorH(S) with entriesH _i(S), we study the vector minimization problem over the set {H(S) :S a design} and call a design efficient if and only if it solves this problem. Assuming a mild regularity condition, we give necessary and sufficient conditions for a design to be efficient, as well as verifiable conditions for the regularity condition to hold. For the case wheref _iis thel _p-distance from warehouse docki, with 1<p<, a design is efficient if and only if it is essentially the same as a contour set of some Steiner-Weber functionf =₁ f ₁++ _m f _m ,when the _i are nonnegative constants, not all zero.This research was supported in part by the Interuniversity College for PhD Studies in Management Sciences (CIM), Brussels, Belgium; by the Army Research Office, Triangle Park, North Carolina; by a National Academy of Sciences-National Research Council Postdoctorate Associateship; and by the Operations Research Division, National Bureau of Standards, Washington, D.C. The authors would like to thank R. E. Wendell for calling Ref. 16 to their attention.     

Finiteness properties of chevalley groups overFq[t]

LetG be a simple Chevalley group of rankn and Γ=G( ). Then the finiteness length of Γ shall be determined by studying the action of Γ on the Bruhat-Tits buildingX ofG . This is always possible provided that certain subcomplexes of the links of simplices inX are spherical. As a consequence, one obtains that Γ is of typeF _n−1 but not of typeFP _n ifG is of typeA _n, B_n, C_n orD _n andq≥2²ⁿ⁻¹.     

Groups acting simply transitively on the vertices of a building of typeà 2, I

If a group acts simply transitively on the vertices of an affine building with connected diagram, then must be of typeà _n–1 for somen2, and must have a presentation of a simple type. The casen=2, when is a tree, has been studied in detail. We consider the casen=3, motivated particularly by the case when is the building ofG=PGL(3,K),K a local field, and when G. We exhibit such a group whenK=F _q ((X)),q any prime power. Our study leads to combinatorial objects which we calltriangle presentations. These triangle presentations give rise to some new buildings of typeà ₂.     

On the gi/m/∞ service system with batch arrivals and different types of service distributions

We study the infinite-server system with batch arrivals ands different types of customers. With probabilityp _i an arriving customer is of typei (i=1,..., s) and requires an exponentially distributed service time with parameter _i (G ^GI /M ₁ ...M _s /). For theGI ^GI /M ₁...M _s / system it is shown that the binomial moments of thes-variate distribution of the number of type-i customers in the system at batch arrival epochs are determined by a recurrence relation and, in steady state, can be computed recursively. Furthermore, forG ^GI /M ₁...M _s /, relations between the distributions (and their binomial moments) of the system size vector at batch arrival and random epochs are given. Thus, earlier results by Takács [14], Gastwirth [9], Holman et al. [11], Brandt et al. [3] and Franken [6] are generalized.     

Modeling of superscalar instruction scheduling and analysis of a heuristic scheduling algorithm

The problem of superscalar instruction scheduling is studied and an analysis of a heuristic scheduling algorithm is presented. First, a superscalar architecture is characterized byk, the number of types of functional units employed,m _i , the number of typei functional units,P _ij , thejth functional unit of typei, andz, the maximal number of delay cycles incurred by the execution of instructions. A program trace to be scheduled is modeled by a directed acyclic graph with delay on precedence relations. These two models reflect most of the flavor of the superscalar instruction scheduling problem. A heuristic scheduling algorithm called the ECG-algorithm is designed by compiling two scheduling guidelines. The performance of the ECG-algorithm is evaluated through worst-case analysis. Lettingw _ECG denote the length of an ECG-schedule andw _opt the length of an optimal schedule, we established the boundwv _ECG /w _opt k+1–2/[max{m _i }(z+1)], which is smaller than other known bounds.     

Cyclic Bernoulli polling

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to move from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilityp _i , or moves on to the next queue (w.p. 1 —p _i ) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all parameterized cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thep _i 's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {p _i } _i ^N =1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalp _i 's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp ₁=1 is the best strategy, and derive conditions under which it is optimal to havep ₁ < 1.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant Number 3321190.     

Bounds of eigenvalues of a graph

LetG be a simple graph withn vertices. We denote by _i(G) thei-th largest eigenvalue ofG. In this paper, several results are presented concerning bounds on the eigenvalues ofG. In particular, it is shown that –1₂(G)(n–2)/2, and the left hand equality holds if and only ifG is a complete graph with at least two vertices; the right hand equality holds if and only ifn is even andG2K _n/2.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

On the classification of elliptic surfaces withq=1

We classify, up to isomorphism, elliptic surfaces with irregularity one having exactly one singular fiber (necessarily of typeI ₆ ^* ). All of them turn out to be elliptic modular surfaces (Shioda [11]), so that the problem is indirectly equivalent to classifying certain subgroups ofSL ₂(Z). These surfaces are then used to produce examples of (elliptic) surfaces withq=1, anyp _g 1, which have maximal Picard number (see Persson [7] for the caseq=0). Finally, the classification yields some interesting relationships between hypergeometric functions, theta functions, and certain automorphic forms.Supported in part by NSF DMS-8501724     

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.     

Line search by curve fitting in minimization algorithms

Summary Consider an unconstrained minimization of an uniformly convex functionf(z). Let be an algorithm that, for solving it constructs a sequence {z _i} withz _i+1 =z _i + ⁽ⁱ⁾ h _i ,h _i R ⁿ , ⁽ⁱ⁾ R ⁼ and –h _i ^T f(z _i ) > 0. For any algorithm that converges linearly and that uses parabolic or cubic interpolations for the line search, upper bounds on the number of function evaluations needed to approximate the minimum off(z) within a given accuracy, are calculated. The obtained results allow to compare the line search procedure under investigation.     

A randomly weighted estimate of the population mean

ＡＲＡＮＤＯＭＬＹＷＥＩＧＨＴＥＤＥＳＴＩＭＡＴＥＯＦＴＨＥＰＯＰＵＬＡＴＩＯＮ　ＭＥＡＮＣＨＥＮＸＩＲＵ（陈希孺）ＪＩＮＭＩＮＧＺＨＯＮＧ（金明仲）（ＧｒａｄｕａｔｅＳｃｈｏｏｌ,ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌａｐｙｏｆ...