UNIVERSALITY OF RANDOM GRAPHS

We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

A Spatial Propensity Score Matching Evaluation of the Social Impacts of Sugarcane Growing on Municipalities in Brazil

The expansion of sugarcane growing in Brazil, spurred particularly by increased demand for ethanol, has triggered the need to evaluate the economic, social, and environmental impacts of this process, both on the country as a whole and on the growing regions. Even though the balance of costs and benefits is positive from an overall standpoint, this may not be so in specific producing regions, due to negative externalities. The objective of this paper is to estimate the effect of growing sugarcane on the human development index (HDI) and its sub-indices in cane producing regions. In the literature on matching effects, this is interpreted as the effect of the treatment on the treated. Location effects are controlled by spatial econometric techniques, giving rise to the spatial propensity score matching model. The authors analyze 424 minimum comparable areas (MCAs) in the treatment group, compared with 907 MCAs in the control group. The results suggest that the presence of sugarcane growing in these areas is not relevant to determine their social conditions, whether for better or worse. It is thus likely that public policies, especially those focused directly on improving education, health, and income generation/distribution, have much more noticeable effects on the municipal HDI.

Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --> N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

Speech Graphs Provide a Quantitative Measure of Thought Disorder in Psychosis

Background: Psychosis has various causes, including mania and schizophrenia. Since the differential diagnosis of psychosis is exclusively based on subjective assessments of oral interviews with patients, an objective quantification of the speech disturbances that characterize mania and schizophrenia is in order. In principle, such quantification could be achieved by the analysis of speech graphs. A graph represents a network with nodes connected by edges; in speech graphs, nodes correspond to words and edges correspond to semantic and grammatical relationships. Methodology/Principal Findings: To quantify speech differences related to psychosis, interviews with schizophrenics, manics and normal subjects were recorded and represented as graphs. Manics scored significantly higher than schizophrenics in ten graph measures. Psychopathological symptoms such as logorrhea, poor speech, and flight of thoughts were grasped by the analysis even when verbosity differences were discounted. Binary classifiers based on speech graph measures sorted schizophrenics from manics with up to 93.8% of sensitivity and 93.7% of specificity. In contrast, sorting based on the scores of two standard psychiatric scales (BPRS and PANSS) reached only 62.5% of sensitivity and specificity. Conclusions/Significance: The results demonstrate that alterations of the thought process manifested in the speech of psychotic patients can be objectively measured using graph-theoretical tools, developed to capture specific features of the normal and dysfunctional flow of thought, such as divergence and recurrence. The quantitative analysis of speech graphs is not redundant with standard psychometric scales but rather complementary, as it yields a very accurate sorting of schizophrenics and manics. Overall, the results point to automated psychiatric diagnosis based not on what is said, but on how it is said.

Propensity score matching approach to test the association of income inequality and mortality in Sao Paulo, Brazil

Background Support for the adverse effect of high income inequality on population health has come from studies that focus on larger areas, such as the US states, while studies at smaller geographical areas (eg, neighbourhoods) have found mixed results. Methods We used propensity score matching to examine the relationship between income inequality and mortality rates across 96 neighbourhoods (distritos) of the municipality of Sao Paulo, Brazil. Results Prior to matching, higher income inequality distritos (Gini >= 0.25) had slightly lower overall mortality rates (2.23 per 10 000, 95% CI -23.92 to 19.46) compared to lower income inequality areas (Gini <0.25). After propensity score matching, higher inequality was associated with a statistically significant higher mortality rate (41.58 per 10 000, 95% CI 8.85 to 73.3). Conclusion In Sao Paulo, the more egalitarian communities are among some of the poorest, with the worst health profiles. Propensity score matching was used to avoid inappropriate comparisons between the health status of unequal (but wealthy) neighbourhoods versus equal (but poor) neighbourhoods. Our methods suggest that, with proper accounting of heterogeneity between areas, income inequality is associated with worse population health in Sao Paulo.