## Files in this item

FilesDescriptionFormat

application/pdf

Ping_Hu.pdf (911kB)
(no description provided)PDF

## Description

 Title: Extremal graph theory: flag algebras, Ramsey-Turan 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 Urbana-Champaign 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 C4-free hypercubes and C6-free hypercubes. The n-dimensional 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_2-free 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 Erdos--Sos defined 'Ramsey-Turan' function RT(n,H,f(n) to be the maximum number of edges of an H-free 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 3-uniform 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 3-uniform 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 r-uniform hypergraphs F is the infimum of all non-negative reals c such that the subfamily of F comprising hypergraphs H with minimum degree at least $c\binom{|V(H)|}{r-1}$ 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 r-uniform hypergraphs for r>=3. With Balogh, Butterfield, Lenz and Mubayi, we proved an upper bound on the family of F5-free 3-uniform hypergraphs. We also gave constructions to show lower bounds on more families of 3-uniform hypergraphs. Issue Date: 2014-09-16 URI: http://hdl.handle.net/2142/50590 Rights Information: Copyright 2014 Ping Hu Date Available in IDEALS: 2014-09-16 Date Deposited: 2014-08
﻿