Files in this item
Files  Description  Format 

application/pdf 1_Ozkahya_Lale.pdf (484kB)  (no description provided) 
Description
Title:  Problems in extremal graph theory 
Author(s):  Ozkahya, Lale 
Director of Research:  Furedi, Zoltan 
Doctoral Committee Chair(s):  West, Douglas B. 
Doctoral Committee Member(s):  Furedi, Zoltan; Kostochka, Alexandr V.; Vijay, Sujith 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  squares of graphs
Turan problem hypercube hypergraph cluster 
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$minorfree 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 socalled 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. 
Issue Date:  20100820 
URI:  http://hdl.handle.net/2142/16851 
Rights Information:  Copyright 2010 Lale Ozkahya 
Date Available in IDEALS:  20100820 
Date Deposited:  201008 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics