On symbolic RG factorization of quasi-birth-and-death processes

In this paper we propose a symbolic method for solving quasi-birth-and-death processes via the RG factorization, and some “simple truncations”—see Remark 4. For reasons yet unexplained, this symbolic method yields the exact G, U, and R matrices in some low dimensional cases like the M/M/c/c retrial queue with c=1,2 servers (these results are essentially known due to Liu and Zhao (2010)), as well as the “Lie solvable model” introduced by Kawanishi (2005) (again only for c=1,2).     

Hitting Simplices with Points in ℝ3

The so-called first selection lemma states the following: given any set P of n points in ℝ ^d , there exists a point in ℝ ^d contained in at least c _d n ^d+1−O(n ^d ) simplices spanned by P, where the constant c _d depends on d. We present improved bounds on the first selection lemma in ℝ³. In particular, we prove that c ₃≥0.00227, improving the previous best result of c ₃≥0.00162 by Wagner (On k-sets and applications. Ph.D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c ₃≤1/4⁴≈0.00390) and Boros and Füredi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69–77, 1984) (where the two-dimensional case was settled).     

On (<Emphasis Type="Italic">p</Emphasis>, 1)-total labelling of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.     

Complete classification of the positive solutions of −Δ<Emphasis Type="Italic">u</Emphasis> + <Emphasis Type="Italic">u</Emphasis><Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>

We study the equation −Δu + u ^q = 0, q > 1, in a bounded C ² domain Ω ⊂ ℝ ^N . A positive solution of the equation is moderate if it is dominated by a harmonic function and σ-moderate if it is the limit of an increasing sequence of moderate solutions. It is known that in the subcritical case, 1 < q <, q _c = (N + 1)/(N − 1), every positive solution is σ-moderate [32]. More recently, Dynkin proved, by probabilistic methods, that this remains valid in the supercritical case for q ≤ 2, [15]. The question remained open for q > 2. In this paper, we prove that for all q ≥ q _c , every positive solution is σ-moderate. We use purely analytic techniques, which apply to the full supercritical range. The main tools come from linear and non-linear potential theory. Combined with previous results, our result establishes a one-to-one correspondence between positive solutions and their boundary traces in the sense of [36].     

Inverse Conductivity Problem on Riemann Surfaces

An electrical potential U on a bordered Riemann surface X with conductivity function σ>0 satisfies equation d(σ d ^c U)=0. The problem of effective reconstruction of σ from electrical currents measurements (Dirichlet-to-Neumann mapping) on the boundary: U| _bX ↦ σ d ^c U| _bX is studied. We extend to the case of Riemann surfaces the reconstruction scheme given, firstly, by R. Novikov (Funkc. Anal. Ego Priloz. 22:11–22, 2008) for simply connected X. We apply for this new kernels for on the affine algebraic Riemann surfaces constructed in Henkin (, 2008).      

Long cycles in abc-permutations

An abc-permutation is a permutation σ _abc ∈S _n obtained by exchanging an initial block of length a and a final block of length c of {1,…,n}, where n=a+b+c. In this note we compute the limit of the probability that a random abc-permutation is a long cycle. This resolves Arnold’s open problem (Arnold in Arnold’s problems, 2004, p. 144).      

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

Properties of traveling waves for integrodifference equations with nonmonotone growth functions

In this paper, we will establish some new properties of traveling waves for integrodifference equations with the nonmonotone growth functions. More precisely, for c ≥ c _*, we show that either lim_x?+￥ f(x)=u*{\lim\limits_{\xi\rightarrow+\infty} \phi(\xi)=u*} or 0 < liminf_{x? + ￥} f(x) < u* < limsup_x?+￥f(x) ￡ b,{0 < \liminf\limits_{\xi \rightarrow + \infty} \phi(\xi) < u* < \limsup \limits_{\xi\rightarrow+\infty}\phi(\xi)\leq b,} that is, the wave converges to the positive equilibrium or oscillates about it at +∞. Sufficient conditions can assure that both results will arise. We can also obtain that any traveling wave with wave speed c > c* possesses exponential decay at −∞. These results can be well applied to three types of growth functions arising from population biology. By choosing suitable parameter numbers, we can obtain the existence of oscillating waves. Our analytic results are consistent with some numerical simulations in Kot (J Math Biol 30:413–436, 1992), Li et al. (J Math Biol 58:323–338, 2009) and complement some known ones.     

<Emphasis Type="Italic">π</Emphasis>-formulas implied by Dougall’s summation theorem for <Subscript>5</Subscript><Emphasis Type="Italic">F</Emphasis><Subscript>4</Subscript>-series

The general summation theorem for well-poised ₅ F ₄-series discovered by Dougall (Proc. Edinb. Math. Soc. 25:114–132, 1907) is shown to imply several infinite series of Ramanujan-type for 1/π and 1/π ², including those due to Bauer (J. Reine Angew. Math. 56:101–121, 1859) and Glaisher (Q. J. Math. 37:173–198, 1905) as well as some recent ones by Levrie (Ramanujan J. 22:221–230, 2010).     

Deducing the multidimensional Szemerédi theorem from an infinitary removal lemma

