O treh dolgotrajnih problemov v teoriji ekstremalnih grafov

In this project three open problems in extremal graph theory will be considered.

Let vt(k, d) be the order of the largest vertex-transitive k-regular graph with a diameter d.

We will prove that new approaches from number theory (an application of theorems which concern the asymptotic density of a set) will lead to a negative answer of the following open question:  Is it true that vt(k, d) = n(k, d) for infinitely many pairs of k ≥ 3 and d ≥ 3 ?

Moreover, there is a hope that, if we apply spectral analysis (block matrices as adjacency matrices of certain subgraphs) we can prove the non-existence of the long missing (57, 2)- Moore graph. The plan is to find the multiplicities of the eigenvalues of a certain subgraph of G and to show that at least one of them is not a positive integer.

Bermond in Bollobas stated the following question which concerns the Degree/Diameter Problem: Let c > 0 be a positive integer. Are there numbers k and d, such that n(k, d) ≤ M(k, d) − c?  We will give an answer of this long standing question by combining combinatorial and real analysis. Based on this method, we will show that the cages are expanders, that is, the cages are graphs with very high connectivity.

All these results will find a very nice application in the topology of a network (such as a telecommunication, multiprocessor, or local area network).