On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

On the asymptotic enumeration of accessible automata

We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Synchronization of Discrete-Time Chaotic Systems in Bandlimited Channels

Over the last couple of decades, many methods for synchronizing chaotic systems have been proposed with communications applications in view. Yet their performance has proved disappointing in face of the nonideal character of usual channels linking transmitter and receiver, that is, due to both noise and signal propagation distortion. Here we consider a discrete-time master-slave system that synchronizes despite channel bandwidth limitations and an allied communication system. Synchronization is achieved introducing a digital filter that limits the spectral content of the feedback loop responsible for producing the transmitted signal. Copyright (C) 2009 Marcio Eisencraft et al.

Bayesian online algorithms for learning in discrete Hidden Markov Models

We propose and analyze two different Bayesian online algorithms for learning in discrete Hidden Markov Models and compare their performance with the already known Baldi-Chauvin Algorithm. Using the Kullback-Leibler divergence as a measure of generalization we draw learning curves in simplified situations for these algorithms and compare their performances.

Discrete approximation to the global spectrum of the tangent operator for flow past a circular cylinder

This paper deals with the calculation of the discrete approximation to the full spectrum for the tangent operator for the stability problem of the symmetric flow past a circular cylinder. It is also concerned with the localization of the Hopf bifurcation in laminar flow past a cylinder, when the stationary solution loses stability and often becomes periodic in time. The main problem is to determine the critical Reynolds number for which a pair of eigenvalues crosses the imaginary axis. We thus present a divergence-free method, based on a decoupling of the vector of velocities in the saddle-point system from the vector of pressures, allowing the computation of eigenvalues, from which we can deduce the fundamental frequency of the time-periodic solution. The calculation showed that stability is lost through a symmetry-breaking Hopf bifurcation and that the critical Reynolds number is in agreement with the value presented in reported computations. (c) 2007 IMACS. Published by Elsevier B.V. All rights reserved.

The pareto-stability concept is a natural solution concept for discrete matching markets with indifferences

In a decentralized setting the game-theoretical predictions are that only strong blockings are allowed to rupture the structure of a matching. This paper argues that, under indifferences, also weak blockings should be considered when these blockings come from the grand coalition. This solution concept requires stability plus Pareto optimality. A characterization of the set of Pareto-stable matchings for the roommate and the marriage models is provided in terms of individually rational matchings whose blocking pairs, if any, are formed with unmatched agents. These matchings always exist and give an economic intuition on how blocking can be done by non-trading agents, so that the transactions need not be undone as agents reach the set of stable matchings. Some properties of the Pareto-stable matchings shared by the Marriage and Roommate models are obtained.

UNIFORM DISSIPATIVENESS, ROBUST SYNCHRONIZATION AND LOCATION OF THE ATTRACTOR OF PARAMETRIZED NONAUTONOMOUS DISCRETE SYSTEMS

In this series of papers, we study issues related to the synchronization of two coupled chaotic discrete systems arising from secured communication. The first part deals with uniform dissipativeness with respect to parameter variation via the Liapunov direct method. We obtain uniform estimates of the global attractor for a general discrete nonautonomous system, that yields a uniform invariance principle in the autonomous case. The Liapunov function is allowed to have positive derivative along solutions of the system inside a bounded set, and this reduces substantially the difficulty of constructing a Liapunov function for a given system. In particular, we develop an approach that incorporates the classical Lagrange multiplier into the Liapunov function method to naturally extend those Liapunov functions from continuous dynamical system to their discretizations, so that the corresponding uniform dispativeness results are valid when the step size of the discretization is small. Applications to the discretized Lorenz system and the discretization of a time-periodic chaotic system are given to illustrate the general results. We also show how to obtain uniform estimation of attractors for parametrized linear stable systems with nonlinear perturbation.

Continuum, Discrete, and Explicit Solvation Models for Describing the Low-Lying Absorption Spectrum of the Pterin Acid in Aqueous Environment

The absorption spectrum of the acid form of pterin in water was investigated theoretically. Different procedures using continuum, discrete, and explicit models were used to include the solvation effect on the absorption spectrum, characterized by two bands. The discrete and explicit models used Monte Carlo simulation to generate the liquid structure and time-dependent density functional theory (B3LYP/6-31G+(d)) to obtain the excitation energies. The discrete model failed to give the correct qualitative effect on the second absorption band. The continuum model, in turn, has given a correct qualitative picture and a semiquantitative description. The explicit use of 29 solvent molecules, forming a hydration shell of 6 angstrom, embedded in the electrostatic field of the remaining solvent molecules, gives absorption transitions at 3.67 and 4.59 eV in excellent agreement with the S(0)-S(1) and S(0)-S(2) absorption bands at of 3.66 and 4.59 eV, respectively, that characterize the experimental spectrum of pterin in water environment. (C) 2010 Wiley Periodicals, Inc. Int J Quantum Chem 110: 2371-2377, 2010

A note on a practical relationship between filter coefficients and scaling and wavelet functions of Discrete Wavelet Transforms

In this paper, the relationship between the filter coefficients and the scaling and wavelet functions of the Discrete Wavelet Transform is presented and exemplified from a practical point-of-view. The explanations complement the wavelet theory, that is well documented in the literature, being important for researchers who work with this tool for time-frequency analysis. (c) 2011 Elsevier Ltd. All rights reserved.

