Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

Extremal Graphs and Additive Combinatorics /

  • Author(s): Timmons, Craig Michael
  • et al.
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 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)¹/²

Main Content
Current View