Polymath10, Post 2: Homological Approach

Posted on November 11, 2015 by Gil Kalai

We launched polymath10 a week ago and it is time for the second post. In this post I will remind the readers what the Erdos-Rado Conjecture and the Erdos-Rado theorem are, briefly mention some points made in the previous post and in the comments, make some remarks of administrative nature, and describe in detail a homological plan for attack, some of whose ingredients were mentioned in the first post.

Of course, there are various other avenues that can be explored: In a series of comments (e.g. this thread and that thread and this) Tim Gowers proposed a line of attack related to understanding quasirandom behavior of families of sets in terms of their pairwise intersections. (Update: Tim developed his ideas in further comments. A theme which is common to his approach as well as to the homological approach is to see if we can “improve” certain properties of the family after moving to an exponentially smaller subfamily. Second update: this post was written after 70 or so comments for post 1. There are many further interesting comments. ) Karim Adiprasito described a different topological combinatorics approach. Another clear direction is to try to extend the ideas of Spencer and Kostochka which led to the best known bounds today. Raising more ideas for attacking the conjecture is most welcome. For example, in Erdos Ko Rado theory, besides direct combinatorial arguments (mainly those based on “shifting,”) spectral methods are also quite important. Of course, the sunflower conjecture may be false as well and ideas on how to construct large families without sunflowers are also most welcome.

Terry Tao kindly set a Wiki page for the project and proposed to conduct computer experimentation for small values of $r$ and $k$ . Of course, computer experimentation will be most welcome! Some of the suggestions described below can also be tested experimentally for small values.

Let me also mention some surprising connections between the sunflower conjecture and various issues arising in matrix multiplication. As pointed by Shachar Lovett (in this comment and the following one), a counterexample to a certain structural special case of the sunflower conjecture will imply an almost quadratic algorithm for matrix multiplication!

Dömötör and I hyperoptimistically conjectured that the Erdos-Rado example is optimal for Balanced families. But Hao gave a very simple counterexample.

The status of our project at this stage is described very nicely by Tim Gowers who wrote:

At the time of writing, Gil’s post has attracted 60 comments, but it is still at what one might call a warming-up stage, so if you are interested in the problem and understand what I have written above, it should still be easy to catch up with the discussion. I strongly recommend contributing — even small remarks can be very helpful for other people, sparking off ideas that they might not have had otherwise. And there’s nothing quite like thinking about a problem, writing regular bulletins of the little ideas you’ve had, and getting feedback on them from other Polymath participants. This problem has the same kind of notoriously hard feel about it that the Erdős discrepancy problem had — it would be wonderful if a Polymath collaboration could contribute to its finally getting solved.

Update to an earlier post. Karim Adiprasito, June Huh, and Eric Katz have now posted their paper “Hodge theory for combinatorial geometries” which contains, among other things, a proof of the Heron-Rota-Welsh conjecture on matroids.

Here is a reminder of the sunflower theorem and conjecture:

The Erdos-Rado sunflower Theorem

A sunflower (a.k.a. Delta-system) of size $r$ is a family of sets $A_1, A_2, \dots, A_r$ such that every element that belongs to more than one of the sets belongs to all of them. We call the common element to all the sets the head of the sunflower (or the kernel of the sunflower), and the elements that belong to just one among the sets, the petals.

A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function $f(k,r)$ so that every family $\cal F$ of $k$ -sets with more than $f(k,r)$ members contains a sunflower of size $r$ .

We denote by $f(k,r)$ the smallest integer that suffices for the assertion of the theorem to be true.

The Erdos-Rado Sunflower Conjecture

The Erdos-Rado sunflower conjecture: $f(k,r) \le C_r^k$ .

Here, $C_r$ is a constant depending on $r$ . It may be also the case that we can take $C_r=Cr$ for some absolute constant C. The conjecture is already most interesting for $r=3$ . I recommend to reading Kostochka’s survey paper and also, as we go, it will be useful to learn Spencer’s argument and Kostochka’s argument which made remarkable improvements over earlier upper bounds.

The main purpose of this post is to provide

A Homological attack on the sunflower Conjecture

Part 1: Combinatorial Extensions and Variations

A) The question as an Erdos-Ko-Rado type question

Let $f(k,r,m;n)$ be the maximum size of a family $\cal F$ of $k$ -subsets of [n]= $\{1,2,\dots ,n\}$ containing no sunflower of size $r$ with head of size at most $m-1$ . (Note: it should me $m-1$ .)

Basic Question: Understand the function f(k,r,m;n). Is it true that $f(k,r,m;n)\le C_r^{k}n^{k-m}$ , where $C_r$ is a constant depending on r, perhaps even linear in r.

A family of $k$ -sets satisfies property P(k,r,m) if it contains no sunflower of size $r$ with head of size at most $m-1$ .

B) Stars and links: Given a family $F$ of sets and a set $S$ , the star of $S$ is the subfamily of those sets in $F$ containing $S$ , and the link of $S$ is obtained from the star of $S$ by deleting the elements of $S$ from every set in the star. Another way to say that $\cal F$ has property P(k,r,m) is that the link of every set of size ~~at most~~ less than $m$ contains no $r$ pairwise disjoint sets.

C) The balanced case

A family of $k$ -sets is balanced (or $k$ -colored, or multipartite) if it is possible to divide the ground set into $k$ parts so that every set in the family contains one element from every part.

