An Asymptotic Ratio in the Complete Binary Tree

Let T _n be the complete binary tree of height n considered as the Hasse-diagram of a poset with its root 1 _n as the maximum element. For a rooted tree T, define two functions counting the embeddings of T into T _n as follows A(n;T)=|{S T _n  : 1 _n ∈S, S≅T}|, and B(n;T)=|{S T _n :1 _n ∉S, S≅T}|. In this paper we investigate the asymptotic behavior of the ratio A(n;T)/B(n;T), and we show that lim  _n→∞[A(n;T)/B(n;T)]=2^ℓ;−1−1, for any tree T with ℓ leaves. This revised version was published online in June 2006 with corrections to the Cover Date.     

Maximum directed cuts in digraphs with degree restriction

For integers m, k≥1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Transient Dynamics in the Random Growth and Reset Model

A mean-field type model with random growth and reset terms is considered. The stationary distributions resulting from the corresponding master equation are relatively easy to obtain; however, for practical applications one also needs to know the convergence to stationarity. The present work contributes to this direction, studying the transient dynamics in the discrete version of the model by two different approaches. The first method is based on mathematical induction by the recursive integration of the coupled differential equations for the discrete states. The second method transforms the coupled ordinary differential equation system into a partial differential equation for the generating function. We derive analytical results for some important, practically interesting cases and discuss the obtained results for the transient dynamics.     

Runge–Kutta convolution quadrature for operators arising in wave propagation

An error analysis of Runge–Kutta convolution quadrature is presented for a class of non-sectorial operators whose Laplace transform satisfies, besides the standard assumptions of analyticity in a half-plane Re s > σ ₀ and a polynomial bound \operatornameO(|s|^m₁){\operatorname{O}(|s|^{\mu_1})} there, the stronger polynomial bound \operatornameO(s^m₂){\operatorname{O}(s^{\mu_2})} in convex sectors of the form |\operatorname*arg s| ￡ p/2-q{|\operatorname*{arg} s| \leq \pi/2-\theta} for θ > 0. The order of convergence of the Runge–Kutta convolution quadrature is determined by μ ₂ and the underlying Runge–Kutta method, but is independent of μ ₁. Time domain boundary integral operators for wave propagation problems have Laplace transforms that satisfy bounds of the above type. Numerical examples from acoustic scattering show that the theory describes accurately the convergence behaviour of Runge–Kutta convolution quadrature for this class of applications. Our results show in particular that the full classical order of the Runge–Kutta method is attained away from the scattering boundary.     

Efficient long-time computations of time-domain boundary integrals for 2D and dissipative wave equation

Linear hyperbolic partial differential equations in a homogeneous medium, e.g., the wave equation describing the propagation and scattering of acoustic waves, can be reformulated as time-domain boundary integral equations. We propose an efficient implementation of a numerical discretization of such equations when the strong Huygens’ principle does not hold.For the numerical discretization, we make use of convolution quadrature in time and standard Galerkin boundary element method in space. The quadrature in time results in a discrete convolution of weights W_j with the boundary density evaluated at equally spaced time points. If the strong Huygens’ principle holds, W_j converge to 0 exponentially quickly for large enough j. If the strong Huygens’ principle does not hold, e.g., in even space dimensions or when some damping is present, the weights are never zero, thereby presenting a difficulty for efficient numerical computation.In this paper we prove that the kernels of the convolution weights approximate in a certain sense the time domain fundamental solution and that the same holds if both are differentiated in space. The tails of the fundamental solution being very smooth, this implies that the tails of the weights are smooth and can efficiently be interpolated. Further, we hint on the possibility to apply the fast and oblivious convolution quadrature algorithm of Schädle et al. to further reduce memory requirements for long-time computation. We discuss the efficient implementation of the whole numerical scheme and present numerical experiments.     

On-line and first fit colorings of graphs

A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called “on-line coloring.” The properties of on-line colorings are investigated in several classes of graphs. In many cases we find on-line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on-line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on-line algorithm: no on-line algorithm can color all trees by a bounded number of colors.     

Effective on-line coloring ofP 5-free graphs

An on-line algorithm is given that colors anyP ₅-free graph withf() colors, wheref is a function of the clique number of the graph.     

How many atoms can be defined by boxes?

We study the functionb(n, d), the maximal number of atoms defined byn d-dimensional boxes, i.e. parallelopipeds in thed-dimensional Euclidean space with sides parallel to the coordinate axes. We characterize extremal interval families definingb(n, 1)=2n-1 atoms and we show thatb(n, 2)=2n ²-6n+7. We prove that for everyd, exists and . Moreover, we obtainb*(3)=8/9.     

Tight embeddings of partial quadrilateral packings

Let f(n;C₄) be the smallest integer such that, given any set of edge disjoint quadrilaterals on n vertices, one can extend it into a complete quadrilateral decomposition by including at most f(n;C₄) additional vertices. It is known, and it is easy to show, that . Here we settle the longstanding problem that .     

[11C]-labeling of some caffeine derivatives for mapping adenosine A2a receptors by PET technique

[¹¹C]-labeled form of ten A_2a adenosine receptor specific 8-styryl-7-methyl-xanthine derivatives ([¹¹C]-caffeines) were synthesised by N-methylation of the corresponding 8-styryl-xanthine derivatives using [¹¹C]-methyl iodide in optimized reaction conditions. The results show that the [¹¹C]-methylations take place with excellent radiochemical yields (35–93%), and can be utilised easily in online preparations. These labeled ligands may facilitate the positron emission tomographic (PET) investigation of adenosine A_2a receptors.