Georgia Institute of Technology College of Sciences

We formulate super-resolution as an inverse problem in the space of measures, and introduce a discrete and a continuous model. For the discrete model, the problem is to accurately recover a sparse high dimensional vector from its noisy low frequency Fourier coefficients. We determine a sharp bound on the min-max recovery error, and this is an immediate consequence of a sharp bound on the smallest singular value of restricted Fourier matrices. For the continuous model, we study the total variation minimization method. We borrow ideas from Beurling in order to determine general conditions for the recovery of singular measures, even those that do not satisfy a minimum separation condition. This presentation includes joint work with John Benedetto and Wenjing Liao.

No Combinatorics Seminar, but many others of interest: (a) on Friday [September 29th, 1pm-2pm in Skiles 005] He Guo, will give an ACO Student Seminar on "Packing nearly optimal Ramsey R(3,t) Graphs" (b) on Thursday [September 28th, 11am-12am in Skiles 006] Tom Bohman will give an ACO colloquim talk on "Randomized Controlled Trials for Combinatorial Construction" (c) on Saturday and Sunday [September 30th and October 1st] Atlanta Lecture Series in Combinatorics and Graph Theory XX takes place at Georgia Tech, with featured speaker Paul Seymour

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.