Let $g(k,r,m;n)$ be the maximum size of a balanced family $\cal F$ of $k$ -subsets of [n]= $\{1,2,\dots ,n\}$ containing no sunflower of size $r$ with head of size at most $m$ . By randomly dividing the ground set into colors we obtain that $f(k,r,m;n) \le \frac{k^k}{k!}g(k,r,m;n)$ .

D) What we aim for. Below we describe two variations of a homological attack on the sunflower conjecture. If successful (as they are) they will lead to the following bounds.

The first variation based on conjectured homological properties of balanced families would yield

(*) $f(k,r,m;n)\le e^k {{(r-1)m}\choose{m}}\cdot{{n-m} \choose {k-m}}$

The alternative version would give

(**) $f(k,r,m;n)\le {{m+(r-1)k}\choose{m}}\cdot {{n-m}\choose {k-m}}$

Part 2: Collections of sets as geometric objects, homology and iterated homology.

E) Simplicial complexes and homology

Staring with a family ${\cal F}$ we will consider the collection of sets obtained by adding all subsets of sets in ${\cal F}$ . This is a simplicial complex, $K$ , and we can regard it as a geometric object if we replace every set of size $i$ by a simplex of dimension $i-1$ . (We call sets in $K$ of cardinality $(i+1)$ by the name i-faces.

The definition of homology groups only depends on the combinatorial data. For simplicity we assume that all sets in ${\cal F}$ (and hence in the associated simplicial complex) are subsets of {1,2,…,n}. We choose a field A (we can agree that the field will be the field of real numbers). Next we define for i>0 the vector space of $i$ -dimensional chains $C_i(K)$ as a vector space generated by i-faces of K. We also define a boundary map $\partial_i:C_i(K)\to C_{i-1}(K)$ for every $i$ . The kernel of $\partial_i$ is the space of i-cycles denoted by $Z_i(K)$ ; the image of $\partial_{i+1}$ is the space of i-boundaries, denoted by $B_i(K)$ . The crucial property is that applying boundary twice gives you zero, and this allows to define homology groups $H_i(K)=Z_i(K)/B_i(K)$ . The betti numbers are defined as $b_i(K)=dim H_i(K)$ . We will give the definition of the boundary operator further below.

F) Acyclic families and intersecting families

A family ${\cal F}$ of $k$ -sets is acyclic if it contains no $k$ -cycle, or equivalently if $H_k({\cal F})=0$ . (For coefficients in $Z/2Z$ , a $k$ -cycle $G$ is a family of $k$ -sets such that every set of size $(k-1)$ is included in an even number of $k$ -sets in $G$ .)

Proposition: An acyclic family of k-subsets of [n], contains at most ${{n-1} \choose {k-1}}$ sets.

In the first post we asked: Are there some connections between the property “intersecting” and the property “acyclic?”

Unfortunately, but not surprisingly intersecting families are not always acyclic, and acyclic families are not always intersecting. (The condition $2k \le n$ from EKR theorem also disappeared.) As we mentioned in the previous post intersecting balanced families are acyclic! And as we will see for balanced families Erdos-Ko-Rado properties translate nicely into homological property.

G) Pushing the analogy further

We made an analogy between “intersecting” and “acyclic”. Building on this analogy

1) What could be the “homological” property analogous to “every two sets have at least m elements in common”?

2) What could be the “homological” property analogous to “not having r pairwise disjoints sets”?

I will propose answers below the fold. What is your answer?

Continue reading →

Posted in Combinatorics, Polymath10 | Tagged algebraic shifting, Iterated homology, sunflower conjecture, Topological combinatorics | 89 Comments

Polymath10: The Erdos Rado Delta System Conjecture

Posted on November 3, 2015 by Gil Kalai

The purpose of this post is to start the polymath10 project. It is one of the nine projects (project 3d) proposed by Tim Gowers in his post “possible future polymath projects”. The plan is to attack Erdos-Rado delta system conjecture also known as the sunflower conjecture. We will start the research thread here. Mimicking a feature of polymath1 I will propose a detailed approach in the next post. Here, I will remind you of the conjecture and some basic known results, mention a few observation and ingredients of my point of view, and leave the floor to you comments.

The Erdos-Rado Delta-system Theorem and Conjecture

A sunflower (a.k.a. Delta-system) of size $r$ is a family of sets $A_1, A_2, \dots, A_r$ such that every element that belongs to more than one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado Delta-syatem theorem: There is a function $f(k,r)$ so that every family $\cal F$ of $k$ -sets with more than $f(k,r)$ members contains a sunflower of size $r$ .

(We denote by $f(k,r)$ the smallest integer that suffices for the assertion of the theorem to be true.) The simple proof giving $f(k,r)\le k! (r-1)^k$ can be found here.

One of the most famous open problems in extremal combinatorics is:

The Erdos-Rado conjecture: Prove that $f(k,r) \le C_r^k$ .

Here, $C_r$ is a constant depending on $r$ . It may be also the case that we can take $C_r=Cr$ for some absolute constant C. The conjecture is already most interesting for $r=3$ . And getting progress for $r=3$ will already be great.

At least for $r=2$ the delta system conjecture is true. Every two sets form a Delta-system of size two. So $f(k,2)=1$ . Can we find more difficult proofs and for weaker statements? The case $r=2$ will play a role in the context of more general questions.

The best known upper bounds

