Approximating the Mean Waiting Time in the <Emphasis Type="Italic">GI/G/s</Emphasis> Queue

We provide two distribution-dependent approximations for the mean waiting time in a GI/G/s queue. Both approximations are weighted combinations of the exact mean waiting times for the GI/M/s and M/D/s queues each of which has the same mean service time and traffic intensity as in the approximating GI/G/s queue. The weights in the approximations are expressed by the service-time c.d.f. and the first two moments of interarrival and service times. To examine the performance of our approximations, they are numerically compared with exact solutions and previous two-moment approximations for various cases. Extensive numerical comparisons indicate that the relative percentage errors of the approximations are of the order of 5% in moderate traffic and 1% in heavy traffic, except for extreme cases.     

Refining Cosmetatos' Approximation for the Mean Waiting Time in the M/D/s Queue

This paper deals with refining Cosmetatos's approximation for the mean waiting time in an M/D/s queue. Although his approximation performs quite well in heavy traffic, it overestimates the true value when the number of servers is large or the traffic is light. We first focus on a normalized quantity that is a ratio of the mean waiting times for the M/D/s and M/M/s queues. Using some asymptotic properties of the quantity, we modify Cosmetatos's approximation to obtain better accuracy both for large s and in light traffic. To see the quality of our approximation, we compare it with the exact value and some previous approximations. Extensive numerical tests indicate that the relative percentage error is less than 1% for almost all cases with s ≤ 20 and at most 5% for other cases.     

Ideal Spaces of Measurable Operators Affiliated to A Semifinite Von Neumann Algebra

Suppose that M is a von Neumann algebra of operators on a Hilbert space H and τ is a faithful normal semifinite trace on M. Let E, F and G be ideal spaces on (M, τ). We find when a τ-measurable operator X belongs to E in terms of the idempotent P of M. The sets E+F and E·F are also ideal spaces on (M, τ); moreover, E·F = F·E and (E+F)·G = E·G+F·G. The structure of ideal spaces is modular. We establish some new properties of the L₁(M, τ) space of integrable operators affiliated to the algebra M. The results are new even for the *-algebra M = B(H) of all bounded linear operators on H which is endowed with the canonical trace τ = tr.     

Weak- and strong-type inequality for the cone-like maximal operator in variable Lebesgue spaces

The classical Hardy-Littlewood maximal operator is bounded not only on the classical Lebesgue spaces L_p(R^d) (in the case p > 1), but (in the case when 1/p(·) is log-Hölder continuous and p- = inf{p(x): x ∈ R^d > 1) on the variable Lebesgue spaces L_p(·)(R^d), too. Furthermore, the classical Hardy-Littlewood maximal operator is of weak-type (1, 1). In the present note we generalize Besicovitch’s covering theorem for the so-called γ-rectangles. We introduce a general maximal operator M_s^γδ, and with the help of generalized Φ-functions, the strong- and weak-type inequalities will be proved for this maximal operator. Namely, if the exponent function 1/p(·) is log-Hölder continuous and p- ≥ s, where 1 ≤ s ≤ ∞ is arbitrary (or p- ≥ s), then the maximal operator M_s^γδ is bounded on the space L_p(·)(R^d) (or the maximal operator is of weak-type (p(·), p(·))).     

Upper bounds of homological invariants of {FI_G}-modules

Given a finite group G, let P_G(s) be the probability that s randomly chosen elements generate G, and let H be a finite group with \({P_{G}(s) = P_{H}(s)}\). We show that if the nonabelian composition factors of G and H are PSL(2, p) for some non-Mersenne prime \({p \geq 5}\), then G and H have the same non-Frattini chief factors.     

Building Graphs Whose Independence Polynomials Have Only Real Roots

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

where s _k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).

Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).     

Geometric properties of the ridge function manifold

We study geometrical properties of the ridge function manifold \(\mathcal{R}_n\) consisting of all possible linear combinations of n functions of the form g(a· x), where a·x is the inner product in \({\mathbb R}^d\). We obtain an estimate for the ε-entropy numbers in terms of smaller ε-covering numbers of the compact class G _n,s formed by the intersection of the class \(\mathcal{R}_n\) with the unit ball \(B\mathcal{P}_s^d\) in the space of polynomials on \({\mathbb R}^d\) of degree s. In particular we show that for n?≤?s ^d???1 the ε-entropy number H _ε (G _n,s,L _q ) of the class G _n,s in the space L _q is of order nslog1/ε (modulo a logarithmic factor). Note that the ε-entropy number \(H_\varepsilon(B\mathcal{P}_s^d,L_q)\) of the unit ball is of order s ^d log1/ε. Moreover, we obtain an estimate for the pseudo-dimension of the ridge function class G _n,s.     

