Effective Random Methods in Discrete Mathematics

Introduction

The probabilistic method, pioneered by Paul Erdős, can show the existence of combinatorial objects without hinting how to construct them effectively. Recent developments concerning the constructive version of Lovász Local Lemma (LLL) showed how to modify the probabilistic method to make it effective. This proposal lists four research directions in analysis, combinatorics, and cryptography, where this method opened new possibilities to go beyond our present knowledge.

Research Directions

1. Measurable Version of LLL
   The question is whether the object, guaranteed by LLL, can additionally be measurable. In some special cases, the answer is affirmative. We aim to explore:

   • What are the constraints that guarantee measurability?
   • When is it impossible to achieve this?
     Results are relevant for classical problems of measure group theory.

2. Improvement of the Sunflower Lemma
   A novel approach improving the celebrated sunflower lemma also uses effective probabilistic tools. We will use a similar approach to improve the best estimates for:

   • Multicolor Ramsey numbers
   • Schur numbers
   • A number of other classical problems

3. Extremal Graphs with Ordered Vertices or Edges
   Several new phenomena arise in extremal graphs when either the vertices or the edges are linearly ordered. To investigate them, we use methods from effective probabilistic sampling. The answers would be relevant in:

   • Discrete geometry
   • Algorithm design

4. Relaxing Requirements in Cryptographic Primitives
   An emerging phenomenon in certain cryptographic primitives, including secret sharing, will be addressed. Relaxing the strict requirements of correctness by allowing negligible errors can lead to significant improvements in efficiency. This is a direct consequence of the mostly unknown structure of the boundary of the entropy region. Using tools and results from the other parts of the project, we will explore this boundary, providing hints for why and tools for where and when such efficiency gaps might occur.