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.

INFERENCE FOR EIGENVALUES AND EIGENVECTORS OF GAUSSIAN SYMMETRIC MATRICES

This article presents maximum likelihood estimators (MLEs) and log-likelihood ratio (LLR) tests for the eigenvalues and eigenvectors of Gaussian random symmetric matrices of arbitrary dimension, where the observations are independent repeated samples from one or two populations. These inference problems are relevant in the analysis of diffusion tensor imaging data and polarized cosmic background radiation data, where the observations are, respectively, 3 x 3 and 2 x 2 symmetric positive definite matrices. The parameter sets involved in the inference problems for eigenvalues and eigenvectors are subsets of Euclidean space that are either affine subspaces, embedded submanifolds that are invariant under orthogonal transformations or polyhedral convex cones. We show that for a class of sets that includes the ones considered in this paper, the MLEs of the mean parameter do not depend on the covariance parameters if and only if the covariance structure is orthogonally invariant. Closed-form expressions for the MLEs and the associated LLRs are derived for this covariance structure.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

A note on the likelihood and moments of the skew-normal distribution

In this paper an alternative approach to the one in Henze (1986) is proposed for deriving the odd moments of the skew-normal distribution considered in Azzalini (1985). The approach is based on a Pascal type triangle, which seems to greatly simplify moments computation. Moreover, it is shown that the likelihood equation for estimating the asymmetry parameter in such model is generated as orthogonal functions to the sample vector. As a consequence, conditions for a unique solution of the likelihood equation are established, which seem to hold in more general setting.

Late Entry into HIV Care: Estimated Impact on AIDS Mortality Rates in Brazil, 2003-2006

Background: Worldwide, a high proportion of HIV-infected individuals enter into HIV care late. Here, our objective was to estimate the impact that late entry into HIV care has had on AIDS mortality rates in Brazil. Methodology/Principal Findings: We analyzed data from information systems regarding HIV-infected adults who sought treatment at public health care facilities in Brazil from 2003 to 2006. We initially estimated the prevalence of late entry into HIV care, as well as the probability of death in the first 12 months, the percentage of the risk of death attributable to late entry, and the number of avoidable deaths. We subsequently adjusted the annual AIDS mortality rate by excluding such deaths. Of the 115,369 patients evaluated, 50,358 (43.6%) had entered HIV care late, and 18,002 died in the first 12 months, representing a 16.5% probability of death in the first 12 months (95% CI: 16.3-16.7). By comparing patients who entered HIV care late with those who gained timely access, we found that the risk ratio for death was 49.5 (95% CI: 45.1-54.2). The percentage of the risk of death attributable to late entry was 95.5%, translating to 17,189 potentially avoidable deaths. Averting those deaths would have lowered the 2003-2006 AIDS mortality rate by 39.5%. Including asymptomatic patients with CD4(+) T cell counts >200 and <= 350 cells/mm(3) in the group who entered HIV care late increased this proportion by 1.8%. Conclusions/Significance: In Brazil, antiretroviral drugs reduced AIDS mortality by 43%. Timely entry would reduce that rate by a similar proportion, as well as resulting in a 45.2% increase in the effectiveness of the program for HIV care. The World Health Organization recommendation that asymptomatic patients with CD4(+) T cell counts <= 350 cells/mm(3) be treated would not have a significant impact on this scenario.

Gibbs random graphs on point processes

