Georgia Institute of Technology College of Sciences

Ramsey theory studies the internal homogenity of mathematical structures (i.e. graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called "Ramsey number", and on the minimum object size such that the first player has a winning strategy in the corresponding combinatorial game, called "game number". In this talk, we investigate the "restricted Ramsey-type theorems". This means, we show the existence of first player's winning strategies, and we show that game numbers are surprisingly small, compared to Ramsey numbers. (This is joint work with Jarek Nesetril.)

In this work we study the ruin problem for a generalized Cramer-Lundberg reserve model with investments, under the modeling (volatility and claim intensity) uncertainty. We formulate the problem in terms of the newly developed theory on G-Expectation, initiated by S. Peng (2005). More precisely, we recast the problem as to determine the ruin probability under a G-expectation for a reserve process with a G-Compound Poisson type claim process, and perturbed by a G-Brownian motion. We show that the Lundberg bounds for a finite time ruin probability can still be obtained by an exponential $G$-martingale approach, and that the asymptotic behavior of the ruin, as the initial endowment tends to infinity, can be analyzed by the sample path large deviation approach in a G-expectation framework, with respect to the corresponding storage process. This is a joint work with Xin Wang.

A multivariate real polynomial p(x) is nonnegative if p(x) is at least 0 for all x in R^n. I will review the history and motivation behind the problem of representing nonnegative polynomials as sums of squares. Such representations are of interest for both theoretical and practical computational reasons, with many applications some of which I will present. I will explain how the problem of describing nonnegative polynomials fits into convex algebraic geometry: the study of convex sets with underlying algebraic structure, that brings together ideas of optimization, convex geometry and algebraic geometry. I will end by presenting current research problems in this area.

The traveling salesman problem (TSP) is the most famous problem in discrete optimization. Given $n$ cities and the costs $c_{ij}$ for traveling from city $i$ to city $j$ for all $i,j$, the goal of the problem is to find the least expensive tour that visits each city exactly once and returns to its starting point. We consider cases in which the costs are symmetric and obey the triangle inequality. In 1954, Dantzig, Fulkerson, and Johnson introduced a linear programming relaxation of the TSP now known as the subtour LP, and used it to find the optimal solution to a 48-city instance. Ever since then, the subtour LP has been used extensively to find optimal solutions to TSP instances, and it is known to give extremely good lower bounds on the length of an optimal tour. Nevertheless, the quality of the subtour LP bound is poorly understood from a theoretical point of view. For 30 years it has been known that it is at least 2/3 times the length of an optimal tour for all instances of the problem, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in 30 years in tightening these bounds. In this talk we will review some of the results that are known about the subtour LP, and give some new results that refine our understanding in some cases. In particular, we resolve a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case. We also begin a study of the subtour LP bound for the extremely simple case in which all costs $c_{ij}$ are either 1 or 2. For these instances we can show that the subtour LP is always strictly better than 3/4 times the length of an optimal tour. These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.