Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs

Download (2.31 MB)
posted on 28.11.2018 by Alexander M Cameron
Let a 2 to 1 directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such directed hypergraph F let the nth extremal number of F be the maximum number of edges that any directed hypergraph on n vertices can have without containing a copy of F. In 2007, Langlois, Mubayi, Sloan, and Turan determined the exact extremal number for a particular directed hypergraph and found the extremal number up to asymptotic equivalence for a second directed hypergraph. Each of these forbidden graphs had exactly two edges. In the first part of this thesis, we determine the exact extremal numbers for every 2 to 1 directed hypergraph that has exactly two edges. For fixed integers p and q, let f(n,p,q) denote the minimum number of colors needed to color all of the edges of the complete graph on n vertices such that no clique of p vertices spans fewer than q distinct colors. Any edge-coloring with this property is known as a (p,q)-coloring. In the second part of this thesis, we construct a (5,5)-coloring and a (5,6)-coloring with few colors, improving on the best known upper bounds for f(n,5,5) and f(n,5,6).



Turán, GyörgyMubayi, Dhruv


Turán, György


Mathematics, Statistics and Computer Science

Degree Grantor

University of Illinois at Chicago

Degree Level


Committee Member

Friedland, Shmuel Reyzin, Lev Sloan, Robert

Submitted date

August 2018

Issue date