Polynomial cases of graph decomposition: A complete solution of Holyer’s problem

Let H be a fixed graph. A graph G has an H-decomposition if the edge set of G can be partitioned into subsets inducing graphs isomorphic to H. Let P_H denote the following decision problem: “Does an instance graph G admit H-decomposition?” In this paper we prove that the problem P_H is polynomial time solvable if H is a graph whose every component has at most 2 edges. This way we complete a solution of Holyer’s problem which is the problem of classifying the problems P_H according to their computational complexities.     

Comparison of potential theoretic properties of rough domains

We discuss the relationships between the notions of intrinsic ultracontractivity, the parabolic Harnack principle, compactness of the 1-resolvent of the Neumann Laplacian, and the non-trap property for Euclidean domains with finite Lebesgue measure. In particular, we give an answer to an open problem raised by Davies and Simon in 1984 about the possible relationship between intrinsic ultracontractivity for the Dirichlet Laplacian in a domain and compactness of the 1-resolvent of the Neumann Laplacian in .

     

Large buffer asymptotics for generalized processor sharing queues with Gaussian inputs

In this paper we derive large-buffer asymptotics for a two-class Generalized Processor Sharing (GPS) model. We assume both classes to have Gaussian characteristics. We distinguish three cases depending on whether the GPS weights are above or below the average rate at which traffic is sent. First, we calculate exact asymptotic upper and lower bounds, then we calculate the logarithmic asymptotics, and finally we show that the decay rates of the upper and lower bound match. We apply our results to two special Gaussian models: the integrated Gaussian process and the fractional Brownian motion. Finally we derive the logarithmic large-buffer asymptotics for the case where a Gaussian flow interacts with an on-off flow. AMS Subject Classification Primary—60K25; Secondary—68M20, 60G15     

On Some Almost-Periodicity Problems in Various Metrics

The Bohr-type and the Bochner-type definitions for almost periodic functions are examined in various metrics (Stepanov, Weyl and Besicovitch). The correct definitions of Besicovitch-like multifunctions are given. Weak almost-periodic solutions are proved for differential equations and inclusions. This problem is also discussed as a fixed-point problem in function spaces.     

Parisian ruin over a finite-time horizon

For a risk process R_u(t) = u + ct- X(t), t≥0, where u≥0 is the initial capital, c 0 is the premium rate and X(t), t≥0 is an aggregate claim process, we investigate the probability of the Parisian ruin P_S(u, T_u) = P{inf (t∈[0,S]_(s∈[t,t+T_u])) sup R_u(s) 0}, S, T_u 0.For X being a general Gaussian process we derive approximations of P_S(u, T_u) as u →∞. As a by-product, we obtain the tail asymptotic behaviour of the infimum of a standard Brownian motion with drift over a finite-time interval.     

Estimates of perturbation series for kernels

We consider Schr?dinger-type perturbations of integral kernels on space–time. Under suitable conditions on the first nontrivial term of the perturbation series, we prove that the perturbed kernel is locally in time comparable with the original kernel.     

Dynamic stability of a porous rectangular plate

The study is devoted to a axial compressed porous-cellular rectangular plate. Mechanical properties of the plate vary across is its thickness which is defined by the non-linear function with dimensionless variable and coefficient of porosity. The material model used in the current paper is as described by Magnucki, Stasiewicz papers. The middle plane of the plate is the symmetry plane. First of all, a displacement field of any cross section of the plane was defined. The geometric and physical (according to Hook's law) relationships are linear. Afterwards, the components of strain and stress states in the plate were found. The Hamilton's principle to the problem of dynamic stability is used. This principle was allowed to formulate a system of five differential equations of dynamic stability of the plate satisfying boundary conditions. This basic system of differential equations was approximately solved with the use of Galerkin's method. The forms of unknown functions were assumed and the system of equations was reduced to a single ordinary differential equation of motion. The critical load determined used numerically processed was solved. Results of solution shown in the Figures for a family of isotropic porous-cellular plates. The effect of porosity on the critical loads is presented. In the particular case of a rectangular plate made of an isotropic homogeneous material, the elasticity coefficients do not depend on the coordinate (thickness direction), giving a classical plate. The results obtained for porous plates are compared to a homogeneous isotropic rectangular plate. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Poincaré-Bendixson Theorem: from Poincaré to the XXIst century

The Poincaré-Bendixson Theorem and the development of the theory are presented ?? from the papers of Poincaré and Bendixson to modern results.     

Uniform Bounds on the Relative Error in the Approximation of Upper Quantiles for Sums of Arbitrary Independent Random Variables

Fix any \(n\ge 1\). Let \(\tilde{X}_1,\ldots ,\tilde{X}_n\) be independent random variables. For each \(1\le j \le n\), \(\tilde{X}_j\) is transformed in a canonical manner into a random variable \(X_j\). The \(X_j\) inherit independence from the \(\tilde{X}_j\). Let \(s_y\) and \(s_y^*\) denote the upper \(\frac{1}{y}{\underline{\text{ th }}}\) quantile of \(S_n=\sum _{j=1}^nX_j\) and \(S^*_n=\sup _{1\le k\le n}S_k\), respectively. We construct a computable quantity \(\underline{Q}_y\) based on the marginal distributions of \(X_1,\ldots ,X_n\) to produce upper and lower bounds for \(s_y\) and \(s_y^*\). We prove that for \(y\ge 8\)

$$\begin{aligned} 6^{-1} \gamma _{3y/16}\underline{Q}_{3y/16}\le s^*_{y}\le \underline{Q}_y \end{aligned}$$

where

$$\begin{aligned} \gamma _y=\frac{1}{2w_y+1} \end{aligned}$$

and \(w_y\) is the unique solution of

$$\begin{aligned} \Big (\frac{w_y}{e\ln (\frac{y}{y-2})}\Big )^{w_y}=2y-4 \end{aligned}$$

for \(w_y>\ln (\frac{y}{y-2})\), and for \(y\ge 37\)

$$\begin{aligned} \frac{1}{9}\gamma _{u(y)}\underline{Q}_{u(y)}<s_y \le \underline{Q}_y \end{aligned}$$

where

$$\begin{aligned} u(y)=\frac{3y}{32} \left( 1+\sqrt{1-\frac{64}{3y}}\right) . \end{aligned}$$

The distribution of \(S_n\) is approximately centered around zero in that \(P(S_n\ge 0) \ge \frac{1}{18}\) and \(P(S_n\le 0)\ge \frac{1}{65}\). The results extend to \(n=\infty \) if and only if for some (hence all) \(a>0\)

$$\begin{aligned} \sum _{j=1}^{\infty }E\{(\tilde{X}_j-m_j)^2\wedge a^2\}<\infty . \end{aligned}$$

(1)