Discrete Graduate Students Seminar

Probabilistic Proofs of the Colorful Caratheodory and Tverberg’s Theorems in Combinatorial Geometry

We examine new probabilistic proofs of the colorful Caratheodory theorem and Tverberg’s theorem with tolerance. These theorems are classic results in the study of the intersection patterns of convex sets. Specifically, the colorful Caratheodory theorem generalizes the classical theorem of Caratheodory which states that any point in the convex hull of a set of points in \(\mathbb{R}^{d}\) can be expressed as a convex combination of at most \(d+1\) of those points. Tverberg’s theorem, which is a generalization of Radon’s lemma, states that any set of at least \((d+1)(r−1)+1\) points in \(\mathbb{R}^{d}\) can be partitioned into \(r\) disjoint subsets whose convex hulls contain a common point.

While these two theorems were proven by Barany (1982) and Tverberg (1966) respectfully, here we discuss new proofs via the probabilistic method. In particular, these proofs make use of Hoeffding’s concentration inequality, which we examine in some detail. We also present an introduction to basic convexity through the lens of discrete geometry to provide context for the primary results. Finally, we discuss algorithmic problems related to these concepts and present some open problems.

The Flag Algebra Method in Extremal Combinatorics

The fundamental question in extremal combinatorics asks the following. Given a fixed graph \(H\) that we want to avoid, what is the maximum number of edges, \(ex(n,H)\), in a graph \(G\) on \(n\) vertices, that guarantees no subgraph of \(G\) is isomorphic to \(H\)? Also, when number of edges is above \(ex(n,H)\), how many copies of \(H\) are guaranteed to exist?

The flag algebra method introduced by Alexander Razborov in 2009 has found its applications to many long-standing open problems in extremal combinatorics. This method is designed to analyze asymptotic behavior of substructure densities present inside a finite structure. In this project, we briefly describe the flag algebra method and then use this method to present an alternate proof of Mantel’s theorem for triangle-free graphs (i.e., when \(H\) is a triangle in the question above). Time permitting, we will also describe some other breakthroughs achieved by this method as well as related open problems.