Dually discrete spaces

A neighbourhood assignment in a space X is a family O = {O-x: x is an element of X} of open subsets of X such that X is an element of O-x for any x is an element of X. A set Y subset of X is a kernel of O if O(Y) = U{O-x: x is an element of Y} = X. We obtain some new results concerning dually discrete spaces, being those spaces for which every neighbourhood assignment has a discrete kernel. This is a strictly larger class than the class of D-spaces of [E.K. van Douwen, W.F. Pfeffer, Some properties of the Sorgenfrey line and related spaces, Pacific J. Math. 81 (2) (1979) 371-377]. (c) 2008 Elsevier B.V. All rights reserved.

Examples from trees, related to discrete subsets, pseudo-radiality and omega-boundedness

We construct some examples using trees. Some of them are consistent counterexamples for the discrete reflection of certain topological properties. All the properties dealt with here were already known to be non-discretely reflexive if we assume CH and we show that the same is true assuming the existence of a Suslin tree. In some cases we actually get some ZFC results. We construct also, using a Suslin tree, a compact space that is pseudo-radial but it is not discretely generated. With a similar construction, but using an Aronszajn tree, we present a ZFC space that is first countable, omega-bounded but is not strongly w-bounded, answering a question of Peter Nyikos. (C) 2008 Elsevier B.V. All rights reserved.

Design methodology for multi-pumped discrete Raman amplifiers: case-study employing photonic crystal fibers

This paper proposes a new design methodology for discrete multi-pumped Raman amplifier. In a multi-objective optimization scenario, in a first step the whole solution-space is inspected by a CW analytical formulation. Then, the most promising solutions are fully investigated by a rigorous numerical treatment and the Raman amplification performance is thus determined by the combination of analytical and numerical approaches. As an application of our methodology we designed an photonic crystal fiber Raman amplifier configuration which provides low ripple, high gain, clear eye opening and a low power penalty. The amplifier configuration also enables to fully compensate the dispersion introduced by a 70-km singlemode fiber in a 10 Gbit/s system. We have successfully obtained a configuration with 8.5 dB average gain over the C-band and 0.71 dB ripple with almost zero eye-penalty using only two pump lasers with relatively low pump power. (C) 2009 Optical Society of America

UNIQUENESS AND NONUNIQUENESS RESULTS FOR A CERTAIN CLASS OF ALMOST PERIODIC DISTRIBUTIONS

We consider distributions u is an element of S'(R) of the form u(t) = Sigma(n is an element of N) a(n)e(i lambda nt), where (a(n))(n is an element of N) subset of C and Lambda = (lambda n)(n is an element of N) subset of R have the following properties: (a(n))(n is an element of N) is an element of s', that is, there is a q is an element of N such that (n(-q) a(n))(n is an element of N) is an element of l(1); for the real sequence., there are n(0) is an element of N, C > 0, and alpha > 0 such that n >= n(0) double right arrow vertical bar lambda(n)vertical bar >= Cn(alpha). Let I(epsilon) subset of R be an interval of length epsilon. We prove that for given Lambda, (1) if Lambda = O(n(alpha)) with alpha < 1, then there exists epsilon > 0 such that u vertical bar I(epsilon) = 0 double right arrow u 0; (2) if Lambda = O(n) is uniformly discrete, then there exists epsilon > 0 such that u vertical bar I(epsilon) = 0 double right arrow u 0; (3) if alpha > 1 and. is uniformly discrete, then for all epsilon > 0, u vertical bar I(epsilon) = 0 double right arrow u = 0. Since distributions of the above mentioned form are very common in engineering, as in the case of the modeling of ocean waves, signal processing, and vibrations of beams, plates, and shells, those uniqueness and nonuniqueness results have important consequences for identification problems in the applied sciences. We show an identification method and close this article with a simple example to show that the recovery of geometrical imperfections in a cylindrical shell is possible from a measurement of its dynamics.

Stability and ergodicity of piecewise deterministic Markov processes

The main goal of this paper is to establish some equivalence results on stability, recurrence, and ergodicity between a piecewise deterministic Markov process ( PDMP) {X( t)} and an embedded discrete-time Markov chain {Theta(n)} generated by a Markov kernel G that can be explicitly characterized in terms of the three local characteristics of the PDMP, leading to tractable criterion results. First we establish some important results characterizing {Theta(n)} as a sampling of the PDMP {X( t)} and deriving a connection between the probability of the first return time to a set for the discrete-time Markov chains generated by G and the resolvent kernel R of the PDMP. From these results we obtain equivalence results regarding irreducibility, existence of sigma-finite invariant measures, and ( positive) recurrence and ( positive) Harris recurrence between {X( t)} and {Theta(n)}, generalizing the results of [ F. Dufour and O. L. V. Costa, SIAM J. Control Optim., 37 ( 1999), pp. 1483-1502] in several directions. Sufficient conditions in terms of a modified Foster-Lyapunov criterion are also presented to ensure positive Harris recurrence and ergodicity of the PDMP. We illustrate the use of these conditions by showing the ergodicity of a capacity expansion model.