Tutte's 5-flow conjecture

The aim of this thesis is to show and put together the results, obtained so far, useful to tackle a conjecture of graph theory proposed in 1954 by William Thomas Tutte. The conjecture in question is Tutte's 5-flow conjecture, which states that every bridgeless graph admits a nowhere-zero 5-flow, namely a flow with non-zero integer values between -4 and 4. We will start by giving some basics on graph theory, useful for the followings, and proving some results about flows on oriented graphs and in particular about the flow polynomial. Next we will treat two cases: graphs embeddable in the plane $\mathbb{R}^2$ and graphs embeddable in the projective plane $\mathbb{P}^2$. In the first case we will see the correlation between flows and colorings and prove a theorem even stronger than Tutte's conjecture, using the 4-color theorem. In the second case we will see how in 1984 Richard Steinberg used Fleischner's Splitting Lemma to show that there can be no minimal counterexample of the conjecture in the case of graphs in the projective plane. In the fourth chapter we will look at the theorems of François Jaeger (1976) and Paul D. Seymour (1981). The former proved that every bridgeless graph admits a nowhere-zero 8-flow, the latter managed to go even further showing that every bridgeless graph admits a nowhere-zero 6-flow. In the fifth and final chapter there will be a short introduction to the Tutte polynomial and it will be shown how it is related to the flow polynomial via the Recipe Theorem. Finally we will see some applications of flows through the study of networks and their properties.

Absolute Hodge cycles and Deligne's principle b

I cicli di Hodge assoluti sono stati utilizzati da Deligne per dividere la congettura di Hodge in due sotto-congetture. La prima dice che tutte le classi di Hodge su una varietà complessa proiettiva liscia sono assolute, la seconda che le classi assolute sono algebriche. Deligne ha dato risposta affermativa alla prima sottocongettura nel caso delle varietà abeliane. La dimostrazione si basa su due teoremi, conosciuti rispettivamente come Principio A e Principio B. In questo lavoro vengono presentate la teoria delle classi di Hodge assolute e la dimostrazione del Principio B.

Transizioni di fase nell'allenamento delle Macchine di Boltzmann Ristrette

In this thesis, we dealt with Restricted Boltzmann Machines with binary priors as models of unsupervised learning, analyzing the role of the number of hidden neurons on the amount of examples needed for a successful training. We simulated a teacher-student scenario and calculated the efficiency of the machine under the assumption of replica symmetry to study the location of the critical threshold beyond which learning begins. Our results confirm the conjecture that, in the absence of correlation between the weights of the data-generating machine, the critical threshold does not depend on the number of hidden units (as long as it is finite) and thus on the complexity of the data. Instead, the presence of correlation significantly reduces the amount of examples needed for training. We have shown that this effect becomes more pronounced as the number of hidden units increases. The entire analysis is supported by numerical simulations that corroborate the results.