On some problems in reconstruction

Spinoza, Hannah R

Permalink

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

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

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