Georgia Institute of Technology College of Sciences

A set~$A$ of integers is a \textit{Sidon set} if all thesums~$a_1+a_2$, with~$a_1\leq a_2$ and~$a_1$,~$a_2\in A$, aredistinct. In the 1940s, Chowla, Erd\H{o}s and Tur\'an determinedasymptotically the maximum possible size of a Sidon set contained in$[n]=\{0,1,\dots,n-1\}$. We study Sidon sets contained in sparserandom sets of integers, replacing the `dense environment'~$[n]$ by asparse, random subset~$R$ of~$[n]$.Let~$R=[n]_m$ be a uniformly chosen, random $m$-element subsetof~$[n]$. Let~$F([n]_m)=\max\{|S|\colon S\subset[n]_m\hbox{ Sidon}\}$. An abridged version of our results states as follows.Fix a constant~$0\leq a\leq1$ and suppose~$m=m(n)=(1+o(1))n^a$. Thenthere is a constant $b=b(a)$ for which~$F([n]_m)=n^{b+o(1)}$ almostsurely. The function~$b=b(a)$ is a continuous, piecewise linearfunction of~$a$, not differentiable at two points:~$a=1/3$and~$a=2/3$; between those two points, the function~$b=b(a)$ isconstant.

The Chv\'atal--Erd\H{o}s Theorem states that every graph whose connectivityis at least its independence number has a spanning cycle. In 1976, Fouquet andJolivet conjectured an extension: If $G$ is an $n$-vertex $k$-connectedgraph with independence number $a$, and $a \ge k$, then $G$ has a cycle of lengthat least $\frac{k(n+a-k)}{a}$. We prove this conjecture. This is joint work with Suil O and Douglas B. West.

We consider the question of coloring the first n integers with two colors in such a way as to avoid copies of a given arithmetic configuration (such as 3 term arithmetic progressions, or solutions to x+y=z+w). We know from results of Van der Waerden and others that avoiding such configurations completely is a hopeless task if n is sufficiently large, so instead we look at the question of finding colorings with comparatively few monochromatic copies of the configuration. At the very least, can we do significantly better than just closing our eyes and coloring randomly? I will discuss some partial answers, experimental results, and conjectured answers to these questions for certain configurations based on joint work with Steven Butler and Ron Graham.

We extend the theory of infinite matroids recently developed by Bruhn et al to a well-known classical result in finite matroids while using the theory of connectivity for infinitematroids of Bruhn and Wollan. We prove that every infinite connected matroid M determines a graph-theoretic decomposition tree whose vertices correspond to minors of M that are3-connected, circuits, or cocircuits, and whose edges correspond to 2-separations of M. Tutte and many other authors proved such a decomposition for finite graphs; Cunningham andEdmonds proved this for finite matroids and showed that this decomposition is unique if circuits and cocircuits are also allowed. We do the same for infinite matroids. The knownproofs of these results, which use rank and induction arguments, do not extend to infinite matroids. Our proof avoids such arguments, thus giving a more first principles proof ofthe finite result. Furthermore, we overcome a number of complications arising from the infinite nature of the problem, ranging from the very existence of 2-sums to proving the treeis actually graph-theoretic.