Georgia Institute of Technology College of Sciences

The Birthday Paradox says that if there are N days in a year, and 1.2*sqrt(N) days are chose uniformly at random with replacement, then there is a 50% probability that some day was chosen twice. This can be interpreted as a statement about self-intersection of random paths of length 1.2*sqrt(N) on the complete graph K_N with loops. We prove an extension which shows that for many graphs random paths with length of order sqrt(N) will have the same self-intersection property. We finish by discussing an application to the Pollard Rho Algorithm for Discrete Logarithm. (joint work with Jeong-Han Kim, Yuval Peres and Prasad Tetali).

This is an expository account of recent work on the enumeration of maps (graphs embedded on a surface of arbitrary genus) and branched covers of the sphere.  These combinatorial and geometric objects can both be represented by permutation factorizations, in the which the subgroup generated by the factors acts transitively on the underlying symbols (these are called "transitive factorizations"). Various results and methods are discussed, including a number of methods from mathematical physics, such as matrix integrals and the KP hierarchy of integrable systems. A notable example of the results is a recent recurrence for triangulations of a surface of arbitrary genus obtained from the simplest partial differential equation in the KP hierarchy. The recurrence is very simple, but we do not know a combinatorial interpretation of it, yet it leads to precise asymptotics for the number of triangulations with n edges, of a surface of genus g.

The Balog-Szemeredi-Gowers theorem is a widely used tool in additive combinatorics, and it says, roughly, that if one has a set A such that the sumset A+A is "concentrated on few values," in the sense that these values v each get close to n representations as v = a+b, with a,b in A, then there is a large subset A' of A such that the sumset A'+A' is "small" -- i.e. it has size a small multiple of n. Later, Sudakov, Szemeredi and Vu generalized this result to handle multiple sums A_1 + ... + A_k. In the present talk we will present a refinement of this result of Sudakov, Szemeredi and Vu, where we get better control on the growth of sums A'+...+A'. This is joint work with Ernie Croot.

Let A be a set of n real numbers. A central problem in additive combinatorics, due to Erdos and Szemeredi, is that of showing that either the sumset A+A or the product set A.A, must have close to n^2 elements. G. Elekes, in a short and brilliant paper, showed that one can give quite good bounds for this problem by invoking the Szemeredi-Trotter incidence theorem (applied to the grid (A+A) x (A.A)). Perhaps motivated by this result, J. Solymosi posed the following problem (actually, Solymosi's original problem is slightly different from the formulation I am about to give). Show that for every real c > 0, there exists 0 < d < 1, such that the following holds for all grids A x B with |A| = |B| = n sufficiently large: If one has a family of n^c lines in general position (no three meet at a point, no two parallel), at least one of them must fail to be n^(1-d)-rich -- i.e. at least one of then meets in the grid in fewer than n^(1-d) points. In this talk I will discuss a closely related result that I and Evan Borenstein have proved, and will perhaps discuss how we think we can use it to polish off this conjecture of Solymosi.