Extendability of Contractible Configurations for Nowhere-Zero Flows and Modulo Orientations

Let H be a connected graph and G be a supergraph of H. It is trivial that for any k-flow (D, f) of G, the restriction of (D, f) on the edge subset E(G / H) is a k-flow of the contracted graph G / H. However, the other direction of the question is neither trivial nor straightforward at all: for any k-flow \((D',f')\) of the contracted graph G / H, whether or not the supergraph G admits a k-flow (D, f) that is consistent with \((D',f')\) in the edge subset E(G / H). In this paper, we will investigate contractible configurations and their extendability for integer flows, group flows, and modulo orientations. We show that no integer flow contractible graphs are extension consistent while some group flow contractible graphs are also extension consistent. We also show that every modulo \((2k+1)\)-orientation contractible configuration is also extension consistent and there are no modulo (2k)-orientation contractible graphs.     

Neighbor sum distinguishing chromatic index of sparse graphs via the combinatorial Nullstellensatz

Let ?: E(G) → {1, 2, · · ·, k} be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if \(\sum\limits_{e \mathrel\backepsilon u} {\phi \left( e \right)} \ne \sum\limits_{e \mathrel\backepsilon v} {\phi \left( e \right)} \) for each edge uv ∈ E(G). The smallest value k for which G has such a coloring is denoted by χ′_Σ(G), which makes sense for graphs containing no isolated edge (we call such graphs normal). It was conjectured by Flandrin et al. that χ′_Σ(G) ≤ Δ(G) + 2 for all normal graphs, except for C₅. Let mad(G) = \(\max \left\{ {\frac{{2\left| {E\left( h \right)} \right|}}{{\left| {V\left( H \right)} \right|}}|H \subseteq G} \right\}\) be the maximum average degree of G. In this paper, we prove that if G is a normal graph with Δ(G) ≥ 5 and mad(G) < 3 ? \(\frac{2}{{\Delta \left( G \right)}}\), then χ′_Σ(G) ≤ Δ(G) + 1. This improves the previous results and the bound Δ(G) + 1 is sharp.     

On control of the prime spectrum of a finite simple group

The set π(G) of all prime divisors of the order of a finite group G is often called its prime spectrum. It is proved that every finite simple nonabelian group G has sections H ₁, …, H _m of some special form such that π(H ₁)∪…∪π(H _m ) = π(G) and m ≤ 5. Moreover, m ≤ 2 if G is an alternating or classical simple group. In all cases, it is possible to choose the sections H _i so that each of them is a simple nonabelian group, a Frobenius group, or (in one case) a dihedral group. If the above equality holds for a finite group G, then we say that the set {H ₁,…,H _m } controls the prime spectrum of G. We also study some parameter c(G) of finite groups G related to the notion of control.     

Bounding the sum of powers of the Laplacian eigenvalues of graphs

For a non-zero real number α, let s _α (G) denote the sum of the αth power of the non-zero Laplacian eigenvalues of a graph G. In this paper, we establish a connection between s _α (G) and the first Zagreb index in which the Hölder’s inequality plays a key role. By using this result, we present a lot of bounds of s _α (G) for a connected (molecular) graph G in terms of its number of vertices (atoms) and edges (bonds). We also present other two bounds for s _α (G) in terms of connectivity and chromatic number respectively, which generalize those results of Zhou and Trinajsti? for the Kirchhoff index [B Zhou, N Trinajsti?. A note on Kirchhoff index, Chem. Phys. Lett., 2008, 455: 120–123].     

On the rank of compact <Emphasis Type="Italic">p</Emphasis>-adic Lie groups

The rank of a profinite group G is the basic invariant \({{\rm rk}(G):={\rm sup}\{d(H) \mid H \leq G\}}\), where H ranges over all closed subgroups of G and d(H) denotes the minimal cardinality of a topological generating set for H. A compact topological group G admits the structure of a p-adic Lie group if and only if it contains an open pro-p subgroup of finite rank. For every compact p-adic Lie group G one has rk(G) ≥ dim(G), where dim(G) denotes the dimension of G as a p-adic manifold. In this paper we consider the converse problem, bounding rk(G) in terms of dim(G). Every profinite group G of finite rank admits a maximal finite normal subgroup, its periodic radical π(G). One of our main results is the following. Let G be a compact p-adic Lie group such that π(G) = 1, and suppose that p is odd. If \(\{g \in G \mid g^{p-1}=1 \}\) is equal to {1}, then rk(G) = dim(G).     

