Georgia Institute of Technology College of Sciences

A sequence A of positive integers is r-Ramsey complete if for every r-coloring of A, every sufficiently large integer can be written as a sum of the elements of a monochromatic subsequence. Burr and Erdos proposed several open problems in 1985 on how sparse can an r-Ramsey complete sequence be and which polynomial sequences are r-Ramsey complete. Erdos later offered cash prizes for two of these problems. We prove a result which solves the problems of Burr and Erdos on Ramsey complete sequences. The proof uses tools from probability, combinatorics, and number theory. 

Joint work with David Conlon.

Traditional Erdos Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain properties by showing that a random (appropriately defined) object will have those properties with positive probability. Modern Erdos Magic analyzes a random process, a random (CS take note!) algorithm. These, when successful, can find a "needle in an exponential haystack" in polynomial time. We'll look at two particular examples, both involving a family of n-element sets under suitable side conditions. The Lovasz Local Lemma finds a coloring with no set monochromatic. A result of this speaker finds a coloring with low discrepency. In both cases the original proofs were not implementable but Modern Erdos Magic finds the colorings in polynomial times. The methods are varied. Basic probability and combinatorics. Brownian Motion. Semigroups. Martingales. Recursions ... and Tetris!

The talk is meant to be a gentle introduction to a part of combinatorial topology which studies randomly generated objects. It is a rapidly developing field which combines elements of topology, geometry, and probability with plethora of interesting ideas, results and problems which have their roots in combinatorics and linear algebra.

There are many instances in Coding Theory when codewords must be restored from partial information, like defected data (error correcting codes), or some superposition of the strings.These lead to superimposed codes, close relatives of group testing problems.There are lots of versions and related problems, likeSidon sets, sum-free sets, union-free families, locally thin families, cover-free codes and families, etc.We discuss two cases {\it cancellative} and {\it union-free} codes.A family of sets $\mathcal F$ (and the corresponding code of0-1 vectors) is called {\bf union-free} if $A\cup B = C\cup D$ and $A,B,C,D\in \mathcal F$ imply $\{ A,B\}=\{ C, D \}$.$\mathcal F$ is called $t$-{\bf cancellative}if for all distict $t+2$ members $A_1, \dots, A_t$ and $B,C\in \mathcal F$ $$A_1\cup\dots \cup A_t\cup B \neq A_1\cup \dots A_t \cup C. $$Let $c_t(n)$ be the size of the largest $t$-cancellative code on $n$elements. We significantly improve the previous upper bounds of Alon, Monti, K\"orner and Sinaimeri, and introduce a method to deal with such problems, namely to investigate first the constant weight case (i.e., uniform hypergraphs).