In this thesis we consider the problem of decomposing the complete graph on v vertices into subgraphs, all of which are isomorphic to a given graph H. The subgraphs of the decomposition are called blocks. According to the definition of a decomposition each edge of the complete graph must occur in precisely one blocjk of the decomposition. This notion generalizes the idea of a block design. From this point of view a block design is a decomposition of the complete graph into complete subgraphs, all having equal cardinality k. In the definition of a block design blocks have no additional structure other than that of bare subsets of the set of points. Therefore, the notion of an H-design which is studied in this thesis forces blocks to inherit a certain structure, namely that of being a copy of the graph H, which, in some sense, determines the “shape” of the blocks. One of the main problems in the theory of classical block designs as well as in the theory of H-designs consists in the determination of the existence spectrum, that is the determination of the values v for which the block design exists. Open problems related to the existence spectrum do survive, as it is known, even for incidence structures that were studied long before block designs, say, for instance, finite projective planes. In the case of interest for this thesis, the request is to establish, for a given graph H, the existence spectrum for H-designs, that is the set of all values v for which an H-deecomposition of the complete graph on v vertices exists. A contribution to the determination of the spectrum is obtained in case H is a connected graph with 7 vertices and 7 edges containing a cycle of length 3. This case remains open from previous investigations in which the graph H is smaller or contains a longer cycle. Generalizations in various directions are also approached, assuming a slight change in the type of the graph H or assuming special incidence features for the decomposition, such as those that generally involve some kind of balance, typically the request that a certain parameter of the decomposition remain uniform consideration. In our specific context the decomposition is balanced if the number of blocks containing any given vertex is constant.

In questa tesi si prende in considerazione il problema della decomposizione del grafo completo con v vertici in sottografi tutti isomorfi a un assegnato grafo H. I sottografi della decomposizione vengono detti blocchi. Secondo la definizione di decomposizione ogni spigolo del grafo completo si deve pertanto collocare in esattamente un blocco della decomposizione. Questa nozione generalizza l’idea di disegno a blocchi che da questo punto di vista diventa una decomposizione del grafo completo in sottografi completi tutti della stessa cardinalità k. Nella definizione di disegno a blocchi questi ultimi sono privi di struttura, vale a dire sono solo pensati come sottoinsiemi dell’insieme dei punti. Nella nozione di H-disegno studiata in questa tesi i blocchi vengono dunque ad assumere una struttura, quella dettata dal grafo H, che dunque in un certo senso determina la “forma” dei blocchi. Uno dei problemi principali tanto nella teoria dei disegni a blocchi classici quanto nella teoria degli H-disegni consiste nella determinazione dello spettro di esistenza, cioè la determinazione dei valori di v per cui il disegno a blocchi esiste. Problemi aperti relativi allo spettro di esistenza sussistono, come è noto, anche per strutture di incidenza studiate ancora prima dei disegni a blocchi, ad esempio i piani proiettivi finiti. Nel caso trattato in questa tesi si tratta di stabilire, per un fissato grafo H, quale sia lo spettro di esistenza degli H-disegni, cioè l’insieme dei valori di v per cui una H-deecomposizione del grafo completo con v vertici esiste. Si dà un contributo al problema della determinazione dello spettro nel caso in cui il grafo H sia un grafo connesso con 7 vertici e 7 spigoli dotato di un ciclo di lunghezza 3. Questo caso rimane aperto rispetto a indagini precedenti, nelle quali il grafo H è più piccolo oppure possiede un ciclo di lunghezza maggiore. Vengono anche affrontate generalizzazioni in varie direzioni, cambiando lievemente la tipologia del grafo H oppure richiedendo che la decomposizione abbia proprietà di incidenza particolari che vanno generalmente sotto il nome di proprietà di bilanciamento, cioè proprietà relative all’uniformità di certi parametri della decomposzione. Nel caso specifico la decomposizione è bilanciata se risulta costante il numero di blocchi che contengono ciascun vertice.

Strutture di incidenza finite con blocchi di forma assegnata / Franco Fernicola , 2020 Feb 28. 32. ciclo, Anno Accademico 2018/2019.

Strutture di incidenza finite con blocchi di forma assegnata

FERNICOLA, FRANCO
2020

Abstract

In this thesis we consider the problem of decomposing the complete graph on v vertices into subgraphs, all of which are isomorphic to a given graph H. The subgraphs of the decomposition are called blocks. According to the definition of a decomposition each edge of the complete graph must occur in precisely one blocjk of the decomposition. This notion generalizes the idea of a block design. From this point of view a block design is a decomposition of the complete graph into complete subgraphs, all having equal cardinality k. In the definition of a block design blocks have no additional structure other than that of bare subsets of the set of points. Therefore, the notion of an H-design which is studied in this thesis forces blocks to inherit a certain structure, namely that of being a copy of the graph H, which, in some sense, determines the “shape” of the blocks. One of the main problems in the theory of classical block designs as well as in the theory of H-designs consists in the determination of the existence spectrum, that is the determination of the values v for which the block design exists. Open problems related to the existence spectrum do survive, as it is known, even for incidence structures that were studied long before block designs, say, for instance, finite projective planes. In the case of interest for this thesis, the request is to establish, for a given graph H, the existence spectrum for H-designs, that is the set of all values v for which an H-deecomposition of the complete graph on v vertices exists. A contribution to the determination of the spectrum is obtained in case H is a connected graph with 7 vertices and 7 edges containing a cycle of length 3. This case remains open from previous investigations in which the graph H is smaller or contains a longer cycle. Generalizations in various directions are also approached, assuming a slight change in the type of the graph H or assuming special incidence features for the decomposition, such as those that generally involve some kind of balance, typically the request that a certain parameter of the decomposition remain uniform consideration. In our specific context the decomposition is balanced if the number of blocks containing any given vertex is constant.
Finite incidence structures in which blocks have a given shape
28-feb-2020
BONISOLI, Arrigo
File in questo prodotto:
File Dimensione Formato  
Tesi_Dottorato_Fernicola.pdf

Open Access dal 30/08/2021

Descrizione: tesi di dottorato
Dimensione 1.13 MB
Formato Adobe PDF
1.13 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1200565
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact