Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Maxillary complete denture movement during chewing in mandibular removable partial denture wearers

To evaluate the pattern of maxillary complete denture movement during chewing for free-end removable partial dentures (RPD) wearers, compared to maxillary and mandibular complete denture wearers. Eighteen edentulous participants (group I) and 10 volunteers with bilateral posterior edentulous mandibles (group II) comprised the sample. Measures of mean denture movement and its variability were obtained by a kinesiographic instrument K6-I Diagnostic System, during the mastication of bread and a polysulphide block. Data were analysed using two-way anova (alpha = 0.05). Upper movement during chewing was significantly lower for group II, regardless of the test food. The test food did not influence the vertical or lateral position of the denture bases, but more anterior dislocation was found when polysulphide blocks were chewed. Group II presented lower intra-individual variability for the vertical axis. Vertical displacement was also more precise with bread as a test food. It can be concluded that mandibular free-end RPD wearers show smaller and more precise movements than mandibular complete denture wearers.

Evaluation of three indices for biofilm accumulation on complete dentures

Objectives: The objective of this study was to evaluate the accuracy and reproducibility of three complete denture biofilm indices (Prosthesis Hygiene Index; Jeganathan et al. Index; Budtz-J circle divide rgensen Index) by means of a computerised comparison method. Background: Clinical studies into denture hygiene have employed a large number of biofilm indices among their outcome variables. However, the knowledge about the validity of these indices is still scarce. Materials and methods: Sixty-two complete denture wearers were selected. The internal surfaces of the upper complete dentures were stained (5% erythrosine) and photographed. The slides were projected on paper, and the biofilm indices were applied over the photos by means of a scoring method. For the computerised method, the areas (total and biofilm-covered) were measured by dedicated software (Image Tool). In addition, to compare the results of the computerised method and Prosthetic Hygiene Index, a new scoring scale (including four and five graded) was introduced. For the Jeganathan et al. and Budtz-J circle divide rgensen indices, the original scales were used. Values for each index were compared with the computerised method by the Friedman test. Their reproducibility was measured by means of weighed kappa. Significance for both tests was set at 0.05. Results: The indices tested provided similar mean measures but they tended to overestimate biofilm coverage when compared with the computerised method (p < 0.001). Agreement between the Prosthesis Hygiene Index and the computerised method was not significant, regardless of the scale used. Jeghanathan et al. Index showed weak agreement, and consistent results were found for Budtz-Jorgensen Index (kappa = 0.19 and 0.39 respectively). Conclusion: Assessment of accuracy for the biofilm indices showed instrument bias that was similar among the tested methods. Weak inter-instrument reproducibility was found for the indices, except for the Budtz-J circle divide rgensen Index. This should be the method of choice for clinical studies when more sophisticated approaches are not possible.

In vitro and clinical evaluation of specific dentifrices for complete denture hygiene

To study the physical properties of two experimental dentifrices for complete denture hygiene, their effect on denture biofilm removal and antimicrobial properties by means of a clinical trial. The experimental dentifrices comprised two compositions. One was based on the addition of 1% chloramine T (D1) and the other on the presence of 0.01% fluorosurfactant (D2). Measurements of density, pH, consistency, rheological features and abrasiveness were conducted. Sixty complete denture wearers were randomly assigned to three groups and were instructed to brush their dentures with a specific toothbrush: (1) Water (control); (2) D1; or (3) D2. Each method was used for 21 days. Denture biofilm was disclosed by a 1% neutral red solution and quantified by means of digital photos taken from the internal surface. Microbiological assessment was conducted to quantify Candida sp. and mutans streptococci. Data were evaluated by one-way anova and Tukey HSD, or Kruskal-Wallis (alpha = 0.05). Both dentifrices decreased biofilm coverage when compared with the control group. D1 was the most efficacious treatment to reduce mutans streptococci, whereas D2 showed an intermediate outcome (anova, p < 0.040). No treatment influenced Candida albicans or non-albicans species (Kruskal-Wallis, p = 0.163 and 0.746, respectively). It can be concluded that brushing complete dentures with the experimental dentifrices tested could be effective for the removal of denture biofilm.

A New Yardstick for Rating Dental Arch Relationship in Patients With Complete Bilateral Cleft Lip and Palate