We offer a new proof of the Furstenberg-Katznelson multiple recurrence theorem for several commuting probability-preserving transformations T ₁, T ₂, …, T _d : ℤ ↷ (X, ∑, μ) ([6]), and so, via the Furstenberg correspondence principle introduced in [5], a new proof of the multi-dimensional Szemerédi Theorem. We bypass the careful manipulation of certain towers of factors of a probability-preserving system that underlies the Furstenberg-Katznelson analysis, instead modifying an approach recently developed in [1] to pass to a large extension of our original system in which this analysis greatly simplifies. The proof is then completed using an adaptation of arguments developed by Tao in [13] for his study of an infinitary analog of the hypergraph removal lemma. In a sense, this addresses the difficulty, highlighted by Tao, of establishing a direct connection between his infinitary, probabilistic approach to the hypergraph removal lemma and the infinitary, ergodic-theoretic approach to Szemerédi’s Theorem set in motion by Furstenberg [5].     

Upper bound for the decay rate of the joint queue-length distribution in a two-node Markovian queueing system

This paper studies the geometric decay property of the joint queue-length distribution {p(n ₁,n ₂)} of a two-node Markovian queueing system in the steady state. For arbitrarily given positive integers c ₁,c ₂,d ₁ and d ₂, an upper bound of the decay rate is derived in the sense

Graphs, partitions and classes of groups

If \mathfrak X{\mathfrak X} is a class of groups, Delizia et al. (Bull Austral Math Soc 75:313–320, 2007) call a group G \mathfrak X{\mathfrak X} -transitive (or an \mathfrak XT{\mathfrak XT} -group) if whenever áa,b?{\langle a,b\rangle} and áb,c?{\langle b,c\rangle} are in \mathfrak X áa,c?{\mathfrak X} \langle a,c\rangle is also in \mathfrak X{\mathfrak X} (a,b,c ? G{a,b,c\in G}). The structure of \mathfrak XT{\mathfrak XT} -groups has been investigated for a number of classes of groups, by Delizia, Moravec and Nicotera and others. A graph can be associated with a group in many ways. Delizia, Moravec and Nicotera introduce a graph which is a generalisation of the commuting graph of a group, but do not make use of the graph. We will use the properties of the graph to investigate further classes of groups and to obtain more detailed structural information.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for <Emphasis Type="Italic">ρ</Emphasis><<Emphasis Type="Italic">c</Emphasis>

We present an exact simulation algorithm for the stationary distribution of customer delay for FIFO M/G/c queues in which ρ=λ/μ<c. In Sigman (J. Appl. Probab. 48A:209–216, 2011) an exact simulation algorithm was presented but only under the strong condition that ρ<1 (super stable case). We only assume that the service-time distribution G(x)=P(S≤x), x≥0, with mean 0<E(S)=1/μ<∞, and its corresponding equilibrium distribution $G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy$G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy are such that samples of them can be simulated. Unlike the methods used in Sigman (J. Appl. Probab. 48A:209–216, 2011) involving coupling from the past, here we use different methods involving discrete-time processes and basic regenerative simulation, in which, as regeneration points, we use return visits to state 0 of a corresponding random assignment (RA) model which serves as a sample-path upper bound.     

Two classes of optimal two-dimensional OOCs

Let Φ(u × v, k, λ _a , λ _c ) denote the largest possible size among all 2-D (u × v, k, λ _a , λ _c )-OOCs. In this paper, the exact value of Φ(u × v, k, λ _a , k − 1) for λ _a = k − 1 and k is determined. The case λ _a = k − 1 is a generalization of a result in Yang (Inform Process Lett 40:85–87, 1991) which deals with one dimensional OOCs namely, u = 1.     

Varieties with at most quadratic growth

Let V be a variety of non-necessarily associative algebras over a field of characteristic zero. The growth of V is determined by the asymptotic behavior of the sequence of codimensions c _n (V), n = 1, 2, …, and here we study varieties of polynomial growth. Recently in [16], for any real number α, 3 < α < 4, a variety V was constructed satisfying C ₁ n ^α < c _n (V) < C ₂ n ^α , for some constants C ₁, C ₂. Motivated by this result here we try to classify all possible growth of varieties V such that c _n (V) < C _n ^α , with 0 < α < 2, for some constant C. We prove that if 0 < α < 1 then, for n large, c _n (V) ≤ 1, whereas if V is a commutative variety and 1 < α < 2, then lim _n→∞ log _n c _n (V) = 1 or c _n (V) ≤ 1 for n large enough.     

A Little More on Coz-Unique Frames

Coz-unique frames were defined and characterized by Banaschewski and Gilmour (J Pure Appl Algebra 157:1–22, 2001). In this note we give further characterizations of these frames along the lines of characterizations of absolutely z-embedded spaces obtained by Blair and Hager (Math Z 136:41–52, 1974) on the one hand, and by Hager and Johnson (Canad J Math 20:389–393, 1968) on the other. We also extend to frames certain characterizations of z-embedded spaces; namely, we give a characterization of coz-onto frame homomorphisms in terms of normal covers.