 Main
Extremal Graphs and Additive Combinatorics /
Abstract
In this thesis we investigate graphs that are constructed using objects from additive number theory. Sidon sets are used to construct C₄free graphs that show ex( q²  q  2 , C₄) >̲ 1/2q³  q²  O(q³/⁴) whenever q is an odd prime power. This disproves a conjecture of Abreu, Balbuena, and Labbate and improves the current lower bound by q/2. Sidon sets are also used to show that there are bipartite graphs F for which the following holds: for infinitely many n there is an nvertex graph with [Omega] (ex(n , F) edges and has the property that every edge lies in exactly one copy of F. This disproves a conjecture of Solymosi concerning a possible extension of the removal lemma to sparse graphs. An ordered Turán problem for bipartite graphs is introduced and studied. We prove upper bounds on this problem and use B_ksets to obtain lower bounds. Generalizations of Sidon sets, such as kfold Sidon sets and B_k*sets, are studied. We prove that for any integer k >̲ 3, if A \subset \{1,2...., N} is a B_k*set, then IAI <̲ (1/4 + o_k (1)) N1/k. This improves the previously best known upper bound by a factor of 1/4. For odd k >̲ 3, we construct B_ksets that have more elements than the Bose Chowla B_ksets. A consequence is that there are B₃sets in {1,2...., N} that are asymptotically larger than any B₃ set contained in {1,2...., N}. For any integer k >̲ 3, we prove that if A \subset {1,2...., N} is a kfold Sidon set, then IAI <̲ ( N /k )¹/² + O( (N/k)¹/⁴). This improves the current upper bound by a factor of (1 / k)¹/²
Main Content
Enter the password to open this PDF file:













