EDP24 — an attempt to get back into the diagonal-decomposition approach

Gil has a not quite finished third post that will appear soon on this blog. Meanwhile, here are a few thoughts I’ve had recently as I tried to get my brain into EDP mode again.

The approach to the Erdős discrepancy problem that, rightly or wrongly, I found most promising when we were last working on it was to prove a certain statement about matrices that can be shown quite easily to imply a positive solution to the problem. In this post, I’m going to treat that matrix statement as the problem, and think about how one might go about trying to prove it. I’ll give the brief explanation of why it implies EDP, but not of what the possible advantages of the approach are (discussions of which can be found in some of the earlier material).

EDP23 — second guest post by Gil Kalai

The Large Deviation Heuristic: an example – triangle-free graphs

Here is a very general probabilistic-based heuristic that seems to give good predictions for questions related to EDP. I will refer to this heuristic as “LDH”. (In my polymath5 comments I referred to it as PH – probabilistic heuristic)). I am thankful to Noga Alon and to Yuval Peres for some helpful help.
Here is an example: Suppose we want to study the following extremal problem.

What is the largest number of edges in a graph on n vertices with no triangle.

If we use the probabilistic method we can ask what is the probability that a random graph in contains no triangle. As long as this probability is positive we know that a triangle-free graph with n vertices and m edges exists. (Being a little careful we can consider instead of where . Looking at random graphs gives us a perfectly correct proof of the assertion that there are triangle-free graphs with vertices and edges for every .

LDH:

1) Estimate naively the probability that a random graph in G(n,m) contains no triangle.

2) Choose m so that this estimated probability behaves like 1 over the number of graphs with n vertices and m edges.

EDP22 — first guest post by Gil Kalai

The purpose of this post is to ignite some new activity related to polymath5 about Erdős’ Discrepancy Problem. This post is thus a polymath5 research thread and comments (also unrelated to the suggestions in this post) are welcome.

The general form of a discrepancy problem

Let be a hypergraph, i.e., a collection of subsets of a ground set . The discrepancy of , denoted by is the minimum over all functions of the maximum over all of

.

We will mention one additional definition, that of hereditary discrepancy. When is a hypergraph and , the restriction of to is the hypergraph with vertex set whose edges are all sets of the form for edges of . The hereditary discrepancy of is the maximum over all of the discrepancy of restricted to .
Here is a link for a recent post discussing discrepancy and the famous Beck-Fiala theorem. The Beck-Fiala theorem assert that if every element in is included in at most sets in then . (Of course, the theorem applies also to the hereditary discrepancy.)

EDP: a possible revival

A few months ago, Gil Kalai got in touch to suggest that it was time to revisit Polymath5, the attempt to prove the Erdős discrepancy problem. I agreed, but we have both been rather busy in the interim, so it is only now that we are ready. One of the things that Gil did was write three posts, which I shall be putting up as guest posts, the first one today and the others over the next few days. I hope that people who contributed to the project the first time round will consider having another go, and that people who didn’t, but would be interested, will find that they can use the wiki that we created to record our progress to get up to speed with what is already known. Once Gil’s posts are up, I’ll probably write a post myself, and I hope that some serious work might start in early September. I always felt that when the original attempt petered out, it was just a kind of loss of energy that individual mathematicians often feel, rather than the result of hitting a brick wall. And just as having a break from a problem is often useful for individuals, I hope it will turn out to be for this polymath project. If it doesn’t, then maybe I’ll do something I meant to do much earlier, which is write up in paper form the progress that has already been made. (Of course, if I do that, then anybody is free to contribute to the writing.)

If you want to look at some of the earlier posts, they are collected together in the polymath5 category on this blog.