Cycling in hypercubes

doctoral thesis

Tilen Marc (Avtor), Sandi Klavžar (Mentor), Kolja Knauer (Komentor)

Povzetek

V disertaciji preučujemo izometrične podgrafe hiperkock, imenovane delne kocke. Osredotočimo se na tri področja: razumevanju ciklov v takih podgrafih, raziskovanju obstoječih družin ter lastnosti delnih kock in iskanju simetričnih primerov. V delu pokažemo, da imajo konveksni cikli v delnih kockah veliko zanimivih lastnosti, saj na primer napenjajo enostavno povezan prostor in se hkrati prepletajo in tvorijo traverze. Z analizo le teh dokažemo rezultate o strukturi in stopnjah delnih kock, ki imajo le daljše cikle. To znanje uporabimo za klasifikacijo kubičnih, vozliščno tranzitivnih delnih kock in za vzpostavitev povezave med delnimi kockami, ki vsebujejo zrcalne simetrije, in končnimi Coxeterjevimi grupami. Nadalje preučujemo različne družine delnih kock in pokažemo na povezave med razporeditvami hiperravnin v evklidskem prostoru, antipodalnimi grafi, orientiranimi matroidi, medianskimi grafi in mnogimi drugimi strukturami najdenimi v delnih kockah. Z glavnim orodjem te disertacije, minorji delnih kock, dokažemo nove karakterizacije različnih družin delnih kock in oblikujemo zemljevid, ki določa hierarhične lastnosti le teh. Disertacijo zaključimo z izračunom in analizo lastnosti majhnih delnih kock omejenih z njihovo izometrično dimenzijo in dokažemo, da je problem iskanja izomorfizma dveh medianskih grafov GI poln problem.

Ključne besede

mathematics;graph theory;partial cubes;metric properties;convex subgraphs;minors;oriented matroids;antipodality;vertex-transitive graphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2018
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[T. Marc]
UDK:	519.17(043.3)
COBISS:	18363993
Št. ogledov:	1310
Št. prenosov:	502
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Kroženje v hiperkockah
Sekundarni povzetek:	We study isometric subgraphs found in hypercubes, called partial cubes. We focus on three aspects: understanding the cycle space of such subgraphs, exploring established subfamilies and properties, and finding symmetric ones. As we show, convex cycles in partial cubes have many intriguing properties, from spanning a simply connected space to forming complex substructures such as intertwinings and traverses. We analyze partial cubes with high girth to obtain results on the structure and degree of such graphs. This knowledge is transferred to symmetric partial cubes to obtain a complete classification of cubic, vertex-transitive ones and to find a connection between partial cubes having mirror automorphisms and finite Coxeter groups. We study various subfamilies of partial cubes to expose a connection between (pseudo-) hyperplane arrangements, antipodal subgraphs, oriented matroids, median graphs, and many other structures found in partial cubes. With our main tool, the concept of partial cube minors, we create a map of partial cubes determining the hierarchical structure of subfamilies of partial cubes, and providing new characterizations and generalizations. Lastly, computational and enumerative properties of partial cubes bounded by their isometric dimension are discussed, together with a result showing that finding isomorphisms of graphs is GI-complete already for one of the simplest classes of partial cubes: median graphs.
Sekundarne ključne besede:	matematika;teorija grafov;delne kocke;metrične lastnosti;konveksni podgrafi;minorji;orientirani matroidi;antipodalnost;vozliščno tranzitivni grafi;Grafi;Disertacije;
Vrsta dela (COBISS):	Doktorsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. Ljubljana, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 3. stopnja
Strani:	92 str.
ID:	10932981