University of Illinois Urbana-Champaign

On some problems in reconstruction

Spinoza, Hannah R

Content Files
SPINOZA-DISSERTATION-2016.pdf

Permalink

https://hdl.handle.net/2142/95378

Description

Title
On some problems in reconstruction
Author(s)
Spinoza, Hannah R
Issue Date
2016-12-01
Director of Research (if dissertation) or Advisor (if thesis)
West, Douglas
Doctoral Committee Chair(s)
Kostochka, Alexandr
Committee Member(s)
  • Schenck, Hal
  • Molla, Theo
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2017-03-01T15:49:22Z
Keyword(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 $(n-3)$-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 degree-associated reconstruction. An $(n-1)$-vertex induced subgraph accompanied with the degree of the missing vertex is called a {\it dacard}. The {\it degree-associated 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 degree-associated 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$.
Graduation Semester
2016-12
Type of Resource
text
Permalink
http://hdl.handle.net/2142/95378
Copyright and License Information
Copyright 2016 Hannah Spinoza

Owning Collections

Dissertations and Theses - Mathematics
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois