Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree ?. We use the Lovasz local lemma to show the following two results about colourings ? of the edges of the complete graph Kn. If for each vertex v of Kn the colouring ? assigns each colour to at most (n - 2)/(22.4?2) edges emanating from v, then there is a copy of G in Kn which is properly edge-coloured by ?. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409433, 2003]. On the other hand, if ? assigns each colour to at most n/(51?2) edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from ?. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Szekely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernandez, Procacci, and Scoppola [preprint, arXiv:0910.1824]. (c) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425436, 2012

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.

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.

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.

Analog circuit synthesis performing fast Pareto frontier exploration and analysis through 3D graphs

This paper presents a technique for performing analog design synthesis at circuit level providing feedback to the designer through the exploration of the Pareto frontier. A modified simulated annealing which is able to perform crossover with past anchor points when a local minimum is found which is used as the optimization algorithm on the initial synthesis procedure. After all specifications are met, the algorithm searches for the extreme points of the Pareto frontier in order to obtain a non-exhaustive exploration of the Pareto front. Finally, multi-objective particle swarm optimization is used to spread the results and to find a more accurate frontier. Piecewise linear functions are used as single-objective cost functions to produce a smooth and equal convergence of all measurements to the desired specifications during the composition of the aggregate objective function. To verify the presented technique two circuits were designed, which are: a Miller amplifier with 96 dB Voltage gain, 15.48 MHz unity gain frequency, slew rate of 19.2 V/mu s with a current supply of 385.15 mu A, and a complementary folded cascode with 104.25 dB Voltage gain, 18.15 MHz of unity gain frequency and a slew rate of 13.370 MV/mu s. These circuits were synthesized using a 0.35 mu m technology. The results show that the method provides a fast approach for good solutions using the modified SA and further good Pareto front exploration through its connection to the particle swarm optimization algorithm.

Statistical Mechanics of Monomer-Dimer Models on Complete and Erdös-Rényi Graphs

Nella tesi sono trattate due famiglie di modelli meccanico statistici su vari grafi: i modelli di spin ferromagnetici (o di Ising) e i modelli di monomero-dimero. Il primo capitolo è dedicato principalmente allo studio del lavoro di Dembo e Montanari, in cui viene risolto il modello di Ising su grafi aleatori. Nel secondo capitolo vengono studiati i modelli di monomero-dimero, a partire dal lavoro di Heilemann e Lieb,con l'intento di dare contributi nuovi alla teoria. I principali temi trattati sono disuguaglianze di correlazione, soluzioni esatte su alcuni grafi ad albero e sul grafo completo, la concentrazione dell'energia libera intorno al proprio valor medio sul grafo aleatorio diluito di Erdös-Rényi.

Learning with Kernels on Graphs: DAG-based kernels, data streams and RNA function prediction.

In many application domains data can be naturally represented as graphs. When the application of analytical solutions for a given problem is unfeasible, machine learning techniques could be a viable way to solve the problem. Classical machine learning techniques are defined for data represented in a vectorial form. Recently some of them have been extended to deal directly with structured data. Among those techniques, kernel methods have shown promising results both from the computational complexity and the predictive performance point of view. Kernel methods allow to avoid an explicit mapping in a vectorial form relying on kernel functions, which informally are functions calculating a similarity measure between two entities. However, the definition of good kernels for graphs is a challenging problem because of the difficulty to find a good tradeoff between computational complexity and expressiveness. Another problem we face is learning on data streams, where a potentially unbounded sequence of data is generated by some sources. There are three main contributions in this thesis. The first contribution is the definition of a new family of kernels for graphs based on Directed Acyclic Graphs (DAGs). We analyzed two kernels from this family, achieving state-of-the-art results from both the computational and the classification point of view on real-world datasets. The second contribution consists in making the application of learning algorithms for streams of graphs feasible. Moreover,we defined a principled way for the memory management. The third contribution is the application of machine learning techniques for structured data to non-coding RNA function prediction. In this setting, the secondary structure is thought to carry relevant information. However, existing methods considering the secondary structure have prohibitively high computational complexity. We propose to apply kernel methods on this domain, obtaining state-of-the-art results.

Spectral theory of differential operators on finite metric graphs and on bounded domains

Die vorliegende Arbeit widmet sich der Spektraltheorie von Differentialoperatoren auf metrischen Graphen und von indefiniten Differentialoperatoren auf beschränkten Gebieten. Sie besteht aus zwei Teilen. Im Ersten werden endliche, nicht notwendigerweise kompakte, metrische Graphen und die Hilberträume von quadratintegrierbaren Funktionen auf diesen betrachtet. Alle quasi-m-akkretiven Laplaceoperatoren auf solchen Graphen werden charakterisiert, und Abschätzungen an die negativen Eigenwerte selbstadjungierter Laplaceoperatoren werden hergeleitet. Weiterhin wird die Wohlgestelltheit eines gemischten Diffusions- und Transportproblems auf kompakten Graphen durch die Anwendung von Halbgruppenmethoden untersucht. Eine Verallgemeinerung des indefiniten Operators $-tfrac{d}{dx}sgn(x)tfrac{d}{dx}$ von Intervallen auf metrische Graphen wird eingeführt. Die Spektral- und Streutheorie der selbstadjungierten Realisierungen wird detailliert besprochen. Im zweiten Teil der Arbeit werden Operatoren untersucht, die mit indefiniten Formen der Art $langlegrad v, A(cdot)grad urangle$ mit $u,vin H_0^1(Omega)subset L^2(Omega)$ und $OmegasubsetR^d$ beschränkt, assoziiert sind. Das Eigenwertverhalten entspricht in Dimension $d=1$ einer verallgemeinerten Weylschen Asymptotik und für $dgeq 2$ werden Abschätzungen an die Eigenwerte bewiesen. Die Frage, wann indefinite Formmethoden für Dimensionen $dgeq 2$ anwendbar sind, bleibt offen und wird diskutiert.

Laplace operator on finite graphs and a network diffusion model for the progression of the Alzheimer disease

Nella tesi viene descritto il Network Diffusion Model, ovvero il modello di A. Ray, A. Kuceyeski, M. Weiner inerente i meccanismi di progressione della demenza senile. In tale modello si approssima l'encefalo sano con una rete cerebrale (ovvero un grafo pesato), si identifica un generale fattore di malattia e se ne analizza la propagazione che avviene secondo meccanismi analoghi a quelli di un'infezione da prioni. La progressione del fattore di malattia e le conseguenze macroscopiche di tale processo(tra cui principalmente l'atrofia corticale) vengono, poi, descritte mediante approccio matematico. I risultati teoretici vengono confrontati con quanto osservato sperimentalmente in pazienti affetti da demenza senile. Nella tesi, inoltre, si fornisce una panoramica sui recenti studi inerenti i processi neurodegenerativi e si costruisce il contesto matematico di riferimento del modello preso in esame. Si presenta una panoramica sui grafi finiti, si introduce l'operatore di Laplace sui grafi e si forniscono stime dall'alto e dal basso per gli autovalori. Al fine di costruire una cornice matematica completa si analizza la relazione tra caso discreto e continuo: viene descritto l'operatore di Laplace-Beltrami sulle varietà riemanniane compatte e vengono fornite stime dall'alto per gli autovalori dell'operatore di Laplace-Beltrami associato a tali varietà a partire dalle stime dall'alto per gli autovalori del laplaciano sui grafi finiti.