Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .     

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.     

System G|Gκ|1 with Batch Service of Calls

For the queuing system G|G |1 with batch service of calls, we determine the distributions of the following characteristics: the length of a busy period, the queue length in transient and stationary modes of the queuing system, the total idle time of the queuing system, the output stream of served calls, etc.     

A sample path analysis of the M t /M t /c queue

The exact transient distribution of the queue length of the M _t /M _t /1 single server queue with timedependent Poisson arrival rate and timedependent exponential service rate was recently obtained by Zhang and Coyle [63] in terms of a solution to a Volterra equation. Their method involved the use of generating functions and complex analysis. In this paper, we present an approach that ties the computation of these transient distributions directly to the random sample path behavior of the M _t /M _t /1 queue. We show the versatility of this method by applying it to the M _t /M _t /c multiserver queue, and indicating how it can be applied to queues with timedependent phase arrivals or timedependent phase service.     

Opérateurs différentiels associés à certaines représentations unitaires d'un groupe de Lie résoluble exponentiel

Soient G = exp g un groupe de Lie résoluble exponentiel et H = exp h un sous-groupe connexe de G. Soient un caractère unitaire de H et = Ind_H ^G. Soit D(G/H) l'algèbre des opérateurs différentiels G-invariants sur G/H. Une question posée par Duflo et Corwin-Greenleaf consiste à voir si la finitude des multiplicités de est équivalente à la commutativité de D (G/H). Nous répondons positivement à cette question quand H est normal dans G. Lorsque H n'est pas normal, nous préparons le terrain pour d'espaces homogènes nilpotents et nous répondons à la question dans différents cas. Nous étudions finalement l'algèbre D (G) ^H , des opérateurs différentiels qui laissent l'espace des vecteurs C de invariant et qui commuttent avec l'action de H sur cet espace.     

Waiting-time tail probabilities in queues with long-tail service-time distributions

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx ^–r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.     

Inequalities in Products of Minors of Totally Nonnegative Matrices

Let _I,I be the minor of a matrix which corresponds to row set I and column set I. We give a characterization of the inequalities of the form _{I,I K,K J,J L,L} which hold for all totally nonnegative matrices. This generalizes a recent result of Fallat, Gekhtman, and Johnson.     

A characterization ofL n(K) as a permutation group

In 1972 M. O'Nan proved thatL _n (q),h 3; can be characterized as a doubly-transitive groupG on a finite set , whereG _a has an Abelian normal subgroup acting not semi-regularly on -a. In the Main Theorem we show that a similar statement holds if is infinite. Our result implies O'Nan's theorem.This paper is part of the author's Ph.D. thesis written under supervision of Prof. F. G. Timmesfeld.     

A Single Server Poisson Input Queue with a Second Optional Channel

Consider an M/G/1 queue such that over and above the first essential service having a general service time distribution, a unit may need a second optional service with another independent general service time. A unit may depart from the system either after the first essential service with probability (1–r) or at the end of the first service may immediately go for a second service with probability r (0r1). This is a generalization of a recent paper considered by Madan [5].     

Characterization theorem of generalized polynomial of best approximation having bounded coefficients

Let the set of generalized polynomials having bounded coefficients beK={p= _jg_j. _{j j j},j=1, 2, ...,n}, whereg ₁,g ₂, ...,g _n are linearly independent continuous functions defined on the interval [a, b], _j, _j are extended real numbers satisfying _j<+, _j>-, and _{j j}. Assume thatf is a continuous function defined on a compact setX [a, b]. This paper gives the characterization theorem forp being the best uniform approximation tof fromK, and points out that the characterization theorem can be applied in calculating the approximate solution of best approximation tof fromK.     

Convolution tails,product tails and domains of attraction

Summary A distribution function is said to have an exponential tail F(t) = F(t, ) if e ^u F(t+u) is asymptotically equivalent to F(t), t, t, for all u. In this case F(lnt) is regularly varying. For two such distributions, F and G, the convolution H=F*G also has an exponential tail. We investigate the relationship between H and its components F and G, providing conditions for lim H/F to exist. In addition, we are able to describe the asymptotic nature of H when the limit is infinite, for many cases. This corresponds to determining both the domain of attraction and the norming constants for the product of independent variables whose distributions have regularly varying tails.In addition, we compare the tails of H=F*G with H ₁=F ₁*G ₁when F is asymptotically equivalent to F and G is equivalent to G ₁. Such a comparison corresponds to the balancing consideration for the product of independent variables in stable domains of attraction. We discover that there are several distinct comparisons possible.     