An excellent review paper is Extremal problem on Δ-systems by Alexandr Kostochka. After an early paper by L. Abbott, D. Hanson, and N. Sauer imroving both the upper and lower bounds, Joel Spencer proved an upper bound of $f(k,r) \le C$ $(1+\epsilon)^kk!$ for every fixed $r$ . Spencer also proved an upper bound $e^{k^{3/4}}k!$ for $r=3$ . (The exponent was improved further to 1/2 by Furedi and Kahn.) A remarkable result by Sasha Kostochka from 1996 is the best upper bound known today.

Sasha Kostochka

A summary of my proposed approach:

I. A more general problem

Given a family $F$ of sets and a set $S$ , the star of $S$ is the subfamily of those sets in $F$ containing $S$ , and the link of $S$ is obtained from the star of $S$ by deleting the elements of $S$ from every set in the star. (We use the terms link and star because we do want to consider eventually hypergraphs as geometric/topological objects.)

We can restate the delta system problem as follows: f(k,r) is the maximum size of a family of k-sets such that the link of every set A does not contain r pairwise disjoint sets.

What can we say about families of k-sets from {1,2,…,n} such that that the link of every set A of size at most m-1 does not contain r pairwise disjoint sets? In particular, what is f(k,r,m;n) the maximum number of sets in such a family. We can ask

Question 1: Understand the function f(k,r,m;n).

Question 2: Is it true that $f(k,r,m;n)\le C_r^{k}n^{k-m}$ , where $C_r$ is a constant depending on r, perhaps even linear in r.

My proposal is to approach the Delta-system problem via these questions. We note that Question 1 includes the Erdos-Ko-Rado theorem:

(r=2, m=1) Erdös-Ko-Rado Theorem: An intersecting of k-subsets of $N$ , when $2k \le n$ contains at most ${{n-1} \choose {k-1}}$ sets.

Here, a family of sets is “intersecting” if every two sets in the family has non empty intersection. The situation for $r=2$ and general $m$ was raised by Erdos-Ko-Rado (who proposed a conjecture for a certain special case), Frankl proposed a general conjecture that was settled by Alswede-Khachatrian. This was a remarkable breakthrough. The case of general r and m=1 is again a famous question of Erdos. The conjecture is that when $n \ge rk$ , $f(k,r,0,n)=\max ({{rk-1} \choose {k}}, {{n} \choose{k}}~-~{{n-r} \choose {k}}).$ This is a classic result by Erdos and Gallai (1959) for graphs (k=2), and very recently it was proved for r=3 for large values of $n$ , in the paper On Erdos’ extremal problem on matchings in hypergraphs by Tomasz Luczak, and Katarzyna Mieczkowska, and for all values of $n$ by Peter Frankl.

We want much weaker results (suggested by Problem 2) than those given (or conjectured) by Erdos-Ko-Rado theory, but strong enough to apply to the Delta system conjecture.

II. moving to the multipartite case

A family of $k$ -sets is balanced (or $k$ -colored) if it is possible to color the elements with $k$ colors so that every set in the family is colorful.

Reduction (folklore): It is enough to prove Erdos-Rado Delta-system conjecture for the balanced case.

Proof: Divide the elements into d color classes at random and take only colorful sets. The expected size of the surviving colorful sets is $k!/k^k|F|$ .

III: Enters homology

A family $F$ of $k$ -sets is acyclic (with Z2 coefficient) if it contains no $k$ -cycle. A $k$ -cycle $G$ is a family of $k$ -sets such that every set of size $(k-1)$ is included in an even number of $k$ -sets in $G$ .

Theorem 1: An acyclic family of k-subsets of [n], contains at most ${{n-1} \choose {k-1}}$ sets.

I suppose many people ask themselves:

Question 3: Are there some connections between the property “intersecting” and the property “acyclic?”

Unfortunately, but not surprisingly intersecting families are not always acyclic. And acyclic families are not always intersecting.(The condition $2k \le n$ from EKR theorem also disappeared in the result about acyclic families.)

Lets ignore for a minute that being acyclic and being intersecting are not related and ask.

Question 4: Is there some “acyclicity” condition related to (or analogous to) the property of not having 3 pairwise disjoint sets? r pairwise disjoint sets?

We know a few things about it.

Question 5: What can we say about families which are acyclic and so are all links for every set A of size at most m-1?

Here under some additional conditions there are quite a lot we can say in a direction of bounds asked for in Question 2.

(We note that one place where a connection between homology and Erdos-Ko-Rado theory was explored successfully is in the paper Homological approaches to two problems on finite sets by Rita Csákány and Jeff Kahn.)

IV) Coloring to the rescue!

Relating acyclicity and being intersecting is not easy in spite of the similar upper bound. We can ask now if for balanced families, there are some connections between the property “intersecting” and the property “acyclic?”

Question 6: Let $F$ be a balanced intersecting family of $k$ -sets, is $K$ acyclic?

The answer is yes. Eran Nevo pointed out a simple inductive argument which also extends in various directions. If you have a balanced k-dimensional cycle (mod Z/Z2) then by induction the link of a vertex v (which is also a cycle) has two disjoint sets R and R‘ and taking one of those sets with v and the other set with yet another vertex w yield a disjoint pair. (Each set of size k-1 in a cycle must be included in more than one sets of size k; in fact this is the only fact we are using.)

On technical matters: The project will run over this blog and Karim Adiprasito will join me in organizing it. (Perhaps to make the mathematical formulas appearing better we will move to another appearance.)

Posted in Combinatorics, Polymath10 | Tagged Alexandr Kostochka, Joel Spencer, Paul Erdos, Richard Rado | 121 Comments

Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies

Posted on October 28, 2015 by Gil Kalai

I am happy to report on two beautiful results on convex polytopes. One disproves an old conjecture of mine and one proves an old conjecture of mine.

Loiskekoski and Ziegler: Simple polytopes without small separators.

Does Lipton-Tarjan’s theorem extends to high dimensions? Can polytopes be expanders?

Lipton and Tarjan proved that a planar graph (hence the graph of a 3-polytope) with n vertices can be separated to connected parts each with no more than 2n/3 vertices by deleting $C\sqrt n$ vertices. I proposed a similar property (with a different exponent depending on the dimension) for graphs of simple polytopes in higher dimensions. This turned out to be false.

Simple polytopes without small separators:

Lauri Loiskekoski, Günter M. Ziegler

Abstract: We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least $\Omega(n/log^{3/2}n)$ This disproves a conjecture by Kalai from 1991/2004.

A major remaining open question is if we can have examples of graphs of simple 4-polytopes where every separator has at least cn vertices or perhaps even examples of such graphs that are expanders. (I conjecture that the answer is negative).

Expansion is closely related to diameter and there are various interesting higher dimensional analogs for the expansion property, for diameter question, and for the non-revisiting property which is crucial in the study of diameter of polytopal graphs.

Adiprasito, Nevo and Samper: Higher chordality and approximating smooth bodies by polytopes.

Consider a sequence of polytopes $P_n$ that converge to a smooth convex body K. It is easy that the number of vertices of these polytopes must tend to infinity and there are interesting theorems relating the quality of the approximation and the the number of vertices.

For a d-dimensional simplicial polytope P there are is remarkable set of parameters introduced by McMullen $(g_1(P),g_2(P),\dots g_m(P))$ where m=[d/2]. $g_1(P)$ is the number of vertices minus (d+1). $g_2(P)$ is the dimension of the space of stresses of a framework based on P. The nonnegativity of these numbers is the generalized lower bound theorem which is part of Stanley’s 1980 “g-theorem” (necessity part), which is one of the most important results on convex polytopes in the last decades. Here on the blog we devoted several posts (I,II,III,IV) to the g-theorem and the related g-conjecture for simplicial spheres. (Probably the g-conjecture for spheres is the single problem I devoted the most effort to in my career.)

I conjectured that for a sequence of polytopes $P_n$ that converge to a smooth convex body K, $g_i(K)$ tends to infinity for i ≤ [d/2]. This was now proved.

Higher Chordality III: A Geometric Lower Bound Theorem

Karim A. Adiprasito, Eran Nevo, José Alejandro Samper

Abstract: We resolve a conjecture of Kalai relating approximation theory of convex bodies by simplicial polytopes to the face numbers and primitive Betti numbers of these polytopes and their toric varieties. The proof uses higher notions of chordality. Further, for $C^2$ -convex bodies, asymptotically tight lower bounds on the g-numbers of the approximating polytopes are given, in terms of their Hausdorff distance from the convex body.

The paper continues a project which led already to:

Higher chordality I. From graphs to complexes by Karim A. Adiprasito, Eran Nevo, Jose A. Samper and

Higher chordality II: Toric chordality via the McMullen-Weil Lefschetz Map by

Karim A. Adiprasito

Further extensions for general polytopes, and similar results regarding the nonlinear part of the g-theorem would be of great interest.

More news in brief

A polymath10 project devoted to the Erdos Rado Delta System Conjecture will start over this blog in about a week. (This is one of the project proposals by Tim Gowers in this post.) Quanta magazine has an article on important progress by Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon and Kristina Vušković towards an efficient coloring argorithm for perfect graphs! (BTW, while we have several notions of chordality in high dimensions I am curious about appropriate notions of perfectness.) In this MathOverflow answer, I report (and describe the background) on the 2013 paper by Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec “Subcubic triangle-free graphs have fractional chromatic number at most 14/5“. This recent mathoverflow question asks for proposals for polymath projects.

$\Omega(n/log^{3/2}n)$ .

Posted in Combinatorics, Convex polytopes | Tagged Eran Nevo, Günter M. Ziegler, José Alejandro Samper, Karim A. Adiprasito, Lauri Loiskekoski | 1 Comment

Igor Pak’s collection of combinatorics videos

Posted on October 23, 2015 by Gil Kalai

The purpose of this short but valuable post is to bring to your attention

Igor Pak’s Collection of Combinatorics Videos

Posted in Combinatorics | Tagged Igor Pak | Leave a comment

EDP Reflections and Celebrations

Posted on October 22, 2015 by Gil Kalai

The Problem

In 1932, Erdős conjectured:

Erdős Discrepancy Conjecture (EDC) [Problem 9 here] For any constant ${C}$ , there is an ${n}$ such that the following holds. For any function ${f:[n] \rightarrow \{-1, +1\}}$ , there exists an ${a}$ and a $k \leq n/a$ such that

$\displaystyle |\sum_{i = 1}^{k}{f(ia)}| > C.$

For any ${a,k}$ , the set ${S_{a,k} = \{ia: 0\leq i \leq k\}}$ is an arithmetic progression containing ${0}$ ; we call such a set, a Homogenous Arithmetic Progression (HAP). The conjecture above says that for any red blue coloring of the [n] (={1,2,…,n}), there is some HAP which has a lot more of red than blue (or vice versa). Given C, we let n(C) to be the minimum value of n for which the assertion of EDC holds, and given n we write D(n) as the minimum value of C for which n(C) ≤ n.

EDC was a well-known conjecture and it was the subject of the fifth polymath project (making it even more well-known,) that took place in the first half of 2010. (With a few additional threads in August-September 2012.) That D(n) > 3 for n > 1160 (and that D(1160)=3 ) was proved in a 2014 paper by Boris Konev and Alexei Lisitsa.

The solution

The two defining moments in the life of a mathematical problem is the time it is born and the time it is solved. As you must have heard by now the Erdős discrepancy conjecture has recently (mid September, 2015) been proved by Terry Tao. I was very happy with the news, congratulations Terry!!

Reading material

(Video:) Terence Tao, The Erdős Discrepancy Problem, UCLA Math Colloquium, video by IPAM, Oct 8, 2015. (Thanks to Igor Pak)

(Papers:) The proof of the conjecture was done in two recent papers. The first The logarithmically averaged Chowla and Elliott conjectures for two-point correlations, proves a necessary analytic number theory result related to a classical conjecture of Chowla. The second paper – The Erdős discrepancy problem, shows the derivation of EDC from the number theory result. The number theoretic paper is based on a new recent breakthrough technique in analytic number theory initiated by Matomaki and Radziwill and further studied by Matomaki, Radzwill, and Tao. I also recommend a very interesting paper Erdős and arithmetic progressions from about a year ago by Gowers: where Tim tells side-by-side the story of Erdős-Turàn problem (leading to Roth-Szemeredi’s theorem), and that of EDP.

(Blog posts:) The proof is described in this blog post by Tao. A similar (somewhat simpler) argument proving EDC based on a number-theoretic conjecture (The Eliott Conjecture) can be found in this very readable blog post by Tao. In 2010 Tim Gowers ran a polymath project devoted to the Erdős discrepancy problem (EDP). A concluding post following Tao’s proof on Gowers’s blog is EDP28. You can also read about the problem and its solution on Lipton and Regan’s blog and in various other places.

(Popular scientific writings:) Quanta magazine (Erica Klarreich) : Nature (Chris Cesare), and various other places.

Erdős’s 1957 Problem paper

Erdős’s 1957 paper on open problems in number theory, geometry, and analysis is especially interesting. (It is linked above but the link here might be more stable.) It has 15 problems in number theory, 5 problems in Geometry, and 9 problems in analysis. Some of the problems are famous, and quite a few of them were settled, but some were new to me. It would be nice to go over them and see what their status is.

We will come back to Erdős’s 57 paper at the end.

Our celebration

To celebrate to solution here are a few things I would like to tell you (including something about the Erdős-Szusz discrepancy problem and its solution), as well as more things and problems related to EDP that I am curious about (the red items):

The proof; Other proofs? Other applications of the methods?
The value: What is the behavior of D(n)? a) Does the proof give $(\log n)^\alpha$ ? What will it take to get $(\log n)^{1/2}$ ? b) Find a multiplicative sequence of of length n of +1 and -1 with discrepancy $(\log n)^{1/2}$ . (Even better, find an infinite sequence with this property for every n.)
Sequences with diminishing correlation to Dirichlet characters. Find a sequence orthogonal to all characters with small discrepancy. Prove a stronger version of the conjecture for such sequences.
The hereditary discrepancy of HAP’s
Variants: Random subsets; square free integers;
Pseudointegers Can we understand softly and under greater generality why EDC is true?
Pseudo HAP: A toy problem proposed by several people in polymath5 is to replace the kth HAP by a random set of integers of density 1/k. The EDC and even the $\latex {\sqrt {\log n}$ prediction should still work.
Restricted gaps a) prime powers gaps, b) powers of two and primes gaps; c) small gaps
Modular versions
What is the strongest version of a statement saying: Functions with values 0, 1, -1 with diminishing correlations to Dirichlet characters have large discrepancy.
Erdős-Szüsz discrepancy problem and the question about basis. (This I heard from Gadi Kozma).
What is the RH-strength analog of Chowla’s conjecture?

The proof

A few words about the proof. Continue reading →

Posted in Combinatorics, Number theory | Tagged Paul Erdos, Terrence Tao | 4 Comments

Séminaire N. Bourbaki – Designs Exist (after Peter Keevash) – the paper

Posted on September 2, 2015 by Gil Kalai

Update: Nov 4, 2015: Here is the final version of the paper: Design exists (after P. Keevash).

On June I gave a lecture on Bourbaki’s seminare devoted to Keevash’s breakthrough result on the existence of designs. Here is a draft of the paper: Design exists (after P. Keevash).

Remarks, corrections and suggestions are most welcome!

I would have loved to expand a little on

1) How designs are connected to statistics

2) The algebraic part of Keevash’s proof

3) The “Rodl-style probabilistic part” (that I largely took for granted)

4) The greedy-random method in general

5) Difficulties when you move from graph decomposition to hypergraph decomposition

6) Wilson’s proofs of his theorem

7) Teirlink’s proof of his theorem

I knew at some point in rough details both Wilson’s proof (I heard 8 lectures about and around it from Wilson himself in 1978) and Teirlink’s (Eran London gave a detailed lecture at our seminar) but I largely forgot, I’d be happy to see a good source).

8) Other cool things about designs that I should mention.

9) The Kuperberg-Lovett-Peled work

(To be realistic, adding something for half these items will be nice.)

Here is the seminar page, (with videotaped lectures), and the home page of Association des collaborateurs de Nicolas Bourbaki . You can find there cool links to old expositions since 1948 which overall give a very nice and good picture of modern mathematics and its highlights. Here is the link to my slides.

In my case (but probably also for some other Bourbaki’s speakers) , it is not that I had full understanding (or close to it) of the proof and just had to decide how to present it, but my presentation largely represent what I know, and the seminaire forced me to learn. I was lucky that Peter gave a series of lectures (Video 1, Video 2, Video3, Video4 ) about it in the winter at our Midrasha, and that he decided to write a paper “counting designs” based on the lectures, and even luckier that Jeff Kahn taught some of it at class (based on Peter’s lectures and subsequent article) and later explained to me some core ingredients. Here is a link to Keevash’s full paper “The existence of design,” and an older post on his work.

Curiously the street was named only after Pierre Curie until the 60s and near the sign of the street you can still see the older sign.

Posted in Combinatorics | Tagged Nicolas Bourbaki, Peter Keevash | 4 Comments

Important formulas in Combinatorics

Posted on August 25, 2015 by Gil Kalai

Another spin-off of the Noga-poster-formula-competition is a MathOverflow question: Important formulas in combinatorics.

The question collects important formulas representing major progress in combinatorics.

So far there are 31 formulas and quite a few were new to me. There are several areas of combinatorics that are not yet represented. As is natural, many formulas come from enumerative combinatorics. Don’t hesitate to contribute (best – on MathOverflow) more formulas!

Here are a few:

Posted in Combinatorics | Tagged Combinatorics, Mathoverflow | 2 Comments

Updates and plans III.

Posted on August 14, 2015 by Gil Kalai

Update on the great Noga’s Formulas competition. (Link to the original post, many cash prizes are still for grab!)

This is the third “Updates and plans post”. The first one was from 2008 and the second one from 2011.

Updates: Combinatorics and more

A lot is happening! I plan to devote special posts to some of these developments.

The Heron-Rota-Welsh conjecture was solved by Adiprasito, Huh and Katz

Karim Adiprasito (with a fan), June Huh, and Eric Katz (click to enlarge!)

The Heron-Rota-Welsh conjecture regarding the log-concavity of coefficients of the characteristic polynomials of matroids is now proved in full generality by Karim Adiprasito, June Huh, and Erick Katz! (Along with several other related conjectures.) A few years ago Huh proved the conjecture for matroids over the reals, and with Katz they extended it to representable matroids over any field. Those results used tools from algebraic geometry. (See this post and this one.) Some months ago Adiprasito and Sanyal gave a proof, based on Alexanderov-Fenchel inequalities and measure concentration, for $c$-arrangements. The general approach of Adiprasito, Huh and Katz of doing “algebraic geometry” in more general combinatorial contexts is very promising. Here is a link to a vidotaped lecture Hodge theory for combinatorial geometries by June Huh.

Thresholds and bounds on erasure codes by Kumar and Pfister and by Kudekar, Mondelli, Şaşoğlu, and Urbanke

(Thanks to Elchanan Mossel and Avi Wigderson for telling me about it.)

Reed-Muller Codes Achieve Capacity on Erasure Channels by Santhosh Kumar, Henry D. Pfister

(and thanks to Kodlu’s comment) Reed-Muller Codes Achieve Capacity on the Binary Erasure Channel under MAP Decoding, by Shrinivas Kudekar, Marco Mondelli, Eren Şaşoğlu, Rüdiger Urbanke

Abstract (for the first paper; for the second see the comment below): This paper introduces a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, this method requires only that the codes are highly symmetric. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge to a number between 0 and 1, and the permutation group of each code is doubly transitive. This also provides a rare example in information theory where symmetry alone implies near-optimal performance.
An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength achieves capacity if its code rate converges to a number between 0 and 1. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. The primary tools used in the proof are the sharp threshold property for monotone Boolean functions and the area theorem for extrinsic information transfer functions.

For me, a pleasant surprise was to learn about connections between threshold behavior and coding theory that I was not aware of, and here specifically, using results with Bourgain on influences under specific groups of permutations.

Explicit extractors and Ramsey numbers by Chattopadhyay and Zuckerman

(Thanks to Guy Kindler and Avi Wigderson.)

Explicit Two-Source Extractors and Resilient Functions, by Eshan Chattopadhyay and David Zuckerman

Abstract: We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$ . Our extractor outputs one bit and has error $n^{-\Omega(1)}$ . The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$ .

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$ , for any $\delta>0$ . In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $polylog(n)$ -wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola \cite{Viola14}, achieved $q=n^{1/2 - \delta}$ .

Our other main contribution is a reduction showing how such a resilient function gives a two-source extractor. This relies heavily on the new non-malleable extractor of Chattopadhyay, Goyal and Li [CGL15].

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$ -Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al. [BRSW12] and matching independent work by Cohen [Coh15b].

Here are comments by Oded Goldreich. For me, a pleasant surprise regarding the construction is that it uses, in addition to an ingenious combination of ingenious recent results (by Li, Cohen, Goyal, the authors, and others) about extractors, also influences of sets of Boolean functions and, in particular, the important construction of Ajtai and Linial. (that I mentioned here several times). Recently with Bourgain and Kahn we studies influences of large sets giving examples related to the Ajtai-Linial example. Update: Another pleasant surprise was to learn (from Avi W.) that among the ingredients used in this new work is Feige’s collective coin flipping method with a very small number of rounds, which was used by Li miraculously in the extractor engineering.

The Garsia-Stanley’s decomposition conjecture was refuted by Duval, Goeckner, Klivans, and Martin

A non-partitionable Cohen-Macaulay simplicial complex by Art M. Duval, Bennet Goeckner, Caroline J. Klivans, and Jeremy L. Martin.

Duval, Goeckner, Klivans, and Martin gave an explicit and rather small counterexample to a conjecture of Garsia and Stanley that every Cohen-Macaulay simplicial complex is decomposable, namely its set of faces can be decomposed into Boolean intervals $[S_i,F_i]$ where $F_i$ are facets (maximal faces).

A Whitney Trick for Tverberg-Type Problems by Mabillard and Wagner

The much awaited paper by Mabillard and Wagner is now on the arxive. See this post on topological Tverberg’s theorem.

Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems, by Isaac Mabillard and Uli Wagner

Abstract: Motivated by topological Tverberg-type problems and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into R^d without triple, quadruple, or, more generally, r-fold points. Specifically, we are interested in maps f from K to $R^d$ that have no r-Tverberg points, i.e., no r-fold points with preimages in r pairwise disjoint simplices of K, and we seek necessary and sufficient conditions for the existence of such maps.
We present a higher-multiplicity analogue of the completeness of the Van Kampen obstruction for embeddability in twice the dimension. Specifically, we show that under suitable restrictions on the dimensions, a well-known Deleted Product Criterion (DPC) is not only necessary but also sufficient for the existence of maps without r-Tverberg points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick.
An important guiding idea for our work was that sufficiency of the DPC, together with an old result of Ozaydin on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the long-standing topological Tverberg conjecture. Unfortunately, our proof of the sufficiency of the DPC requires a “codimension 3” proviso, which is not satisfied for when K is the N-simplex.
Recently, Frick found an extremely elegant way to overcome this last “codimension 3” obstacle and to construct counterexamples to the topological Tverberg conjecture for d at least 3r+1 (r not a prime power). Here, we present a different construction that yields counterexamples for d at least 3r (r not a prime power).

Behavior of Möbius functions (and other multiplicative functions) in short intervals by Matomaki and Radziwill

(Thanks to Tami Ziegler) We followed over here here sparsely and laymanly a few developments in analytic number theory (mainly related to gaps in primes and Möbius randomness). It is a pleasure to mention another breakthrough, largely orthogonal to earlier ones by Kaisa Matomaki and Maksym Radziwill. (Here is a link to the paper and to related blog posts by Terry Tao (1), (2) (reporting also on subsequent works by Matomaki, Radzwill, and Tao) NEW (3) (4)).

Update (Sept 18, 2015): Terry Tao have just uploaded a paper to the arxive where he solves the Erdos Discrepancy problem! The number theory works by Tao with Matomaki and Radzwill play important role in the proof. See this blog post on Tao’s blog with links to two new relevant papers, and this post by Tim Gowers.

Belated updates : Past and future events

My fest

On mid-June my former students organized a lovely conference celebrating my 60th birthday which I enjoyed greatly. I do plan to devote a post to the lectures and the event. Meanwhile, here are a few pictures.

Travels

In the last year or so I made only very short trips. Here is a quick report on some from the last months.

BCC2015

This was the second time I participated in a British combinatorial conference, after BCC1979 that I participated as a student. My lecture and paper for the proceedings deal with questions around Borsuk’s problem. Here is the BCC paper Some old and new problems in combinatorial geometry I: Around Borsuk’s problem. The proceeding is as always very recommended and let me mention, in particular, Conlon, Fox and Sudakov’s survey on Graph Ramsey theory. One of the participants, Anthony Hilton, took part in each and every earlier BCC. Another, Peter Cameron (blog) also gave an impressive singing with guitar performance.

Bourbaki seminaire: Designs after Keevash

I gave an expose on Keevash’s work about designs. My experience with giving this seminar is quite similar to the experience of other mathematicians. It was an opportunity to learn quite a few new things. Here is a draft of the written exposition Design exists (after Peter Keevash). . (And here are the slides) Remarks are most welcome. The event was very exciting and J-P Serre actively participated in the first half of the day. I plan to write more about it once the paper is finalized.

LFT100 and celebrating (small part of) Matousek’s work

Laszlo Fejer Toth 100th birthday conference was in Budapest. I gave a talk (click for the slides) on works of Jiri Matousek. It was great to meet many friends from Hungary and other places, some of which I did not meet for many years, including Asia Ivic-Weiss, Wlodek and Greg Kuperberg, Frank Morgan, Sasha Barvinok, and many others. I plan to report at a later time on some things Sasha Barvinok have told me.

More birthday conferences

My colleagues Abraham Neyman (Merale) and Sergiu Hart celebrated with a back-to-back conferences devoted to Game theory. Egon Schulte and Caroly Bezdek celebrated together a 60th birthday conference. Congratulations to all.

Guest posts by Thilo Weinert

On infinite combinatorics are coming. We have some further promises for guest posts and even guest columns.

Polymath plans

I plan a new polymath project. Details will follow.

Between two cities

We live now in Tel-Aviv and I commute 2-3 times a week to Jerusalem. Jerusalem is, of course, a most exciting and beautiful city and a great place to live (especially in the summer), and I also love Tel-Aviv, its rhythm and atmosphere, and the beach, of course. My three children and grandchild are TelAvivians. One interesting aspect of the change is the move from a ground floor with a yard to a high floor with view.

(Dec 1,2015)

Checking the 2008 and 2011 plans: (In red – unfulfilled plans, in Green fulfilled plans).

2008 Plans and updates

Continue reading →

Posted in Combinatorics, Conferences, Updates | 6 Comments

NogaFest, NogaFormulas, and Amazing Cash Prizes

Posted on August 10, 2015 by Gil Kalai

Ladies and gentlemen, a conference celebrating Noga Alon’s 60th birthday is coming on January. It will take place at Tel Aviv University on January 17-21. Here is the event webpage. Don’t miss the event !

Cash Prizes!

The poster includes 15 formulas representing some of Noga’s works. Can you identify them?

The first commentator to identify a formula will win a prize of 10 Israeli Shekels (ILS) that can be claimed on Noga’s Fest itself, (or else, in person, next time we meet after the meeting.) Cash prizes claimed in person on the meeting will be doubled! Cash prizes for the oldest and newest formulas are tripled! There is a limit of one answer/prize per person/ per week. Answers need to include the formula itself, tell what the formula is, and give crucial details about it.

More cash prizes!!

For each of these formulas, once identified, the comment giving the latest place where the formula is reproduced, (in a later paper or book not coauthored by any of the original discoverers) will be eligible also to 5 ILS prize. The same doubling and tripling rules as above apply. Here there is no limit on answers per person.

And even more cash prizes !!!

There will be 5 additional prizes of 20 ILS for formulas by Noga, that did not make it to the poster. Same doubling and tripling rules apply.

And Even More! Win a Travel Grant to the conference

Among all participants who are students or post docs, one grant for a round trip to the meeting will be given.

Rules

People involved in preparing the poster are not eligible.

The competition opens now!!!

And here are more details on the meeting itself. (The meeting also celebrates a decade anniversary for Zeilberger’s Opinion 71.) Continue reading →

Posted in Combinatorics, Conferences, Updates | Tagged Cash prizes, Noga Alon | 27 Comments

Carmella Kalai (1926-2015)

Posted on August 2, 2015 by Gil Kalai

My beloved mother Carmella Kalai passed away last week.

With me, 1956

My father Hanoch Kalai, my mother Carmella, My sister Tamar (Tami) and me around 1957). Continue reading →

Posted in Art, Obituary, personal, Updates | Tagged Carmella Kalai | 2 Comments

	Gil Kalai on Polymath10, Post 2: Homologica…
	daeseoklee on Polymath10, Post 2: Homologica…
	gowers on Polymath10, Post 2: Homologica…
	Gil Kalai on Polymath10, Post 2: Homologica…
	domotorp on Polymath10, Post 2: Homologica…
	Gil Kalai on Polymath10, Post 2: Homologica…
	domotorp on Polymath10, Post 2: Homologica…
	domotorp on Polymath10, Post 2: Homologica…
	Gil Kalai on Polymath10, Post 2: Homologica…
	Philip Gibbs on Polymath10, Post 2: Homologica…
	Gil Kalai on Polymath10, Post 2: Homologica…
	GFP on Four Derandomization Problems

The Erdos-Rado sunflower Theorem

The Erdos-Rado Sunflower Conjecture

A Homological attack on the sunflower Conjecture

Part 1: Combinatorial Extensions and Variations

Part 2: Collections of sets as geometric objects, homology and iterated homology.

Share this:

Like this:

The Erdos-Rado Delta-system Theorem and Conjecture

The best known upper bounds

A summary of my proposed approach:

I. A more general problem

II. moving to the multipartite case

III: Enters homology

IV) Coloring to the rescue!

Share this:

Like this:

Loiskekoski and Ziegler: Simple polytopes without small separators.

Does Lipton-Tarjan’s theorem extends to high dimensions? Can polytopes be expanders?

Adiprasito, Nevo and Samper: Higher chordality and approximating smooth bodies by polytopes.

More news in brief

Share this:

Like this:

Share this:

Like this:

The Problem

The solution

Reading material

Erdős’s 1957 Problem paper

Our celebration

The proof

Like this:

Like this:

The question collects important formulas representing major progress in combinatorics.

Like this:

Updates: Combinatorics and more

The Heron-Rota-Welsh conjecture was solved by Adiprasito, Huh and Katz

Thresholds and bounds on erasure codes by Kumar and Pfister and by Kudekar, Mondelli, Şaşoğlu, and Urbanke

Explicit extractors and Ramsey numbers by Chattopadhyay and Zuckerman

The Garsia-Stanley’s decomposition conjecture was refuted by Duval, Goeckner, Klivans, and Martin

A Whitney Trick for Tverberg-Type Problems by Mabillard and Wagner

Behavior of Möbius functions (and other multiplicative functions) in short intervals by Matomaki and Radziwill

Belated updates : Past and future events

My fest

Travels

BCC2015

Bourbaki seminaire: Designs after Keevash

LFT100 and celebrating (small part of) Matousek’s work

More birthday conferences

Guest posts by Thilo Weinert

Polymath plans

Between two cities

Checking the 2008 and 2011 plans: (In red – unfulfilled plans, in Green fulfilled plans).

2008 Plans and updates

Share this:

Like this:

Cash Prizes!

More cash prizes!!

And even more cash prizes !!!

And Even More! Win a Travel Grant to the conference

Rules

The competition opens now!!!

Like this:

Like this:

Recent Comments

Recent Posts

Top Posts & Pages

RSS

Categories

Blogroll

Archives

Follow “Combinatorics and more”