Abstract
In this thesis we investigate graphs that are constructed using objects from additive number theory. Sidon sets are used to construct C 4-free graphs that show ex(q2 -- q -- 2, C4) ≥ ½ q3 -- q2 -- 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 $\frac{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 O(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 Turan problem for bipartite graphs is introduced and studied. We prove upper bounds on this problem and use Bk-sets to obtain lower bounds.
Generalizations of Sidon sets, such as k-fold Sidon sets and Bk*-sets, are studied. We prove that for any integer k ≥ 3, if A ⊂ {1, 2, ...\subset \{1,2,..., N}$ is a Bk *-set, then |A| ≤ (¼ + 0 k (1)) N1/k. This improves the previously best known upper bound by a factor of ¼. For odd k ≥ 3, we construct Bk*-sets that have more elements than the Bose-Chowla Bk-sets. A consequence is that there are B3*-sets in {1, 2, ..., N} that are asymptotically larger than any B3-set contained in {1,2, ... , N}. For any integer k ≥ 3, we prove that if A ⊂ {1, 2, ... , N} is a k-fold Sidon set, then |A| ≤ (N /k)½ + O((N/k)¼ ). This improves the current upper bound by a factor of (1/k)½ .