Withdraw
Loading…
Problems in graph reconstruction and set pair systems
Nahvi, Mina
Loading…
Permalink
https://hdl.handle.net/2142/125609
Description
- Title
- Problems in graph reconstruction and set pair systems
- Author(s)
- Nahvi, Mina
- Issue Date
- 2024-07-11
- Director of Research (if dissertation) or Advisor (if thesis)
- Kostochka, Alexandr
- Doctoral Committee Chair(s)
- West, Douglas
- Committee Member(s)
- White, Ethan
- Milenkovic, Olgica
- 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 reconstruction, set pair systems
- Abstract
- 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}$.
- Graduation Semester
- 2024-08
- Type of Resource
- Thesis
- Handle URL
- https://hdl.handle.net/2142/125609
- Copyright and License Information
- Copyright 2024 Mina Nahvi
Owning Collections
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at IllinoisManage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…