Consider a discrete locally finite subset Gamma of R(d) and the cornplete graph (Gamma, E), with vertices Gamma and edges E. We consider Gibbs measures on the set of sub-graphs with vertices Gamma and edges E` subset of E. The Gibbs interaction acts between open edges having a vertex in common. We study percolation properties of the Gibbs distribution of the graph ensemble. The main results concern percolation properties of the open edges in two cases: (a) when Gamma is sampled from a homogeneous Poisson process; and (b) for a fixed Gamma with sufficiently sparse points. (c) 2010 American Institute of Physics. [doi:10.1063/1.3514605]

ON GENERIC ROTATIONLESS DIFFEOMORPHISMS OF THE ANNULUS

Let f be a C(r)-diffeomorphism of the closed annulus A that preserves the orientation, the boundary components and the Lebesgue measure. Suppose that f has a lift (f) over tilde to the infinite strip (A) over tilde which has zero Lebesgue measure rotation number. If the rotation number of f restricted to both boundary components of (f) over tilde is positive, then for such a generic f (r >= 16), zero is an interior point of its rotation set. This is a partial solution to a conjecture of P. Boyland.

LIPSCHITZ CLASSIFICATION OF FUNCTIONS ON A HOLDER TRIANGLE

The problem of semialgebraic Lipschitz classification of quasihomogeneous polynomials on a Holder triangle is studied. For this problem, the ""moduli"" are described completely in certain combinatorial terms.

ON ISOMORPHIC CLASSIFICATIONS OF SPACES OF COMPACT OPERATORS

We prove an extension of the classical isomorphic classification of Banach spaces of continuous functions on ordinals. As a consequence, we give complete isomorphic classifications of some Banach spaces K(X,Y(n)), eta >= omega, of compact operators from X to Y(eta), the space of all continuous Y-valued functions defined in the interval of ordinals [1, eta] and equipped with the supremum norm. In particular, under the Continuum Hypothesis, we extend a recent result of C. Samuel by classifying, up to isomorphism, the spaces K(X(xi), c(0)(Gamma)(eta)), where omega <= xi < omega(1,) eta >= omega, Gamma is a countable set, X contains no complemented copy of l(1), X* has the Mazur property and the density character of X** is less than or equal to N(1).

Induced Modules for Affine Lie Algebras

We study induced modules of nonzero central charge with arbitrary multiplicities over affine Lie algebras. For a given pseudo parabolic subalgebra P of an affine Lie algebra G, our main result establishes the equivalence between a certain category of P-induced G-modules and the category of weight P-modules with injective action of the central element of G. In particular, the induction functor preserves irreducible modules. If P is a parabolic subalgebra with a finite-dimensional Levi factor then it defines a unique pseudo parabolic subalgebra P(ps), P subset of P(ps). The structure of P-induced modules in this case is fully determined by the structure of P(ps)-induced modules. These results generalize similar reductions in particular cases previously considered by V. Futorny, S. Konig, V. Mazorchuk [Forum Math. 13 (2001), 641-661], B. Cox [Pacific J. Math. 165 (1994), 269-294] and I. Dimitrov, V. Futorny, I. Penkov [Comm. Math. Phys. 250 (2004), 47-63].

ON THE THREE-DIMENSIONAL BLASCHKE-LEBESGUE PROBLEM

The width of a closed convex subset of n-dimensional Euclidean space is the distance between two parallel supporting hyperplanes. The Blaschke-Lebesgue problem consists of minimizing the volume in the class of convex sets of fixed constant width and is still open in dimension n >= 3. In this paper we describe a necessary condition that the minimizer of the Blaschke-Lebesgue must satisfy in dimension n = 3: we prove that the smooth components of the boundary of the minimizer have their smaller principal curvature constant and therefore are either spherical caps or pieces of tubes (canal surfaces).

ON SPACES OF COMPACT OPERATORS ON C(K, X) SPACES

This paper concerns the spaces of compact operators kappa(E,F), where E and F are Banach spaces C([1, xi], X) of all continuous X-valued functions defined on the interval of ordinals [1, xi] and equipped with the supremun norm. We provide sufficient conditions on X, Y, alpha, beta, xi and eta, with omega <= alpha <= beta < omega 1 for the following equivalence: (a) kappa(C([1, xi], X), C([1, alpha], Y)) is isomorphic to kappa(C([1,eta], X), C([1, beta], Y)), (b) beta < alpha(omega). In this way, we unify and extend results due to Bessaga and Pelczynski (1960) and C. Samuel (2009). Our result covers the case of the classical spaces X = l(p) and Y = l(q) with 1 < p, q < infinity.

COUNTABLE GROUPS OF ISOMETRIES ON BANACH SPACES

A group G is representable in a Banach space X if G is isomorphic to the group of isometrics on X in some equivalent norm. We prove that a countable group G is representable in a separable real Banach space X in several general cases, including when G similar or equal to {-1,1} x H, H finite and dim X >= vertical bar H vertical bar or when G contains a normal subgroup with two elements and X is of the form c(0)(Y) or l(p)(Y), 1 <= p < +infinity. This is a consequence of a result inspired by methods of S. Bellenot (1986) and stating that under rather general conditions on a separable real Banach space X and a countable bounded group G of isomorphisms on X containing -Id, there exists an equivalent norm on X for which G is equal to the group of isometrics on X. We also extend methods of K. Jarosz (1988) to prove that any complex Banach space of dimension at least 2 may be renormed with an equivalent complex norm to admit only trivial real isometries, and that any complexification of a Banach space may be renormed with an equivalent complex norm to admit only trivial and conjugation real isometrics. It follows that every real Banach space of dimension at least 4 and with a complex structure may be renormed to admit exactly two complex structures up to isometry, and that every real Cartesian square may be renormed to admit a unique complex structure up to isometry.