Kode v razdaljno regularnih grafih

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2013
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[J. Vidali]
UDK:	519.172.4(043.3)
COBISS:	10141524
Št. ogledov:	75
Št. prenosov:	3
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Codes in distance-regular graphs
Sekundarni povzetek:	In this dissertation we study distance-regular graphs. In particular, we look for codes inside them and study triple intersection numbers that we can calculate when certain Krein parameters vanish. After introducing strongly regular graphs, distance-regular graphs, and exploring their algebraic structures through association schemes, we study the homogeneous property in the sense of Nomura. This gives us the first result, namely a proof of uniqueness of the Coxeter and Sylvester graphs which does not refer to the uniqueness of larger objects. The next results are a new characterization of the unknown Moore graph on 3250 vertices and a proof of nonexistence of a bipartite distance-regular graph of diameter 5, for which existence was unsettled. We give new bounds for the size of a code in a distance-regular graph, and look for graphs that might meet these bounds. In the case of diameter 3 we find two three-parameter families of intersection numbers which contain almost 40 feasible intersection arrays for small graphs and 4 known examples. Several feasible infinite subfamilies are derived from the two families. For some of them we show that the corresponding graphs must contain the desired codes, however this often leads to their nonexistence. Nevertheless, we are also left with a two-parameter Q-polynomial subfamily (which itself contains two feasible one-parameters subfamilies). Moreover, we can prove the existence of a completely regular code and an antipodal distance-regular subgraph. The latter is, of course, a very restrictive condition on the existence of the graph itself, but also gives us additional hints for a possible construction. Many known families of graphs can be parametrized with only four parameters, which are known as the classical parameters. We present several results on them and look at some small open cases. For two of them we show that no such graph exists. This time, the central theme are tight distance-regular graphs. We find out when distance-regular graphs with classical parameters are tight. This leads us to an alternative proof of the classification of antipodal distance-regular graphs with classical parameters. Using the local structure, we show nonexistence for a two-parameter family of feasible tight distance-regular graphs with classical parameters. We also give a conjecture about the local structure of tight distance-regular graphs with classical parameters. We conclude the dissertation with some possibilities for further work. Finally, an alternative construction for bilinear forms graphs is given.
Sekundarne ključne besede:	algebraic combinatorics;coding theory;distance-regular graphs;codes in a graph;triple intersection numbers;classical parameters;Q-polynomial property;Krein parameters;antipodal covers;Grafi;Disertacije;Kode;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Doktorska disertacija
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	XIV, 155 str.
ID:	24207374