Problems in graph reconstruction and set pair systems

This thesis focuses on how large (or small) certain mathematical structures can be if we impose specific conditions onto them. More specifically, we study the concept of reconstructing things (like graphs and strings) from their smaller parts, as well as a system of sets whose pairwise intersections have specific sizes. In Chapter 1, we introduce all the problems we study in this thesis and provide the necessary definitions and background. In Chapter 2, we consider reconstruction of graphs and recognizing their various properties. The {\it $n-\ell$-deck} of a graph is the multiset of its subgraphs induced by $n-\ell$ vertices. A graph property is {\it $l$-recognizable} if it is determined by the deck of subgraphs obtained by deleting $l$ vertices. We show that the degree list of an $n$-vertex graph is $3$-recognizable when $n\ge7$, and the threshold on $n$ is sharp. Using this result, we also show that when $n\ge7$ the $(n-3)$-deck also determines whether an $n$-vertex graph is connected; this is also sharp. In Chapter 3, we focus on reconstructing trees. An $n$-vertex graph is {\it $\ell$-reconstructible} if it is determined by its $(n-\ell)$-deck, meaning that no other graph has the same deck. We prove that every tree with at least $6\ell+11$ vertices is $\ell$-reconstructible. In Chapter 4, we shift our focus to reconstructing strings from their $k$-subsequences, which are subsequences of length $k$. We also introduce a new problem called gapped reconstruction: we seek the smallest positive integer $G(k)$ such that there exist at least two distinct strings of length $G(k)$ that cannot be distinguished based on a set of ``gapped'' subsequences of length at most $k$. The gap constraint requires the elements in the subsequences to be non-adjacent within the original string. We construct sequences sharing the same gapped $k$-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure, establishing the first known constructive upper bound on $G(k)$. In Chapter 5, we study systems of sets. A set pair system \{(A_i,B_i)\}_i=1^m is {\em $1$-cross intersecting} if |A_i\cap B_j| is $1$ when $i\neq j$ and $0$ if $i=j$. Let $m(a,b,1)$ be the maximum size of a $1$-cross intersecting set pair system in which |A_i|\leq a and |B_i|\leq b for all $i$. Holzman proved that if $a,b\geq 2$, then $m(a,b,1)\leq \frac{29}{30}\binom{a+b}{a}$. We prove a conjecture by Holzman which claims that the factor $\frac{29}{30}$ can be replaced by $\frac{5}{6}$.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Nahvi, Mina

Contributors dc:contributor

• Kostochka, Alexandr
• West, Douglas
• White, Ethan
• Milenkovic, Olgica

• Graph Reconstruction
• Set Pair Systems

Statement dc:rights

• Copyright 2024 Mina Nahvi

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F125609