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.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Solving the non-convexity problem in some shopping-time and human-capital models

Several works in the shopping-time and in the human-capital literature, due to the nonconcavity of the underlying Hamiltonian, use Örst-order conditions in dynamic optimization to characterize necessity, but not su¢ ciency, in intertemporal problems. In this work I choose one paper in each one of these two areas and show that optimality can be characterized by means of a simple aplication of Arrowís (1968) su¢ ciency theorem.

Difference variance dispersion graphs for comparing response surface designs with applications in food technology

Variance dispersion graphs have become a popular tool in aiding the choice of a response surface design. Often differences in response from some particular point, such as the expected position of the optimum or standard operating conditions, are more important than the response itself. We describe two examples from food technology. In the first, an experiment was conducted to find the levels of three factors which optimized the yield of valuable products enzymatically synthesized from sugars and to discover how the yield changed as the levels of the factors were changed from the optimum. In the second example, an experiment was conducted on a mixing process for pastry dough to discover how three factors affected a number of properties of the pastry, with a view to using these factors to control the process. We introduce the difference variance dispersion graph (DVDG) to help in the choice of a design in these circumstances. The DVDG for blocked designs is developed and the examples are used to show how the DVDG can be used in practice. In both examples a design was chosen by using the DVDG, as well as other properties, and the experiments were conducted and produced results that were useful to the experimenters. In both cases the conclusions were drawn partly by comparing responses at different points on the response surface.

Unsupervised manifold learning using Reciprocal kNN Graphs in image re-ranking and rank aggregation tasks

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

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.

Graphs of experimental results given in concentration of trace metals versus time in days

The impact of CO2 leakage on solubility and distribution of trace metals in seawater and sediment has been studied in lab scale chambers. Seven metals (Al, Cr, Ni, Pb, Cd, Cu, and Zn) were investigated in membrane-filtered seawater samples, and DGT samplers were deployed in water and sediment during the experiment. During the first phase (16 days), "dissolved" (<0.2 µm) concentrations of all elements increased substantially in the water. The increase in dissolved fractions of Al, Cr, Ni, Cu, Zn, Cd and Pb in the CO2 seepage chamber was respectively 5.1, 3.8, 4.5, 3.2, 1.4, 2.3 and 1.3 times higher than the dissolved concentrations of these metals in the control. During the second phase of the experiment (10 days) with the same sediment but replenished seawater, the dissolved fractions of Al, Cr, Cd, and Zn were partly removed from the water column in the CO2 chamber. DNi and DCu still increased but at reduced rates, while DPb increased faster than that was observed during the first phase. DGT-labile fractions (MeDGT) of all metals increased substantially during the first phase of CO2 seepage. DGT-labile fractions of Al, Cr, Ni, Cu, Zn, Cd and Pb were respectively 7.9, 2.0, 3.6, 1.7, 2.1, 1.9 and 2.3 times higher in the CO2 chamber than that of in the control chamber. AlDGT, CrDGT, NiDGT, and PbDGT continued to increase during the second phase of the experiment. There was no change in CdDGT during the second phase, while CuDGT and ZnDGT decreased by 30% and 25%, respectively in the CO2 chamber. In the sediment pore water, DGT labile fractions of all the seven elements increased substantially in the CO2 chamber. Our results show that CO2 leakage affected the solubility, particle reactivity and transformation rates of the studied metals in sediment and at the sediment-water interface. The metal species released due to CO2 acidification may have sufficiently long residence time in the seawater to affect bioavailability and toxicity of the metals to biota.

Analytical properties of horizontal visibility graphs in the Feigenbaum scenario

Time series are proficiently converted into graphs via the horizontal visibility (HV) algorithm, which prompts interest in its capability for capturing the nature of different classes of series in a network context. We have recently shown [B. Luque et al., PLoS ONE 6, 9 (2011)] that dynamical systems can be studied from a novel perspective via the use of this method. Specifically, the period-doubling and band-splitting attractor cascades that characterize unimodal maps transform into families of graphs that turn out to be independent of map nonlinearity or other particulars. Here, we provide an in depth description of the HV treatment of the Feigenbaum scenario, together with analytical derivations that relate to the degree distributions, mean distances, clustering coefficients, etc., associated to the bifurcation cascades and their accumulation points. We describe how the resultant families of graphs can be framed into a renormalization group scheme in which fixed-point graphs reveal their scaling properties. These fixed points are then re-derived from an entropy optimization process defined for the graph sets, confirming a suggested connection between renormalization group and entropy optimization. Finally, we provide analytical and numerical results for the graph entropy and show that it emulates the Lyapunov exponent of the map independently of its sign.