UC San Diego

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 n-vertex 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_k-sets to obtain lower bounds. Generalizations of Sidon sets, such as k-fold 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_k-sets that have more elements than the Bose- Chowla B_k-sets. 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 k-fold Sidon set, then IAI <̲ ( N /k )¹/² + O( (N/k)¹/⁴). This improves the current upper bound by a factor of (1 / k)¹/²