An M/G/1 queue with second optional service

We study an M/G/1 queue with second optional service. Poisson arrivals with mean arrival rate (>0) all demand the first essential service, whereas only some of them demand the second optional service. The service times of the first essential service are assumed to follow a general (arbitrary) distribution with distribution function B(v) and that of the second optional service are exponential with mean service time 1/₂ (₂>0). The time-dependent probability generating functions have been obtained in terms of their Laplace transforms and the corresponding steady state results have been derived explicitly. Also the mean queue length and the mean waiting time have been found explicitly. The well-known Pollaczec–Khinchine formula and some other known results including M/D/1, M/E_k/1 and M/M/1 have been derived as particular cases.     

Inductive sources and subnormal subgroups

A character pair (H, ) in a group G is a subgroup H and a character Irr(H). Following Dade, we say that a character pair (H, ) is an inductive source in G if induction to G defines an injective map from the irreducible characters of the stabilizer of (H, ) that lie over into Irr(G). (By the Clifford correspondence, this necessarily happens if H is normal in G.) A character pair is said to be conjugate stable if its conjugates satisfy a certain technical condition. We show that an inductive source must be conjugate stable and we present an example of a character pair that is conjugate stable but is not an inductive source. Finally, if (H, ) is conjugate stable and H is a subnormal subgroup of G, we show that (H, ) must be an inductive source in G.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

Wiener-Hopf analysis of an M/G/1 queue with negative customers and of a related class of random walks

Two variants of an M/G/1 queue with negative customers lead to the study of a random walkX _n+1=[X _n + _n ]⁺ where the integer-valued _n are not bounded from below or from above, and are distributed differently in the interior of the state-space and on the boundary. Their generating functions are assumed to be rational. We give a simple closed-form formula for , corresponding to a representation of the data which is suitable for the queueing model. Alternative representations and derivations are discussed. With this formula, we calculate the queue length generating function of an M/G/1 queue with negative customers, in which the negative customers can remove ordinary customers only at the end of a service. If the service is exponential, the arbitrarytime queue length distribution is a mixture of two geometrical distributions.Supported by the European grant BRA-QMIPS of CEC DG XIII.     

Dominated, diagonal polynomials on ℓ p spaces

We show that the r-dominated polynomials on _p(2 p ) are integral on ₁, and give examples proving that the converse is not true. We characterize when the 2-homogeneous, diagonal polynomials on _p(1 < p ) are r-dominated. We prove that, unlike the linear case, there are nuclear polynomials which are not 1-dominated.Received: 6 June 2004; revised: 28 September 2004     

On the Eigenvalues and Eigenfunctions of the Sturm--Liouville Operator with a Singular Potential

In this paper we consider the Sturm--Liouville operators generated by the differential expression -y+q(x)y and by Dirichlet boundary conditions on the closed interval [0,]. Here q(x) is a distribution of first order,, i.e., q(x)dx L ₂[0,]. Asymptotic formulas for the eigenvalues and eigenfunctions of such operators which depend on the smoothness degree of q(x) are obtained.     

Cyclic Ostrom Spreads

We call a transitive permutation group G stable if every non-trivial orbit B, of a point stabilizerG _O , is such that some element of G-G _O leaves invariant B {O}. We characterize all finite affine planes of order n that admit a collineation group G that acts, on the points of , as a stable 3/2-transitive permutation group of rank n+2 . The planes obtained are precisely what we have called cyclic Ostrom planes; these are translation planes whose associated spreads are obtained from the Desarguesian spread , of order n=p^r , by replacing a partial subspread of by another consisting of GF(p) subspaces that are unions of kern orbits. All André spreads, as well as many other spreads, are examples of cyclic Ostrom spreads.     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

Polynomially convex orbits of compact lie groups

LetV be a finite dimensional complex linear space and letG be a compact subgroup of GL(V). We prove that an orbitG, V, is polynomially convex if and only ifG is closed andG is the real form ofG . For every orbitG which is not polynomially convex we construct an analytic annulus or strip inG with the boundary inG. It is also proved that the group of holomorphic automorphisms ofG which commute withG acts transitively on the set of polynomially convexG-orbits. Further, an analog of the Kempf-Ness criterion is obtained and homogeneous spaces of compact Lie groups which admit only polynomially convex equivariant embeddings are characterized.Supported by Federal program Integratsiya, no. 586.Supported by INTAS grant 97/10170.