{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/16851"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/16851","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Problems in extremal graph theory","abstract":"We consider a variety of problems in extremal graph and set theory. The {\\em chromatic number} of $G$, $\\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable. The {\\it square} of $G$, written $G^2$, is the supergraph of $G$ in which also vertices within distance 2 of each other in $G$ are adjacent. A graph $H$ is a {\\it minor} of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. We show that the upper bound for $\\chi(G^2)$ conjectured by Wegner (1977) for planar graphs holds when $G$ is a $K_4$-minor-free graph. We also show that $\\chi(G^2)$ is equal to the bound only when $G^2$ contains a complete graph of that order. One of the central problems of extremal hypergraph theory is finding the maximum number of edges in a hypergraph that does not contain a specific forbidden structure. We consider as a forbidden structure a fixed number of members that have empty common intersection as well as small union. We obtain a sharp upper bound on the size of uniform hypergraphs that do not contain this structure, when the number of vertices is sufficiently large. Our result is strong enough to imply the same sharp upper bound for several other interesting forbidden structures such as the so-called strong simplices and clusters. The {\\em $n$-dimensional hypercube}, $Q_n$, is the graph whose vertex set is $\\{0,1\\}^n$ and whose edge set consists of the vertex pairs differing in exactly one coordinate. The generalized Tur\\'an problem asks for the maximum number of edges in a subgraph of a graph $G$ that does not contain a forbidden subgraph $H$. We consider the Tur\\'an problem where $G$ is $Q_n$ and $H$ is a cycle of length $4k+2$ with $k\\geq 3$. Confirming a conjecture of Erd{\\H o}s (1984), we show that the ratio of the size of such a subgraph of $Q_n$ over the number of edges of $Q_n$ is $o(1)$, i.e. in the limit this ratio approaches 0 as $n$ approaches infinity.","abstract_html":"We consider a variety of problems in extremal graph and set theory. The {\\em chromatic number} of $G$, $\\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable. The {\\it square} of $G$, written <span class=\"etd-inline-math\">G<sup>2</sup></span>, is the supergraph of $G$ in which also vertices within distance 2 of each other in $G$ are adjacent. A graph $H$ is a {\\it minor} of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. We show that the upper bound for <span class=\"etd-inline-math\">\\chi(G<sup>2</sup>)</span> conjectured by Wegner (1977) for planar graphs holds when $G$ is a <span class=\"etd-inline-math\">K<sub>4</sub></span>-minor-free graph. We also show that <span class=\"etd-inline-math\">\\chi(G<sup>2</sup>)</span> is equal to the bound only when <span class=\"etd-inline-math\">G<sup>2</sup></span> contains a complete graph of that order. One of the central problems of extremal hypergraph theory is finding the maximum number of edges in a hypergraph that does not contain a specific forbidden structure. We consider as a forbidden structure a fixed number of members that have empty common intersection as well as small union. We obtain a sharp upper bound on the size of uniform hypergraphs that do not contain this structure, when the number of vertices is sufficiently large. Our result is strong enough to imply the same sharp upper bound for several other interesting forbidden structures such as the so-called strong simplices and clusters. The {\\em $n$-dimensional hypercube}, <span class=\"etd-inline-math\">Q<sub>n</sub></span>, is the graph whose vertex set is <span class=\"etd-inline-math\">\\{0,1\\}<sup>n</sup></span> and whose edge set consists of the vertex pairs differing in exactly one coordinate. The generalized Tur\\&#x27;an problem asks for the maximum number of edges in a subgraph of a graph $G$ that does not contain a forbidden subgraph $H$. We consider the Tur\\&#x27;an problem where $G$ is <span class=\"etd-inline-math\">Q<sub>n</sub></span> and $H$ is a cycle of length $4k+2$ with $k\\geq 3$. Confirming a conjecture of Erd{\\H o}s (1984), we show that the ratio of the size of such a subgraph of <span class=\"etd-inline-math\">Q<sub>n</sub></span> over the number of edges of <span class=\"etd-inline-math\">Q<sub>n</sub></span> is $o(1)$, i.e. in the limit this ratio approaches 0 as $n$ approaches infinity.","abstract_has_math":true,"creators":["Ozkahya, Lale"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Furedi, Zoltan","West, Douglas B.","Kostochka, Alexandr V.","Vijay, Sujith"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-08-20T17:59:49Z","date_published":"2010-08-20T17:59:49Z","updated_at":"2026-07-22T22:25:09Z","subjects":["squares of graphs","Turan problem","hypercube","hypergraph","cluster"],"languages":["en"],"rights":["Copyright 2010 Lale Ozkahya"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/16851","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Furedi, Zoltan","West, Douglas B.","Kostochka, Alexandr V.","Vijay, Sujith"]},{"key":"dc:creator","label":"Author","values":["Ozkahya, Lale"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-08-20T17:59:49Z","2010-08"]},{"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":["squares of graphs","Turan problem","hypercube","hypergraph","cluster"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Lale Ozkahya"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/16851"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We consider a variety of problems in extremal graph and set theory. The {\\em chromatic number} of $G$, $\\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable. The {\\it square} of $G$, written $G^2$, is the supergraph of $G$ in which also vertices within distance 2 of each other in $G$ are adjacent. A graph $H$ is a {\\it minor} of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. We show that the upper bound for $\\chi(G^2)$ conjectured by Wegner (1977) for planar graphs holds when $G$ is a $K_4$-minor-free graph. We also show that $\\chi(G^2)$ is equal to the bound only when $G^2$ contains a complete graph of that order. One of the central problems of extremal hypergraph theory is finding the maximum number of edges in a hypergraph that does not contain a specific forbidden structure. We consider as a forbidden structure a fixed number of members that have empty common intersection as well as small union. We obtain a sharp upper bound on the size of uniform hypergraphs that do not contain this structure, when the number of vertices is sufficiently large. Our result is strong enough to imply the same sharp upper bound for several other interesting forbidden structures such as the so-called strong simplices and clusters. The {\\em $n$-dimensional hypercube}, $Q_n$, is the graph whose vertex set is $\\{0,1\\}^n$ and whose edge set consists of the vertex pairs differing in exactly one coordinate. The generalized Tur\\'an problem asks for the maximum number of edges in a subgraph of a graph $G$ that does not contain a forbidden subgraph $H$. We consider the Tur\\'an problem where $G$ is $Q_n$ and $H$ is a cycle of length $4k+2$ with $k\\geq 3$. Confirming a conjecture of Erd{\\H o}s (1984), we show that the ratio of the size of such a subgraph of $Q_n$ over the number of edges of $Q_n$ is $o(1)$, i.e. in the limit this ratio approaches 0 as $n$ approaches infinity.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-06-11T17:50:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Ozkahya_Lale.pdf: 484613 bytes, checksum: 19073e8c4bca5cc20a0fc3eaf85e02ea (MD5)","Made available in DSpace on 2010-08-20T17:59:49Z (GMT). No. of bitstreams: 3 Ozkahya_Lale.pdf: 484613 bytes, checksum: 19073e8c4bca5cc20a0fc3eaf85e02ea (MD5) 1_Ozkahya_Lale.pdf: 483788 bytes, checksum: 75d90e39c5fa1d788d63d2deaa283f7e (MD5) license.txt: 4061 bytes, checksum: 7c1a50473ea99a202fadd7e898c9ff0f (MD5)"]},{"key":"dc:title","label":"Title","values":["Problems in extremal graph theory"]}]}],"canonical_facts":{"dc:contributor":["Furedi, Zoltan","West, Douglas B.","Kostochka, Alexandr V.","Vijay, Sujith"],"dc:creator":["Ozkahya, Lale"],"dc:date":["2010-08-20T17:59:49Z","2010-08"],"dc:description":["We consider a variety of problems in extremal graph and set theory. The {\\em chromatic number} of $G$, $\\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable. The {\\it square} of $G$, written $G^2$, is the supergraph of $G$ in which also vertices within distance 2 of each other in $G$ are adjacent. A graph $H$ is a {\\it minor} of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. We show that the upper bound for $\\chi(G^2)$ conjectured by Wegner (1977) for planar graphs holds when $G$ is a $K_4$-minor-free graph. We also show that $\\chi(G^2)$ is equal to the bound only when $G^2$ contains a complete graph of that order. One of the central problems of extremal hypergraph theory is finding the maximum number of edges in a hypergraph that does not contain a specific forbidden structure. We consider as a forbidden structure a fixed number of members that have empty common intersection as well as small union. We obtain a sharp upper bound on the size of uniform hypergraphs that do not contain this structure, when the number of vertices is sufficiently large. Our result is strong enough to imply the same sharp upper bound for several other interesting forbidden structures such as the so-called strong simplices and clusters. The {\\em $n$-dimensional hypercube}, $Q_n$, is the graph whose vertex set is $\\{0,1\\}^n$ and whose edge set consists of the vertex pairs differing in exactly one coordinate. The generalized Tur\\'an problem asks for the maximum number of edges in a subgraph of a graph $G$ that does not contain a forbidden subgraph $H$. We consider the Tur\\'an problem where $G$ is $Q_n$ and $H$ is a cycle of length $4k+2$ with $k\\geq 3$. Confirming a conjecture of Erd{\\H o}s (1984), we show that the ratio of the size of such a subgraph of $Q_n$ over the number of edges of $Q_n$ is $o(1)$, i.e. in the limit this ratio approaches 0 as $n$ approaches infinity.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-06-11T17:50:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Ozkahya_Lale.pdf: 484613 bytes, checksum: 19073e8c4bca5cc20a0fc3eaf85e02ea (MD5)","Made available in DSpace on 2010-08-20T17:59:49Z (GMT). No. of bitstreams: 3 Ozkahya_Lale.pdf: 484613 bytes, checksum: 19073e8c4bca5cc20a0fc3eaf85e02ea (MD5) 1_Ozkahya_Lale.pdf: 483788 bytes, checksum: 75d90e39c5fa1d788d63d2deaa283f7e (MD5) license.txt: 4061 bytes, checksum: 7c1a50473ea99a202fadd7e898c9ff0f (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/16851"],"dc:language":["en"],"dc:rights":["Copyright 2010 Lale Ozkahya"],"dc:subject":["squares of graphs","Turan problem","hypercube","hypergraph","cluster"],"dc:title":["Problems in extremal graph theory"],"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:09Z"}