Holonomy groups of pseudo-quaternionic-Kählerian manifolds of non-zero scalar curvature

The holonomy group G of a pseudo-quaternionic-Kählerian manifold of signature (4r, 4s) with non-zero scalar curvature is contained in Sp(1) · Sp(r, s) and it contains Sp(1). It is proved that either G is irreducible, or s = r and G preserves an isotropic subspace of dimension 4r, in the last case, there are only two possibilities for the connected component of the identity of such G. This gives the classification of possible connected holonomy groups of pseudo-quaternionic-Kählerian manifolds of non-zero scalar curvature.     

Automorphism group of Green ring of Sweedler Hopf algebra

Let H ₂ be Sweedler’s 4-dimensional Hopf algebra and r(H ₂) be the corresponding Green ring of H ₂. In this paper, we investigate the automorphism groups of Green ring r(H ₂) and Green algebra F(H ₂) = r(H ₂)?_? F, where F is a field, whose characteristics is not equal to 2. We prove that the automorphism group of r(H ₂) is isomorphic to K ₄, where K ₄ is the Klein group, and the automorphism group of F(H ₂) is the semidirect product of ?₂ and G, where G = F {1/2} with multiplication given by a · b = 1? a ? b + 2ab.     

Normal coverings of solvable groups

For a finite non cyclic group G, let γ(G) be the smallest integer k such that G contains k proper subgroups H ₁, . . . , H _k with the property that every element of G is contained in \({H_i^g}\) for some \({i \in \{1,\dots,k\}}\) and \({g \in G.}\) We prove that for every n ≥ 2, there exists a finite solvable group G with γ(G) = n.     

Generalized 3-edge-connectivity of Cartesian product graphs

The generalized k-connectivity κ _k (G) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ _k (G) = min{λ(S): S ? V (G) and |S| = k}, where λ(S) denotes the maximum number l of pairwise edge-disjoint trees T ₁, T ₂, …, T _l in G such that S ? V (T _i ) for 1 ? i ? l. In this paper we prove that for any two connected graphs G and H we have λ ₃(G □ H) ? λ ₃(G) + λ ₃(H), where G □ H is the Cartesian product of G and H. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes.     

Invariable generation of prosoluble groups

A group G is invariably generated by a subset S of G if G = 〈s^g(s) | s ∈ S〉 for each choice of g(s) ∈ G, s ∈ S. Answering two questions posed by Kantor, Lubotzky and Shalev in [8], we prove that the free prosoluble group of rank d ≥ 2 cannot be invariably generated by a finite set of elements, while the free solvable profinite group of rank d and derived length l is invariably generated by precisely l(d ? 1) + 1 elements.     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

Using the M/G/1 queue under processor sharing for exact simulation of queues

In Sigman (J. Appl. Probab. 48A:209–216, 2011b), a first exact simulation algorithm was presented for the stationary distribution of customer delay for FIFO M/G/c queues in which ρ=λ/μ<1 (super stable case). The key idea involves dominated coupling from the past while using the M/G/1 queue under the processor sharing (PS) discipline as a sample-path upper bound, taking advantage of its time-reversibility properties so as to be able to simulate it backwards in time. Here, we expand upon this method and give several examples of other queueing models for which this method can be used to exactly simulate from their stationary distributions. Examples include sojourn times for single-server queues under various service disciplines, tandem queues, and multi-class networks with general routing.     

Expanding curves in T1(Hn) under geodesic flow and equidistribution in homogeneous spaces

Let H = SO(n, 1) and A = {a(t): t ∈ R} be a maximal R-split Cartan subgroup of H. Let G be a Lie group containing H and Γ be a lattice of G. Let φ = gΓ ∈ G/Γ be a point of G/Γ such that its H-orbit Hx is dense in G/Γ. Let φ: I = [a, b] → H be an analytic curve. Then φ(I)x gives an analytic curve in G/Γ. In this article, we will prove the following result: if φ(I) satisfies some explicit geometric condition, then a(t)φ(I)x tends to be equidistributed in G/Γ as t → ∞. It answers the first question asked by Shah in [Sha09c] and generalizes the main result of that paper.