Objective: To develop yardsticks for assessment of dental arch relationship in young individuals with repaired complete bilateral cleft lip and palate appropriate to different stages of dental development. Participants: Eleven cleft team orthodontists from five countries worked on the projects for 4 days. A total of 776 sets of standardized plaster models from 411 patients with operated complete bilateral cleft lip and palate were available for the exercise. Statistics: The interexaminer reliability was calculated using weighted kappa statistics. Results: The interrater weighted kappa scores were between .74 and .92, which is in the ""good"" to ""very good"" categories. Conclusions: Three bilateral cleft lip and palate yardsticks for different developmental stages of the dentition were made: one for the deciduous dentition (6-year-olds` yardstick), one for early mixed dentition (9-year-olds` yardstick), and one for early permanent dentition (12-year-olds` yardstick).

Tooth Abnormalities of Number and Position in the Permanent Dentition of Patients With Complete Bilateral Cleft Lip and Palate

Objective: To radiographically evaluate the prevalence of tooth abnormalities of number and position in the permanent dentition of individuals with complete bilateral cleft lip and palate. Design: Cross-sectional retrospective. Setting: Hospital for Rehabilitation of Craniofacial Anomalies, University of Sao Paulo, Bauru, Brazil. Patients: Two hundred five individuals with complete bilateral cleft lip and palate. Interventions: Analysis of patient records and panoramic radiographs. Main outcome measures: Evaluation of hypodontia and supernumerary teeth and analysis of the position of the permanent maxillary lateral incisor in relation to the alveolar cleft. Results: Hypodontia was observed in 144 patients (70.2%), and the highest prevalence was observed for the maxillary lateral incisor. When both lateral incisors were present (43%), they were primarily located on the distal side of the cleft (25%). Supernumerary teeth were observed in 11.7% of individuals. Conclusion: Patients with cleft lip and palate presented high prevalence of hypodontia and supernumerary teeth. The prevailing characteristics of their location may suggest the presence of a similar genetic component for the occurrence of hypodontia and cleft.

A Survey on Graphical Methods for Classification Predictive Performance Evaluation

Predictive performance evaluation is a fundamental issue in design, development, and deployment of classification systems. As predictive performance evaluation is a multidimensional problem, single scalar summaries such as error rate, although quite convenient due to its simplicity, can seldom evaluate all the aspects that a complete and reliable evaluation must consider. Due to this, various graphical performance evaluation methods are increasingly drawing the attention of machine learning, data mining, and pattern recognition communities. The main advantage of these types of methods resides in their ability to depict the trade-offs between evaluation aspects in a multidimensional space rather than reducing these aspects to an arbitrarily chosen (and often biased) single scalar measure. Furthermore, to appropriately select a suitable graphical method for a given task, it is crucial to identify its strengths and weaknesses. This paper surveys various graphical methods often used for predictive performance evaluation. By presenting these methods in the same framework, we hope this paper may shed some light on deciding which methods are more suitable to use in different situations.

Topological invariants of isolated complete intersection curve singularities

In this paper we present some formulae for topological invariants of projective complete intersection curves with isolated singularities in terms of the Milnor number, the Euler characteristic and the topological genus. We also present some conditions, involving the Milnor number and the degree of the curve, for the irreducibility of complete intersection curves.

X-ray spectrometry: a powerful tool for the measurement of complete fusion of weakly bound nuclei

We describe how the method of detection of delayed K x-rays produced by the electron capture decay of the residual nuclei can be a powerful tool in the investigation of the effect of the breakup process on the complete fusion (CF) cross-section of weakly bound nuclei at energies close to the Coulomb barrier. This is presently one of the most interesting subjects under investigation in the field of low-energy nuclear reactions, and the difficult experimental task of separating CF from the incomplete fusion (ICF) of one of the breakup fragments can be achieved by the x-ray spectrometry method. We present results for the fusion of the (9)Be + (144)Sm system. Copyright (c) 2008 John Wiley & Sons, Ltd.

Effect of Age on Outcome of Reduced-Intensity Hematopoietic Cell Transplantation for Older Patients With Acute Myeloid Leukemia in First Complete Remission or With Myelodysplastic Syndrome

Purpose Acute myelogenous leukemia (AML) and myelodysplastic syndrome (MDS) primarily afflict older individuals. Hematopoietic cell transplantation (HCT) is generally not offered because of concerns of excess morbidity and mortality. Reduced-intensity conditioning (RIC) regimens allow increased use of allogeneic HCT for older patients. To define prognostic factors impacting long-term outcomes of RIC regimens in patients older than age 40 years with AML in first complete remission or MDS and to determine the impact of age, we analyzed data from the Center for International Blood and Marrow Transplant Research (CIBMTR). Patients and Methods We reviewed data reported to the CIBMTR (1995 to 2005) on 1,080 patients undergoing RIC HCT. Outcomes analyzed included neutrophil recovery, incidence of acute or chronic graft-versus-host disease (GVHD), nonrelapse mortality (NRM), relapse, disease-free survival (DFS), and overall survival (OS). Results Univariate analyses demonstrated no age group differences in NRM, grade 2 to 4 acute GVHD, chronic GVHD, or relapse. Patients age 40 to 54, 55 to 59, 60 to 64, and >= 65 years had 2-year survival rates as follows: 44% (95% Cl, 37% to 52%), 50% (95% Cl, 41% to 59%), 34% (95% Cl, 25% to 43%), and 36% (95% Cl, 24% to 49%), respectively, for patients with AML (P = .06); and 42% (95% Cl, 35% to 49%), 35% (95% Cl, 27% to 43%), 45% (95% Cl, 36% to 54%), and 38% (95% Cl, 25% to 51%), respectively, for patients with MDS (P = .37). Multivariate analysis revealed no significant impact of age on NRM, relapse, DFS, or OS (all P>.3). Greater HLA disparity adversely affected 2-year NRM, DFS, and OS. Unfavorable cytogenetics adversely impacted relapse, DFS, and OS. Better pre-HCT performance status predicted improved 2-year OS. Conclusion With these similar outcomes observed in older patients, we conclude that older age alone should not be considered a contraindication to HCT.

Texture analysis using graphs generated by deterministic partially self-avoiding walks

Texture is one of the most important visual attributes for image analysis. It has been widely used in image analysis and pattern recognition. A partially self-avoiding deterministic walk has recently been proposed as an approach for texture analysis with promising results. This approach uses walkers (called tourists) to exploit the gray scale image contexts in several levels. Here, we present an approach to generate graphs out of the trajectories produced by the tourist walks. The generated graphs embody important characteristics related to tourist transitivity in the image. Computed from these graphs, the statistical position (degree mean) and dispersion (entropy of two vertices with the same degree) measures are used as texture descriptors. A comparison with traditional texture analysis methods is performed to illustrate the high performance of this novel approach. (C) 2011 Elsevier Ltd. All rights reserved.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs

The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks` dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.