Files in this item
Files  Description  Format 

application/pdf SPINOZADISSERTATION2016.pdf (712kB)  (no description provided) 
Description
Title:  On some problems in reconstruction 
Author(s):  Spinoza, Hannah R 
Director of Research:  West, Douglas 
Doctoral Committee Chair(s):  Kostochka, Alexandr 
Doctoral Committee Member(s):  Schenck, Hal; Molla, Theo 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Graph theory
Reconstruction 
Abstract:  A graph is {\it reconstructible} if it is determined by its {\it deck} of unlabeled subgraphs obtained by deleting one vertex; a {\it card} is one of these subgraphs. The {\it Reconstruction Conjecture} asserts that all graphs with at least three vertices are reconstructible. In Chapter $2$ we consider $k$deck reconstruction of graphs. The {\it $k$deck} of a graph is its multiset of $k$vertex induced subgraphs. We prove a generalization of a result by Bollob\'as concerning the $k$deck reconstruction of almost all graphs, showing that when $\ell \le (1\epsilon)\frac{n}{2}$, the probability than an $n$vertex graph is reconstructible from some $\binom{\ell+1}{2}$ of the graphs in the $(n\ell)$deck tends to $1$ as $n$ tends to $\infty$. We determine the smallest $k$ such that all graphs with maximum degree $2$ are $k$deck reconstructible. We prove for $n\ge 26$ that whether a graph is connected is determined by its $(n3)$deck. We prove that if $G$ is a complete $r$partite graphs, then $G$ is $(r+1)$deck reconstructible (the same holds for $\overline{G}$). In Chapter $3$ we consider degreeassociated reconstruction. An $(n1)$vertex induced subgraph accompanied with the degree of the missing vertex is called a {\it dacard}. The {\it degreeassociated reconstruction number} of a graph $G$ is the fewest number of dacards needed to determine $G$. We provide a tool for reconstructing some graphs from two dacards. We prove that certain families of trees and disconnected graphs can be reconstructed from two dacards. We also determine the degreeassociated reconstruction number for complete multipartite graphs and their complements. For such graphs, we also determine the least $s$ such that {\it every} set of $s$ dacards determine the graph. In Chapter $4$ we consider the reconstruction of matrices from principal submatrices. A $(n\ell)$by$(n\ell)$ principal submatrix is a submatrix formed by deleting $\ell$ rows and columns symmetrically. The {\it matrix reconstruction threshold} $mrt(\ell)$ is the minimum integer $n_0$ such that for $n\ge n_0$ all $n$by$n$ matrices are reconstructible from their deck of $(n\ell)$by$(n\ell)$ principal submatrices. We prove $mrt(\ell) \leq \frac{2}{\ln 2}\ell^2+3\ell$. 
Issue Date:  20161201 
Type:  Text 
URI:  http://hdl.handle.net/2142/95378 
Rights Information:  Copyright 2016 Hannah Spinoza 
Date Available in IDEALS:  20170301 
Date Deposited:  201612 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois