Combinatorics Seminar

When: Sunday, June 10, 10am Where: Schreiber 309 Speaker: Gil Kalai, Hebrew University Title: Random Graphs and Analysis of Boolean functions - Two problems

Abstract:

We will discuss two conjectures regarding Boolean functions which are related to questions in random graph theory. We will start with the second conjecture and if time allows we will also discuss the first.

The first conjecture to be described (with Friedgut) is called the Entropy-Influence Conjecture. It gives a far reaching extension to the KKL theorem, and theorems by Friedgut, Bourgain, and me.

The second conjecture (with Kahn) proposes a far-reaching generalization to results by Friedgut, Bourgain and Hatami. This conjecture is related via a complicated array of intermediate problems (generalizations and restrictions) to the following Conjecture with Kahn.

Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H' in G is at least 1/2 for every subgraph H' of H. Let p be the value for which the probability that G contains a copy of H is 1/2. Conjecture: p/q = O(log n).

We also mention a simple yet annoying question related to Kruskal Katona's theorem.