Georgia Institute of Technology College of Sciences

Colloids are mixtures of molecules  well-studied in material science that are not well-understood mathematically.  Physicists model colloids as a system of two types of tiles (type A and type B) embedded on a region of the plane, where no two tiles can overlap.  It is conjectured that at high density, the type A tiles tend to separate out and form large "clusters".   To verify this conjecture, we need methods for counting these configurations directly or efficient algorithms for sampling.  Local sampling algorithms are known to be inefficient. However, we provide the first rigorous analysis of a global "DK Algorithm" introduced by Dress and Krauth.  We also examine the clustering effect directly via a combinatorial argument. We prove for a certain class of colloid models that at high density the configurations are likely to exhibit clustering, whereas at low density the tiles are all well-distributed. Joint work with Sarah Miracle and Dana Randall.

In the Property Testing model an algorithm is required to distinguish between the case that an object has a property or is far from having the property. Recently, there has been a lot of interest in understanding which properties of Boolean functions admit testers making only a constant number of queries, and a common theme investigated in this context is linear invariance. A series of gradual results has led to a conjectured characterization of all testable linear invariant properties. Some of these results consider properties where the query upper bounds are towers of exponentials of large height dependent on the distance parameter. A natural question suggested by these bounds is whether there are non-trivial families with testers making only a polynomial number of queries in the distance parameter.In this talk I will focus on a particular linear-invariant property where this is indeed the case: odd-cycle freeness.Informally, a Boolean function fon n variables is odd-cycle free if there is no x_1, x_2, .., x_2k+1 satisfying f(x_i)=1 and sum_i x_i = 0.This property is the Boolean function analogue of bipartiteness in the dense graph model. I will discuss two testing algorithms for this property: the first relies on graph eigenvalues considerations and the second on Fourier analytic techniques. I will also mention several related open problems. Based on joint work with Arnab Bhattacharyya, Prasad Raghavendra, Asaf Shapira

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.