Files in this item
Files  Description  Format 

application/pdf Ping_Hu.pdf (911kB)  (no description provided) 
Description
Title:  Extremal graph theory: flag algebras, RamseyTuran numbers, chromatic thresholds, and sparse hypergraphs 
Author(s):  Hu, Ping 
Director of Research:  Balogh, József 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  Balogh, József; Yong, Alexander; Lidicky, Bernard 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Flag Algebras
Ramsey Turan Chromatic Thresholds 
Abstract:  We study problems in extremal combinatorics motivated by Turan's Theorem and Ramsey Theory. In Chapter 2, we use Flag Algebras to study these problems. With Balogh, Lidicky, Pikhurko, Udvari and Volec, we gave the exact structures of permutations of [n] = {1,...,n} which maximize the number of monotone subsequences of length 4. With Balogh, Lidicky and Liu, we gave upper bounds on the number of edges of C4free hypercubes and C6free hypercubes. The ndimensional Boolean lattice B_n denotes the partial ordered set whose elements are all subsets of [n] ordered by inclusion. A layer of B_n is a family of sets of the same size. We also gave upper bounds on the sizes of B_2free subposets of three layers of B_n. In Chapter 3, we study a variation of both Turan type problems and Ramsey type problems. Let H be a graph and f(n) be a function. Sos and ErdosSos defined 'RamseyTuran' function RT(n,H,f(n) to be the maximum number of edges of an Hfree graph on n vertices with independence number less than f(n). With Balogh and Simonovits, we answered a question from Erdos and Sos by proving that RT(n,K_5,o(\sqrt{n log n}))=o(n^2). We also extended this result to several other K_ls and functions f(n). In Chapter 4, we study a sparse version of Turan type problems.The maximum 3uniform hypergraphs that do not contain a copy of F5={abc, ade, bde}, sometimes called the generalized triangle, is tripartite. With Balogh, Butterfield and Lenz, we extended this result to the sparse random setting, proving that with probability tending to 1 the largest subgraph of the random 3uniform hypergraph that does not contain F5 is tripartite. In Chapter 5, we study chromatic threshold, which was motivated by a variation of Turan type problems and introduced by Erdos and Simonovits. The chromatic threshold of a family of runiform hypergraphs F is the infimum of all nonnegative reals c such that the subfamily of F comprising hypergraphs H with minimum degree at least $c\binom{V(H)}{r1}$ has bounded chromatic number. The problem of chromatic thresholds of graphs has been well studied, but there have been no previous results about the chromatic thresholds of runiform hypergraphs for r>=3. With Balogh, Butterfield, Lenz and Mubayi, we proved an upper bound on the family of F5free 3uniform hypergraphs. We also gave constructions to show lower bounds on more families of 3uniform hypergraphs. 
Issue Date:  20140916 
URI:  http://hdl.handle.net/2142/50590 
Rights Information:  Copyright 2014 Ping Hu 
Date Available in IDEALS:  20140916 
Date Deposited:  201408 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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