Problems in graph reconstruction and set pair systems

Nahvi, Mina

Permalink

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

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