{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/125609"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/125609","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Problems in graph reconstruction and set pair systems","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","abstract_has_math":false,"creators":["Nahvi, Mina"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Kostochka, Alexandr","West, Douglas","White, Ethan","Milenkovic, Olgica"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-07-11","date_published":"2024-07-11","updated_at":"2026-07-22T22:25:02Z","subjects":["Graph Reconstruction","Set Pair Systems"],"languages":["en","eng"],"rights":["Copyright 2024 Mina Nahvi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/125609","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr","West, Douglas","White, Ethan","Milenkovic, Olgica"]},{"key":"dc:creator","label":"Author","values":["Nahvi, Mina"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-07-11","2024-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Reconstruction","Set Pair Systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Mina Nahvi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/125609"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","The student, Mina Nahvi, accepted the attached license on 2024-07-10 at 15:24.","The student, Mina Nahvi, submitted this Dissertation for approval on 2024-07-10 at 15:30.","This Dissertation was approved for publication on 2024-07-11 at 13:46.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21049 on 2025-02-04 at 21:04:55","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}$."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Problems in graph reconstruction and set pair systems"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr","West, Douglas","White, Ethan","Milenkovic, Olgica"],"dc:creator":["Nahvi, Mina"],"dc:date":["2024-07-11","2024-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","The student, Mina Nahvi, accepted the attached license on 2024-07-10 at 15:24.","The student, Mina Nahvi, submitted this Dissertation for approval on 2024-07-10 at 15:30.","This Dissertation was approved for publication on 2024-07-11 at 13:46.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21049 on 2025-02-04 at 21:04:55","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}$."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/125609"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Mina Nahvi"],"dc:subject":["Graph Reconstruction","Set Pair Systems"],"dc:title":["Problems in graph reconstruction and set pair systems"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}