Recurrences and graphs of recurrences

doktorski rad

• Naslov (hrvatski): Rekurzije i grafovi rekurzija
• Autor: Luka Podrug
• Mentor: Tomislav Došlić (mentor)
• Član povjerenstva: Vedran Krčadinac (predsjednik povjerenstva)
• Član povjerenstva: Snježana Majstorović Ergotić (član povjerenstva)
• Član povjerenstva: Tomislav Došlić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2024-05-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika
• Univerzalna decimalna klasifikacija (UDC): 51 - Matematika

Sažetak

In the first part of the dissertation, we count tilings of narrow strips in the hexagonal grid with a given number and type of tiles and investigate identities involving the obtained enumerating sequences. On the same substrate, we also study the number of tilings in which both the number and the shape of tiles are free. In both cases, the enumerating sequences satisfy linear recurrences with constant coefficients. In contrast to the first part where linear recurrences are obtained as a solution to the problem, the central part of the work uses them as a starting point. Namely, it is dedicated to the family of graphs that generalize Fibonacci cubes and whose number of vertices satisfies the recursion \(s_n = as_{n−1} + s_{n−2}\). We determine basic enumerative and metric properties and show that the family retains many desirable properties of Fibonacci cubes. Canonical decomposition and distribution of degrees will be investigated, as well as the existence of Hamiltonian paths and cycles. In the last part, we explore the possibility of extending the family of graphs to the Horadam recursion \(s_n = as_{n−1} +bs_{n−2}\).

Sažetak (hrvatski)

U prvom dijelu rada prebrojavamo popločenja uskih traka šesterokutne mreže s unaprijed poznatim brojem pločica određenog tipa i istražujemo mogućnost dobivanja identiteta o nizovima koje tako dobivamo. Preciznije, istražujemo na koliko se načina može popločati uska šesterokutna mreža koristeći samo monomere i dimere, a s unaprijed određenim brojem dimera. Nadalje, proučavamo sličan problem, ali umjesto horizontalnih dimera koristimo trimere, dobivene od tri uzastopna šesterokuta na mreži. Na istom supstratu promatramo i ukupni broj podjela promatrane šesterokutne mreže, tj. broj popločenja u kojima su i broj i oblik pločica proizvoljni. U ovom slučaju dobivamo jednostavan odgovor, broj načina na koji možemo podijeliti usku šesterokutnu mrežu odgovara Fibonaccijevim brojevima neparnog indexa. U svim slučajevima dobivaju se nizovi zadani linearnim rekurzijama. Središnji dio rada posvećen je familiji grafova koja poopćuje Fibonaccijeve kocke. Broj vrhova \(sn\) u grafovima takve familije također zadovoljava linearnu rekurziju, \(s_n = as_{n−1} + s_{n−2}\). Određujemo njihova osnovna enumerativna i metrička svojstava te pokazujemo da familija zadržava mnoga poželjna svojstva Fibonaccijevih kocaka. Određivanjem kanonske dekompozicije pokazujemo da se grafovi mogu dekomponirati u više grafova iste vrste, a manje dimenzije. Također, dekomponirajući ih u rešetke, pronalazimo još jednu vezu promatrane familije i Fibonaccijevih kocki. Određujemo i raspodjelu stupnjeva vrhova i dajemo nužne uvjete za postojanje Hamiltonovih putova i ciklusa. U posljednjem dijelu rada istražujemo mogućnost proširenja familije grafova na Horadamovu rekurziju \(s_n = as_{n−1} +bs_{n−2}\), i pokazujemo da se mnoga svojstva Fibonaccijevih i metalnih kocaka nasljeđuju za grafove te familije.

• Ključne riječi: tilings; Fibonacci cubes; Horadam recursion
• Ključne riječi (hrvatski): popločenja; Fibonaccijeve kocke; Horadamova rekurzija
• Jezik: engleski
• URN:NBN: urn:nbn:hr:217:529626
• Datum promocije: 2024
• Studijski program: Naziv: Matematika; Vrsta studija: sveučilišni; Stupanj studija: doktorski studij; Akademski / stručni naziv: doktor/doktorica u području prirodnih znanosti (dr. sc. natur.)
• Vrsta resursa: Tekst
• Opseg: v, 128 str.
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-06-27 08:41:57