Georgia Institute of Technology College of Sciences

In 1995 Kim famously proved the Ramsey bound $R(3,t) \ge c t^2/\log t$ by constructing an $n$-vertex graph that is triangle-free and has independence number at most $C \sqrt{n \log n}$. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph $K_n$ into a packing of such nearly optimal Ramsey $R(3,t)$ graphs. More precisely, for any $\epsilon>0$ we find an edge-disjoint collection $(G_i)_i$ of $n$-vertex graphs $G_i \subseteq K_n$ such that (a) each $G_i$ is triangle-free and has independence number at most $C_\epsilon \sqrt{n \log n}$, and (b) the union of all the $G_i$ contains at least $(1-\epsilon)\binom{n}{2}$ edges. Our algorithmic proof proceeds by sequentially choosing the graphs $G_i$ via a semi-random (i.e., Rödl nibble type) variation of the triangle-free process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabó (concerning a Ramsey-type parameter introduced by Burr, Erdös, Lovász in 1976). Namely, denoting by $s_r(H)$ the smallest minimum degree of $r$-Ramsey minimal graphs for $H$, we close the existing logarithmic gap for $H=K_3$ and establish that $s_r(K_3) = \Theta(r^2 \log r)$. Based on joint work with Lutz Warnke.

The probabilistic method for constructing combinatorial objects has had a profound impact on the field since the pioneering work of Erdos in the first half of the twentieth century. Some recent applications of the probabilistic method build objects of interest by making a series of random choices that are guided by a simple rule and depend on previous choices. We give two examples of randomized algorithms of this type: random triangle removal and the triangle-free process. These algorithms address the classical questions of counting Steiner triple systems and determining the minimum independence number of a triangle-free graph on n vertices, respectively. Pseudo-random heuristics and concentration of measure phenomena play a central role in analyzing these processes.

The Gabor system of a function is the set of all of its integer translations and modulations. The Balian-Low Theorem states that the Gabor system of a function which is well localized in both time and frequency cannot form an Riesz basis for $L^2(\mathbb{R})$. An important tool in the proof is a characterization of the Riesz basis property in terms of the boundedness of the Zak transform of the function. In this talk, we will discuss results showing that weaker basis-type properties also correspond to boundedness of the Zak transform, but in the sense of Fourier multipliers. We will also discuss using these results to prove generalizations of the Balian-Low theorem for Gabor systems with weaker basis properties, as well as for shift-invariant spaces with multiple generators and in higher dimensions.

We shall make an overview of the interplay between the geometry of tubular neighbourhoods of Riemannian manifold and the spectrum of the associated Dirichlet Laplacian. An emphasis will be put on the existence of curvature-induced eigenvalues in bent tubes and Hardy-type inequalities in twisted tubes of non-circular cross-section. Consequences of the results for physical systems modelled by the Schroedinger or heat equations will be discussed.