{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:5453"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:5453","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Packings and coverings with Hamilton cycles and on-line Ramsey theory","abstract":"A major theme in modern graph theory is the exploration of maximal packings and minimal covers of graphs with subgraphs in some given family. We focus on packings and coverings with Hamilton cycles, and prove the following results in the area. • Let ε > 0, and let \\(G\\) be a large graph on n vertices with minimum degree at least (1=2+ ε)n. We give a tight lower bound on the size of a maximal packing of \\(G\\) with edge-disjoint Hamilton cycles. • Let \\(T\\) be a strongly k-connected tournament. We give an almost tight lower bound on the size of a maximal packing of \\(T\\) with edge-disjoint Hamilton cycles. • Let log \\(^1\\)\\(^1\\)\\(^7\\) \\(n\\)/\\(n\\)≤\\(p\\)≤1-\\(n\\)\\(^-\\)\\(^1\\)\\(^/\\)\\(^8\\). We prove that \\(G\\)\\(_n\\)\\(_,\\)\\(_p\\) may a.a.s be covered by a set of ⌈Δ(\\(G\\)\\(_n\\)\\(_,\\)\\(_p\\))/2⌉ Hamilton cycles, which is clearly best possible. In addition, we consider some problems in on-line Ramsey theory. Let r(\\(G\\),\\(H\\)) denote the on-line Ramsey number of \\(G\\) and \\(H\\). We conjecture the exact values of r (\\(P\\)\\(_k\\),\\(P\\)\\(_ℓ\\)) for all \\(k\\)≤ℓ. We prove this conjecture for \\(k\\)=2, prove it to within an additive error of 10 for \\(k\\)=3, and prove an asymptotically tight lower bound for \\(k\\)=4. We also determine r(\\(P\\)\\(_3\\),\\(C\\)\\(_ℓ\\) exactly for all ℓ.","abstract_html":"A major theme in modern graph theory is the exploration of maximal packings and minimal covers of graphs with subgraphs in some given family. We focus on packings and coverings with Hamilton cycles, and prove the following results in the area. • Let ε &gt; 0, and let \\(G\\) be a large graph on n vertices with minimum degree at least (1=2+ ε)n. We give a tight lower bound on the size of a maximal packing of \\(G\\) with edge-disjoint Hamilton cycles. • Let \\(T\\) be a strongly k-connected tournament. We give an almost tight lower bound on the size of a maximal packing of \\(T\\) with edge-disjoint Hamilton cycles. • Let log <span class=\"etd-inline-math\"><sup>1</sup></span><span class=\"etd-inline-math\"><sup>1</sup></span><span class=\"etd-inline-math\"><sup>7</sup></span> \\(n\\)/\\(n\\)≤\\(p\\)≤1-\\(n\\)<span class=\"etd-inline-math\"><sup>-</sup></span><span class=\"etd-inline-math\"><sup>1</sup></span><span class=\"etd-inline-math\"><sup>/</sup></span><span class=\"etd-inline-math\"><sup>8</sup></span>. We prove that \\(G\\)<span class=\"etd-inline-math\"><sub>n</sub></span><span class=\"etd-inline-math\"><sub>,</sub></span><span class=\"etd-inline-math\"><sub>p</sub></span> may a.a.s be covered by a set of ⌈Δ(\\(G\\)<span class=\"etd-inline-math\"><sub>n</sub></span><span class=\"etd-inline-math\"><sub>,</sub></span><span class=\"etd-inline-math\"><sub>p</sub></span>)/2⌉ Hamilton cycles, which is clearly best possible. In addition, we consider some problems in on-line Ramsey theory. Let r(\\(G\\),\\(H\\)) denote the on-line Ramsey number of \\(G\\) and \\(H\\). We conjecture the exact values of r (\\(P\\)<span class=\"etd-inline-math\"><sub>k</sub></span>,\\(P\\)<span class=\"etd-inline-math\"><sub>ℓ</sub></span>) for all \\(k\\)≤ℓ. We prove this conjecture for \\(k\\)=2, prove it to within an additive error of 10 for \\(k\\)=3, and prove an asymptotically tight lower bound for \\(k\\)=4. We also determine r(\\(P\\)<span class=\"etd-inline-math\"><sub>3</sub></span>,\\(C\\)<span class=\"etd-inline-math\"><sub>ℓ</sub></span> exactly for all ℓ.","abstract_has_math":true,"creators":["Lapinskas, John Adam"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12","date_published":"2014-12","updated_at":"2026-11-19T09:28:23Z","subjects":["QA Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"http://etheses.bham.ac.uk//id/eprint/5453/1/Lapinskas14PhD.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://etheses.bham.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Aetheses.bham.ac.uk%3A5453","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["na"]},{"key":"dc:creator","label":"Author","values":["Lapinskas, John Adam"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12"]},{"key":"dc:date.issued","label":"Date","values":["2014-12"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["College of Engineering & Physical Sciences","School of Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/5453/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.dcterms_iso639_2","label":"Language (ISO 639-2)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/5453/1/Lapinskas14PhD.pdf","http://etheses.bham.ac.uk//id/eprint/5453/2/Decl_IS_Lapinskas14PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["A major theme in modern graph theory is the exploration of maximal packings and minimal covers of graphs with subgraphs in some given family. We focus on packings and coverings with Hamilton cycles, and prove the following results in the area. • Let ε > 0, and let \\(G\\) be a large graph on n vertices with minimum degree at least (1=2+ ε)n. We give a tight lower bound on the size of a maximal packing of \\(G\\) with edge-disjoint Hamilton cycles. • Let \\(T\\) be a strongly k-connected tournament. We give an almost tight lower bound on the size of a maximal packing of \\(T\\) with edge-disjoint Hamilton cycles. • Let log \\(^1\\)\\(^1\\)\\(^7\\) \\(n\\)/\\(n\\)≤\\(p\\)≤1-\\(n\\)\\(^-\\)\\(^1\\)\\(^/\\)\\(^8\\). We prove that \\(G\\)\\(_n\\)\\(_,\\)\\(_p\\) may a.a.s be covered by a set of ⌈Δ(\\(G\\)\\(_n\\)\\(_,\\)\\(_p\\))/2⌉ Hamilton cycles, which is clearly best possible. In addition, we consider some problems in on-line Ramsey theory. Let r(\\(G\\),\\(H\\)) denote the on-line Ramsey number of \\(G\\) and \\(H\\). We conjecture the exact values of r (\\(P\\)\\(_k\\),\\(P\\)\\(_ℓ\\)) for all \\(k\\)≤ℓ. We prove this conjecture for \\(k\\)=2, prove it to within an additive error of 10 for \\(k\\)=3, and prove an asymptotically tight lower bound for \\(k\\)=4. We also determine r(\\(P\\)\\(_3\\),\\(C\\)\\(_ℓ\\) exactly for all ℓ."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public","staffonly"]},{"key":"dc:title","label":"Title","values":["Packings and coverings with Hamilton cycles and on-line Ramsey theory"]}]}],"canonical_facts":{"dc:contributor.sponsor":["na"],"dc:creator":["Lapinskas, John Adam"],"dc:date":["2014-12"],"dc:date.issued":["2014-12"],"dc:description.abstract":["A major theme in modern graph theory is the exploration of maximal packings and minimal covers of graphs with subgraphs in some given family. We focus on packings and coverings with Hamilton cycles, and prove the following results in the area. • Let ε > 0, and let \\(G\\) be a large graph on n vertices with minimum degree at least (1=2+ ε)n. We give a tight lower bound on the size of a maximal packing of \\(G\\) with edge-disjoint Hamilton cycles. • Let \\(T\\) be a strongly k-connected tournament. We give an almost tight lower bound on the size of a maximal packing of \\(T\\) with edge-disjoint Hamilton cycles. • Let log \\(^1\\)\\(^1\\)\\(^7\\) \\(n\\)/\\(n\\)≤\\(p\\)≤1-\\(n\\)\\(^-\\)\\(^1\\)\\(^/\\)\\(^8\\). We prove that \\(G\\)\\(_n\\)\\(_,\\)\\(_p\\) may a.a.s be covered by a set of ⌈Δ(\\(G\\)\\(_n\\)\\(_,\\)\\(_p\\))/2⌉ Hamilton cycles, which is clearly best possible. In addition, we consider some problems in on-line Ramsey theory. Let r(\\(G\\),\\(H\\)) denote the on-line Ramsey number of \\(G\\) and \\(H\\). We conjecture the exact values of r (\\(P\\)\\(_k\\),\\(P\\)\\(_ℓ\\)) for all \\(k\\)≤ℓ. We prove this conjecture for \\(k\\)=2, prove it to within an additive error of 10 for \\(k\\)=3, and prove an asymptotically tight lower bound for \\(k\\)=4. We also determine r(\\(P\\)\\(_3\\),\\(C\\)\\(_ℓ\\) exactly for all ℓ."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/5453/1/Lapinskas14PhD.pdf","http://etheses.bham.ac.uk//id/eprint/5453/2/Decl_IS_Lapinskas14PhD.pdf"],"dc:language.dcterms_iso639_2":["eng"],"dc:publisher.department":["College of Engineering & Physical Sciences","School of Mathematics"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/5453/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public","staffonly"],"dc:title":["Packings and coverings with Hamilton cycles and on-line Ramsey theory"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:28:23Z"}