Fix a Horse Race…

GK (2019): Can you base world economy on horse races? Here is an old unpublished draft from 2008 that I did not complete, which was  inspired by the  economic crisis at that time. (It also felt a little over the top, but my standards since then have relaxed somewhat.)

Another opportunity to be reminded with this old post came in a recent conference at Pittsburgh where I had an interesting conversation over lunch with Bill Benter whose company uses statistical methods to get ahead of Horse race gambling.  

Continue reading

Advertisements
Posted in Economics, Games, Rationality, Taxi-and-other-stories | Tagged , , , | Leave a comment

Attila Por’s Universality Result for Tverberg Partitions

In this post  I would like to tell you about three papers and three theorems. I am thankful to Moshe White and Imre Barany for helpful discussions.

a) Universality of vector sequences and universality of Tverberg partitions, by Attila Por;

Theorem (Por’s universality result, 2018): Every long enough sequence of points in general position in \mathbb R^d  contains a subsequence of length n whose Tverberg partitions are exactly the so called rainbow partitions.

b) Classifying unavoidable Tverberg partitions, by Boris BukhPo-Shen LohGabriel Nivasch

Theorem (Bukh, Loh, and Nivasch, 2017): Let H be a tree-like r-uniform simple hypergraph with d+1 edges and n=(d+1)(r-1)+1 edges. It is possible to associate to the vertices of each such hypergraph H a set X of n points in \mathbb R^d so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is (r-1)!^d. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

c) On Tverberg partitions, by Moshe White

Theorem (White, 2015): For any partition a_1,a_2,\dots ,a_r: 1 \le a_i\le d+1 of n, there exists a set X \subset \mathbb R^d of n  points, such that every Tverberg partition of X  induces the same partition on n given by the parts a_1,\dots,a_r. Moreover, the number of Tverberg’s partitions of X is (r-1)!^d

See the original abstracts for the papers at the end of the post.

Radon’s and Tverberg’s theorems and Sierksma’s conjecture

Recall the beautiful theorem of Tverberg: (We devoted two posts (I, II) to its background and proof.)

Tverberg Theorem (1965): Let x_1,x_2,\dots, x_m be points in R^d, m \ge (r-1)(d+1)+1. Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that \cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset.

The (much easier) case r=2 of Tverberg’s theorem is Radon’s theorem.

We devoted a post to seven open problems related to Tverberg’s theorem, and one of them was:

Sierksma Conjecture: The number of Tverberg’s r-partitions of a set of (r-1)(d+1)+1 points in R^d is at least ((r-1)!)^d.

Gerard Sierksma’s construction with (r-1)!^d Tverberg’s partition is obtained by taking (r-1) copies of each vertex of a simplex containing the origin in its interior, and adding the origin itself. A configuration of (r-1)(d+1)+1 points in R^d with precisely ((r-1)!)^d Tverberg partitions to r parts is called a Sierksma Configuration.

White’s Theorem

In 2015 Moshe White proved the following theorem which was an open problem for many years. White’s construction was surprisingly simple.

Theorem 1 (White, 2015):  For any partition a_1,a_2,\dots ,a_r: 1 \le a_i\le d+1 of n, there exists a set X \subset \mathbb R^d of n  points, such that every Tverberg partition of X  induces the same partition on n given by the parts a_1,\dots,a_r. Moreover, the number of Tverberg’s partitions of X is (r-1)!^d

Bukh, Loh, and Nivasch’s  examples via staircase convexity.

Five tree-like simple hypergraphs that correspond to configurations of 11 points in 4-dimensional space.

Start with a tree-like hypergraph H of d+1 blocks of size r like the five examples in the Figure above. The intersection of every two blocks has at most one element. The union of all blocks has n=(d+1)(r-1)+1 elements.

A rainbow coloring of a r-uniform hypergraph H is a coloring of the vertices of H with r colors so that the vertices of every edge is colored by all r colors.

Theorem 2 (Bukh, Loh, and Nivasch): It is possible to associate to the vertices of each such hypergraph H a set X of n points in \mathbb R^d so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is (r-1)!^d. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

For a star-like hypergraph where all blocks have a vertex in common we get the original Sierksma’s example. (Example (d) above.) White’s examples are obtained by considering such hypergraphs where there exists an edge A such that all edges have non empty intersection with A. (Examples (c), (d), and (e) above).

Rainbow colorings of our five examples 

Tverberg’s partitions for stretched points on the moment curve

It is natural to consider $n$ points on the moment curve x(t)=(t,t^2,\dots, t^d). It turns out that the set of Tverberg’s partitions for points on the moment curve depend on the precise location of the points. By stretched points on the moment curve I mean that  you take the points x(t_1), x(t_2), \dots x(t_n) where t_1 << t_2 << \dots t_n, namely $t_2$ is much much larger than t_1 and t_3 is much much much much larger than t_2, etc. etc. In this case, the configuration corresponds to a path H: you let the vertices be \{1,2,\dots,n\} and the edges are sets of the form \{(k-1)(r-1)+1, (k-1)(r-1)+2,\dots , k(r-1)+1\}. A stretched configuration of points on the moment curve has the property that every subset is also a stretched configuration of points on the moment curve.

The importance of Tverberg’s partitions for stretched points on the moment curve was realized by Barany and Por, by Bukh, Loh, and Nivasch, and by Perles and Sidron (See their paper Tverberg Partitions of Points on the Moment Curve), and perhaps by others as well.

Por’s universality result

Por’s universality theorem asserts that in terms of Tverberg partitions every large enough configuration of points in general position in R^d contains a configuration whose Tverberg partitions are those of a stretched configuration of n points on the moment curve! Por’s  universality result was conjectured independently by Bukh, Loh, and Nivasch, (and they gave some partial results) and by Por himself.

Theorem 3 (Por’s universality result, 2018): Every long enough sequence of points in \mathbb R^d in general position contains a subsequence  of length n whose Tverberg partitions are exactly the so called rainbow partitions.

Por actually proved an apparently stronger statement: We can find a subsequence Y so the conclusion holds not only for Y but also for every subsequence Z of Y

Staircase Convexity

The work of Bukh, Loh, and Nivasch relied on an important method of “staircase convexity”. An earlier 2001 application of the method (where it was introduced) was for lower bounds on weak epsilon nets by Bukh, Matousek, and Nivasch (Here are links to the paper, and to slides from a talk by Boris Bukh. See also this post and this one of the weak epsilon net problem.) Roughly the idea is this: consider a stretched grid where the sequence of coordinates are very very fast growing. When you choose configuration of points in such a grid, questions regarding their convex hulls translate to purely combinatorial problems.

Stairconvex sets explained by Boris Bukh

Erdos Szekeres in the plane and higher dimensions

The planar case

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that ES(n) is finite.

The finiteness of ES(n) can be stated as follows: Given a sequence of N points in general position in the plane x_1,x_2, \dots , x_N  there is a subsequence 1_i,x_2, \dots , x_n such that the line segments [x_i,x_k] and [x_j,x_\ell ] intersect. With this statement, the Erdős and Szekeres’ theorem can be seen as identifying a universal set of points in term of its Radon partitions (or equivalently in terms of its order type).

In high dimensions

In higher dimensions we can define ES_d(n) and replace “in convex position” by “in cyclic position”. The finiteness of ES_d(n) (with terrible bounds) follows easily from various Ramsey results. In a series of papers very good lower and upper bounds where obtained:  Imre BaranyJiri MatousekAttila Por: Curves in R^d intersecting every hyperplane at most d+1 timesMarek EliášJiří MatoušekEdgardo Roldán-PensadoZuzana Safernová: Lower bounds on geometric Ramsey functions; Marek Elias, Jiri Matousek: Higher-order Erdos–Szekeres theorems .

Por’s result

Por’s result can be seen as a far-reaching strengthening of the finiteness of ES_d(n).

Further Discussion:

High order order types?

Can you base a higher-order notion of “order types” on Tverberg partitions?

The order type of a sequence of n points affinely spanning R^d, is the described by the vector of signs (0, 1 or -1) of volume of simplices described by subsequences of length d+1. Equivalently the order type can be described by the minimal Radon partitions of the points.

  1. We can first ask if we can base a notion of higher order types on Tverberg’s partitions to r parts where r>2.
  2. Next we can ask for an associated notion of “higher order oriented matroids.” (Oriented matroids in the usual sense are abstract order types which coincide with Euclidean order types for every subsequence of d+3 points.)
  3. A natural question regarding these “higher order types is: If a sequence of points in strong general position is Tverberg-equivalent to stretched points on the moment curve, does it apply to all of its subsequences?

Another way to consider “higher” order types is to enlarge the family by to start with a family of points add to it all Radon points of minimal Radon’s partition and consider the order type of the new configuration. (This operation can be repeated r times.) See this paper of Michael Kallay on point sets which contain their Radon points.

Staircase convexity order types

Understanding order types of configuration of points on stretched grids of Bukh et al. is a very interesting problem. It is interesting to understand such configurations that are not in general position as well. (In particular, which matroids are supported on the stretched grid?) Of course, the method may well have many more applications.

Fantastically strong forms of Sierksma’s conjecture

Is the following true: For every sequence T of n=(r-1)(d+1)+1 points in R^d there is a Sierksma’s configuration S of $n$ points so that every Tverberg’s partition of  S is a Tverberg’s partition of T?

An even stronger version is:

Does every sequence T of (r-1)(d+1)+1 points in R^d there is a tree-like simple hypergraph so that all the rainbow coloring of H correspond to Tverberg partitions of the sequence? If true this will be a fantastically strong version of Sierksma’s conjecture.

Is the Erdős-Szekeres’ conjecture outrageous?

Erdős and Szekeres proved in 1935 that ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}, and in 1960, they showed that ES(n) \ge 2^{n-2}+1, and conjectured this to be optimal. Despite the efforts of many researchers, until recently no improvement in the order of magnitude has ever been made on the upper bound over  81 years. A  recent breakthrough result by Andrew Suk (Here are links to the paper, and to our post discussing the result) asserts that ES(n)=2^{n+o(n)}. Sometime ago I asked over MO a question on outrageous mathematical conjectures and perhaps the conjecture that  ES(n) = 2^{n-2}+1 on the nose is an example.

Original Abstracts

Continue reading

Posted in Combinatorics, Convexity | Tagged , , , , , , , | 4 Comments

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska: Universal optimality of the E8 and Leech lattices and interpolation formulas

Henry Cohn

A follow up paper on the tight bounds for sphere packings in eight and 24 dimensions. (Thanks, again, Steve, for letting me know.)

For the 2016 breakthroughs see this post, this post of John Baez, this article by Erica Klarreich on Quanta Magazine, and a Notices AMS article by  Henry Cohn   A conceptual breakthrough in sphere packing. See also, Henry Cohn’s 2010 paper Order and disorder in energy minimization, and Maryna Viazovska’s ICM 2018 videotaped lecture.

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska: Universal optimality of the E8 and Leech lattices and interpolation formulas

Abstract: We prove that the E_8 root lattice and the Leech lattice are universally optimal among point configurations in Euclidean spaces of dimensions 8 and 24, respectively. In other words, they minimize energy for every potential function that is a completely monotonic function of squared distance (for example, inverse power laws or Gaussians), which is a strong form of robustness not previously known for any configuration in more than one dimension. This theorem implies their recently shown optimality as sphere packings, and broadly generalizes it to allow for long-range interactions.

The proof uses sharp linear programming bounds for energy. To construct the optimal auxiliary functions used to attain these bounds, we prove a new interpolation theorem, which is of independent interest. It reconstructs a radial Schwartz function f from the values and radial derivatives of f and its Fourier transform \hat f at the radii √2π for integers n ≥ 1 in R^8 and n ≥ 2 in R^{24}. To prove this theorem, we construct an interpolation basis using integral transforms of quasimodular forms, generalizing Viazovska’s work on sphere packing and placing it in the context of a more conceptual theory.

Posted in Algebra and Number Theory, Combinatorics, Geometry | Tagged , , , , , , , | Leave a comment

Extremal Combinatorics V: POSETS

This is the remaining post V on partially ordered sets of my series on extremal combinatorics (I,II,III,IV,VI). 

We will talk here about POSETS – partially ordered sets. The study of order is very important in many areas of mathematics starting with the order relation on the integers and reals in algebra and in Euclidean geometry. The set of all subsets of a set can be partially ordered by inclusion and this is a very basic example of posets. While the study of order and posets is a separate area on its own, parts of it are very important in extremal combinatorics and we will give a little taste here.

Dear readers, please contribute your favorite result or problem on partially ordered sets (or Sorting) in the comment session.

A chain C \subset P in a POSET is a set of elements so that every two of them are comparable. An antichain $A \subset P$ is a set of elements so that every two distinct elemenאs in A are incomparable.  (Antichains are also called independent sets.) An immediate but important Lemma is:

The immediate lemma: The intersection of a chain A and an antichain C contains at most one element. Walla!

Dilworth’s theorem

Dilworth’s theorem (DT): Every finite partially ordered P set can be covered by a(P) chains.

(By the immediate lemma, at least a(P) chains are needed.)

Dual Dilworth theorem: Every partially ordered sets can be covered by c(P) antichains.

(By the immediate lemma, at least c(P) antichains are needed.)

The proof of the dual Dilworth theorem is easy. Note that the set A_1=MIN(P) of minimal elements of P is an antichain. Let A_k = MIN (P\backslash (A_1 \cup A_2 \cup \dots A_{k-1})). We need two easy observations. First, A_k is an antichain and second: If A_k \ne \emptyset then there is a chain with one element from A_i: 1 \le i\le k. Walla!

The proof of Dilworth’s theorem is by induction on $|P|$. For the induction step you first consider the case where every antichain of maximal size is either MAX(P) or MIN (P). In this case you consider a chain with one element in MAX(P) and one element in MIN (P) and delete these elements from P. For the resulting post Q, a(Q)=a(P)-1 and we can use the induction hypothesis.

Otherwise there is an antichain A of maximum size t=a(P) which is not MAX(P) or MIN(P).  Put A=\{a_1,a_2,\dots,a_t\}. Let P^+ be the set of elements in P which are larger or equal some element in A, and let P^- be the set of elements in P which are smaller or equal some element in A.

Now,

  1. P^+ \cup P^-=P. Otherwise we could add an element to A to form a larger antichain.
  2. P^+ \cap P^- = A. Otherwise, there will be two elements of A which are comparable.

So by the induction hypothesis P^+ can be covered by t chains C_1^+, C_2^+, \dots, C_t^+ and P^- can be covered by a(P$ chains C_1^-, C_2^-, \dots, C_t^-. Bu re-indexing we can assume that both C_i^+ and C_i^- contains a_i. It follows that a_i is the minimal element in $C_i^+$ and the maximal element in $C_i^-$ and hence C_i=:C_i^+ \cup C_i^- is a chain. The t chains C_1, C_2, \dots, C_t cover P. Sababa!

An important Corollary both from Dilworth’s theorem and its dual is that

a(P) c(P) \ge |P|.

Erdos-Szekeres theorem

The fundamental Erdos Szekeres theorem asserts that if n=ab+1 then every sequence a_1,a_2,\dots ,a_n of different real numbers contains a monotone increasing sequence of length a+1 or a monotone decreasing sequence of length b+1.

There are simple proofs. For example, associate to every k a pair (I_k,D_k) of integers where  I_k is the maximum length of the increasing subsequence starting with a_k and D_k is the maximum length of the deccreasing subsequence starting with a_k. The result follows from the easy observation that all these pairs are different.

Both Dilworth’ theorem and its easy dual imply easily (in fact we need only the important corollary) the Erdos Szekeres theorem when we define the following partial order: i < k if both i<k and a_i < a_k.

Looking at Sperner’s theorem again

Sperner’s theorem asserts that the maximal size of an antichain of subsets of an n elements set is {{n} \choose {[n/2]}}. By Dilworth’s theorem it follows that we can cover all sets by {{n} \choose {[n/2]}} chains (and, of course when we exhibit such a covering it reproves Sperner’s theorem). A symmetric saturated chain decomposition is a partition of P(n) (=all subsets of [n]) to saturated chains where each chain has, for some k, sets of sizes $k,k+1,\dots,d-k$. You can build such a decomposition inductively.

Start with a decomposition for n for each chain C_i create a new chain C'_i by adding the element n+1 to every set. And then move the top set in C'_i to C_iWalla!

This is the beginning of a very beautiful story related also to the Dedekind Problem about  number of antichains in P(n).

Curtis Greene and Danny Kleitman

The Greene-Kleitman theorem

Let a_k(P) be the maximum size of the union X of k antichains in a poset P. For every chain For every chain C we have |C \cap X| \le \min\{|C|,k\}. Therefore for a partition of P to chains C_1,C_2,\dots,C_t we   have \sum\min\{|C_i|,k\ge |X|. The Greene-Kleitman theorem asserts that there is always  a decomposition into chains with \sum\min\{|C_i|,k\}=a_k(P).

The perfect graph theorem.

What is the relation between the very easy dual Dilworth theorem and the harder Dilworth theorem? As it turns out there is a very general theorem, Lovasz’ perfect graph theorem, that shows that these two theorems are equivalent.

A graph G is perfect if for every induced subgraph H, the chromatic number equals the clique number. Lovasz’ theorem  (conjectured by Claude Berge) asserts that complements of perfect graphs are perfect. The perfectness of the comparability graph of a poset amounts to the dual Dilworth theorem, and for its complement it is the Dilworth theorem. Lovasz in fact proved that perfectness is equivalent to the relation $\latex \omega(H)\cdot \alpha (H) \ge |H|$ for every induced subgraph H. (For posets this is our important corollary above.)

Jeff Kahn and Jake Baron (see here on their 2016 asymptotic solution to Tusza’s conjecture), Mike Saks, and Nati Linial

Startling theorems on POSETS: Kahn-Saks,  Linial-Saks, Linial-Kahn, and Kahn-Saks

Here  are some beautiful and important theorems on posets. An order ideas I of a post is a set of elements so that if x in I and y < x then y \in I.

Theorem (Linial-Saks, 1985): In every poset P there is an element which is contained in more than δ and less than 1-δ order ideas of P.  (Paper)

Theorem (Kahn-Saks, 1984): For every Poset P which is not a chain there are two incomparable elements x,y such that the number of linear extensions of P for which x<y is between 3/11 and 8/11. (Paper)

A simpler proof was found in the late 80s by Kahn and Linial and by Karzanov and Khachiyan. It  is  based on the Brunn Minkowski theorem and gives a weaker constant 1/2e .

Theorem (Kahn-Saks, 1987): For every finite distributive lattice L the maximum antichain is of size o(|L|). (Paper)

Lattices are special types of posets with the property that for every set of elements (pairs \{x,y\} suffice in the finite case), there is a unique minimal elements above them all (denoted for pairs by x ∧ y) and a unique maximal element (denoted for pairs by x ∨ y) below them all.

A distributive lattice is a lattice that satisfies for every x, y and z, the relation

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Birkhoff’s representation theorem asserts that finite distributive lattices can be represented as order ideals of posets (ordered by inclusion).

 

 

Posted in Combinatorics | Tagged , , , , , , , , , | 5 Comments

Konstantin Tikhomirov: The Probability that a Bernoulli Matrix is Singular

Konstantin Tikhomirov

An old problem in combinatorial random matrix theory is cracked!

Singularity of random Bernoulli matrices by Konstantin Tikhomirov

Abstract: For each n, let M_n be an n×n random matrix with independent ±1 entries. We show that

P(M_n is singular}=(1/2+o_n(1))^n,

which settles an old problem. Some generalizations are considered.

János Komlós

Background and discussion

What is the probability s(n) that a random n by n matrix with \pm 1 entries is singular? Well, it can be singular if either two rows are identical, or if two columns are identical. This happens with probability

n(n-1)(1+0(1)) \cdot 2^{-n}.

Are there other more dominant reasons for singularity? Are most \pm 1 matrices nonsingular as n tends to infinity? The first results in this direction are by Janos Komlos who first proved in 1968 that s(n)=o(1) and later that s(n)=O(1/\sqrt n). A major breakthrough came in 1995 when  Kahn , Komlos, and Szemeredi proved that s(n) \le 0.999^n. Terry Tao and Van Vu improved in 2006 the constant to 0.939 and then to (3/4+o(1)) and the, now broken, world record from 2010 was (1/\sqrt 2)+o(1))^n  by Jean Bourgain, Van Vu and Philip Wood. Congratulations Konstantin!

If you want to tease the Gods of Mathematics you can try to prove that s(n) =n(n-1)(1+o(1)) \cdot 2^{-n}? and, as suggested in the Kahn-Komlós-Szemerédi paper,  even prove an expansion  s(n) = 2{{n} \choose {2}}(\frac{1}{2})^{n}+2{{n}\choose {4}} (\frac{3}{8})^n\cdots based on dependencies between k-tuples of rows and columns.

Let me mention that  Kevin Costello, Tao, and Vu, proved in 2005 that  random symmetric matrices are almost surely non-singular.  This is related to beautiful mathematics.  Tao and Vu also proved that the probability for vanishing of the permanent of a Bernoulli matrix is o(1). I am not sure what the proven behavior for permanents is and one may expect that vanishing of the permanent occurs in probability which is super exponentially small. (Perhaps C/\sqrt {n!}.)

Here are related posts on Tao’s blog What’s New. A post on Tao’s Milliman’s lecture on the additive combinatorics and random matrices; On the permanent of random Bernoulli matrix;

Determinants and the guaranteed cancellation phenomenon

The value of the determinant of a Bernoulli matrix is the sum of n! ±1 terms. So we can guess that the expected value will be around \sqrt {n!}, and with high probability it is near the expected value. There is something special about the determinant which we can call the Guaranteed Cancellation Phenomenon (GCP). The value of the determinant of a Bernoulli  matrix is at most n^{n/2} which is not that much larger than \sqrt {n!}. (GCP applies to matrices with real or complex variables with rows with prescribed  \ell_2 norms.)  Guaranteed cancellation is a very interesting mathematical phenomenon in various contexts. (For example, the prime number theorem and the Riemann hypothesis are about guaranteed cancellation.) The determinant itself is a polynomial of degree n with n^2 variables , and GCP for determinants was one of the starting points in a paper that I wrote with Leonard Schulman on quasi-random multilinear polynomials. (For other examples of GCP see also this MO question and various posts  on Mobius randomness.) Maybe it is time to ask on MathOverflow for a list of places were GCP  is expected or proven.)

Sperner, the Littlewood-Offord problem, and additive combinatorics

The determinant of a \pm 1 matrix is the signed sum of n minors. It follows from Sperner’s theorem that if m of these minors are non-zero then the probability that the sum vanishes is O(1/\sqrt m). This is the idea behind Komlos’ second proof. The relevant general question (backward Littlewood Offord  problem) which is of much independent interest is “Under which conditions on a sequence a_1,a_2, \dots, a_n we can guarantee that the probability that a signed sum of the sequence vanished (or has a small absolute value) is small.” The famous Erdos-Moser conjecture (solved on the nose by Stanley using the Hard Lefschetz theorem, sharpening a result by Sárközy and Szemerédi) asserts that if the elements of the sequence are distinct then the larger vanishing probability is attained by the sequence of integers between -[n/2] and +[n/2]. In this case (like for any arithmetic progression) the vanishing probability is n^{-3/2}.  Kahn, Komlos and Szemeredi relied on (and extended)  a theory by  Gábor Halász for guaranteeing that the vanishing probability is small (exponentially small) and, of course, much work is needed to prove that Halász-type conditions are satisfied.

I was excited by the 2005 solution for symmetric matrices also because it involved a quadratic version of Littlewood-Offord type results which are of much independent interest. I think that there are many interesting remaining open problems.

 

Posted in Combinatorics, Probability | Tagged | 1 Comment

Three Pictures

With Tolya (Anatoly) Vershik, Saint Petersburg, 2003

Peter Frankl and Voita (Vojtěch)  Rödl, NYC, summer 1986 (or 1987). This post mentions the Frankl-Rödl theorem.

Jeroen Zuiddam at IAS, a few days ago. (See this post)

We just moved to a new apartment, and I discovered in the process a few old pictures. Here are two pictures from the late 80s and the early 2000s (I may add a few more later) and a fresh new one from a recent short US visit.

Posted in Uncategorized | Tagged , , , | Leave a comment

Jean

Jean Bourgain and Joram Lindenstrauss.

I was very sad to hear that Jean Bourgain, among the greatest mathematicians of our time, and a dear friend, passed away.  I first met Jean about forty years ago and later we  became friends and collaborators.  In the 80s and 90s Jean used to visit Israel quite often and had close collaboration with the Banach space Israeli community, and with the Ergodic theory community,  and with the Harmonic analysis community, and the PDE community, and later also with the combinatorics, probability,  algebra, number theory,  and theoretical computer science communities.  I always admired his immense mathematical powers and his deep devotion to mathematics.

You can read about Jean Bourgain in Terry Tao’s beautiful obituary post.  I was also moved by Svetlana Jitomirskaya’s beautiful facebook post. Some of Jean’s contributions to combinatorics (which formed a small portion of his interests) are mentioned in several posts over my blog (and my lecture below). I will try to come back to these mathematical topics at a later post and here I post a few pictures of Jean over the years. Here is the moving IAS obituary notice. See also Ryan O’Donnell’s moving comment. And here is a MathOverflow question Jean Bourgains relatively lesser known significant contributions. (Added later:) Here is a beautiful tribute on GLL for Jean Bourgain and Michael Atiya. Let me also add a link to the moving obituary post of Terry Tao on Elias Stein.

 

My 2016 lecture “Questions for Jean Bourgain” about questions that I (and some colleagues) asked Jean Bourgain over the years, mainly in the areas of combinatorics and combinatorial aspects of convexity.

Continue reading

Posted in Algebra and Number Theory, Analysis, Combinatorics, Computer Science and Optimization, Convexity, Obituary | Tagged | 4 Comments

Amazing: Karim Adiprasito proved the g-conjecture for spheres!

Karim in his youth with a fan

Congratulations, Karim!

Update: Here is the link to the paper

From the arXive, Dec 26, 2018. (Link will be added tomorrow.)

COMBINATORIAL LEFSCHETZ THEOREMS BEYOND POSITIVITY

by Karim Adiprasito

Abstract: Consider a simplicial complex that allows for an embedding into \mathbb R^d. How many faces of dimension d/2 or higher can it have? How dense can they be?

This basic question goes back to Descartes. Using it and other fundamental combinatorial
problems, we will introduce a version of the Kähler package beyond positivity,
allowing us to prove the Lefschetz theorem for toric varieties even when the ample
cone is empty. A particular focus lies on replacing the Hodge-Riemann relations by a
non-degeneracy relation at torus-invariant subspaces, allowing us to state and prove a
generalization of the theorems of Hall and Laman in the setting of toric varieties. Of
the many applications, we highlight two main applications, one because it is the most
well-known, the other because it provided the most guiding light.

(1) We fully characterize the possible face numbers of simplicial spheres, resolving the
so called g-conjecture of McMullen in full generality and generalizing Stanley’s
earlier proof for simplicial polytopes.

(2) We prove that for a simplicial complex K that embeds into \mathbb R^{2d}, the number of d-dimensional simplices exceeds the number of (d − 1)-dimensional simplices by a factor of at most d + 2. This generalizes a result of Descartes, and resolves the Grünbaum-Kalai-Sarkaria conjecture.

_______

(GK:) A few further comments. Probably the g-conjecture for spheres is the single problem I knock my head against the most. It is great to see it settled and it is even greater to see it settled by my friend and colleague Karim Adiprasito.

To the three ingredients of the standard conjectures (See also the previous post), Poincare duality (PD), Hard Lefschetz (HL) and Hodge-Riemann (HR), Karim adds the Hall-Laman relations. Very roughly, the Hall-Laman relations  substitute (HR) and apply genericity (rather than definiteness) toward (HL).

(We still need a good acronym for Hall-Laman, maybe (AHL).)

One very nice feature of Karim’s proof is that vertex decomposable spheres play a special role in the path toward the proof. Those were introduced by Provan and Billera in the context of the Hirsch conjecture.

We have devoted plenty of posts to the g-conjecture for spheres, and mentioned it in even more posts.  For an introduction to the conjecture see Eran Nevo introductory post, and the post How the g-Conjecture Came About. There is also plenty left to be done beyond the g-conjecture.

Merry X-mas and Happy new year 2019 to all our readers.

Posted in Combinatorics, Updates | Tagged , | 9 Comments

ICM 2018 Rio (4): Huh; Balog & Morris; Wormald

 

This is my fourth report from ICM2018. (I plan one more.)  As I already mentioned, Combinatorics  was very nicely represented at ICM2018.  The combinatorics session itself was great, and there were quite a few other sessions and other lectures related to combinatorics. I also met quite a few combinatorialists. As I mentioned in my ICM 2010 post, one thing that I enjoyed was to unexpectedly meet some old friends and this also happened in Rio (maybe a little less compared to Hyderabad as I learned to expect the unexpected). I also had an irrational expectation to unexpectedly meet the same people that I met unexpectedly in India. It was a pleasure meeting  Tadeusz Januszkiewicz again   but I was irrationally disappointed not to bump again into Oriol Serra and Anna Llado whom I had met  by surprise in Hyderabad.

This post will be about the Monday afternoon Session in combinatorics. Let me mention that the ICM 2018 You Tube channel now contains high quality videos for plenary and invited talks (as well as discussion panels, public lectures, and various other activities). This is a valuable resource! Here is the combinatorics session playlist, and the CS session, and the probability and statistics session, and the plenary lectures, and the public lectures. Also, here is the most recent version of my ICM paper THREE PUZZLES ON MATHEMATICS, COMPUTATION, AND GAMES. Last minute corrections and comments are most welcome.

Monday’s afternoon combinatorics

The Monday afternoon combinatorics session featured three lectures that knocked my socks off. The talks were great and I was in a perfect position to enjoy them as I knew something about the problems and some related results  and yet each lecture surprised me.  The three talks were Combinatorial applications of the Hodge–Riemann relations by June Huh, The method of hypergraph containers by József Balogh & Robert Morris,  Asymptotic enumeration of graphs with given degree sequence by Nicholas Wormald. Bella Bollobas chaired the session and gave a very nice and thoughtful introduction to each of the four speakers.

 

June Huh, and the Lefschetz package in combinatorics

June Huh: The standard conjectures are both ubiquitous and fundamental

Combinatorial applications of the Hodge–Riemann relations

June Huh talked about a mysterious package of conjectures (PD), (HL) and (HR), referred to as the standard conjectures,  for certain algebras associated with geometric and combinatorial objects. PD stands for the Poincare Duality, and it asserts that certain vector spaces A_i and A_{d-i} are dual. HD stands for Hard Lefschetz and it asserts that certain linear maps \phi_k from A_k to A_k+1  have the property that their composition from A_i all the way to A_{d-i} is an injection. (HR) stands for Hodge Riemann relations. (PD) and (HD) imply that a certain bilinear form  is nondegenerate and (HR) is a stronger statement that this form is definite!

June started with some startling applications of the Hard-Lefschetz theorem in combinatorics pioneered by Stanley. He then mentioned a startling new application with Wang: Consider n points spanning a d-dimensional space.  Let w_i be the number of flats of dimension k spanned by the point.  Motzkin  conjectured in 1936 and proved over the reals that  w_1 \le w_d. The planar case follows from the classic Erdos deBruijn theorem. Hu and Wang used {HL} to prove w_i \le w_d-i, i \le [d/2] which was conjectured by Dowling and Wilson.

Next came applications of (HR), starting with Huh’s proof of the log concavity of coefficients of chromatic polynomials for graphs (Read conjecture ) and the far-reaching extension by Adiprasito-Huh-Kats to general matroids (Rota’s conjecture). We mentioned the Adiprasito-Huh-Katz solution of the Rota-Heron conjecture in the previous post and in this one.

Here is the link to the ICM paper by June Huh: Combinatorial applications of the Hodge-Riemann relations.

 

József Balogh and Rob Morris and the container method

The method of hypergraph containers

The container theorem for hypergraphs is one of the most important tools in extremal combinatorics with many applications also to random graphs and hypergraphs, additive combinatorics, discrete geometry, and more.

Rob Morris explained the container theorem for triangle-free graphs. It asserts that there is a collection \cal C of graphs on n vertices with the following three properties:

(1) Every graph in the collection contains o(n^3) triangles,

(2) The number of graphs in the collection is n^{C \cdot 3/2},

(3) Each triangle free graph is contained in a graph in the collection.

Rob explained the origins of this theorem, how it follows from a container theorem for 3-uniform hypergraphs,   and how the later extends to the very general and important container theorem for k-uniform hypergraphs that was achieved in 2012 independently by Saxton and Thomason (Here is the link to their paper), and by Balogh, Morris, and Samotij (Here is a link to their paper).

Jozsef Balogh described two consequences of the container theorem to additive combinatorics and to discrete geometry. Let me describe the result in discrete geometry by Balogh and Solymosi. The (4,3) problem ask for the size $\alpha (n)$ of the largest subset of points in general position (no three on a line) that can always be found in a planar configuration of n points with the property that no four points lie on a line. The container method is used to show (surprisingly!) that \alpha(n)=n^{5/6+o(1)} .

For a recent beautiful application to (p,q)-Helly type theorems see A new lower bound on Hadwiger-Debrunner numbers in the plane by Chaya Keller and Shakhar Smorodinsky.

Here is a link to the ICM survey paper: The method of hypergraph containers, by József Balogh, Robert Morris, and Wojciech Samotij

(In a previous post  Midrasha Mathematicae #18: In And Around Combinatorics, we gave links to a series of lectures Wojiech Samotij: Toward the hypergraph “container” theorem (4 lectures) Video 1, video 2 video 3 video 4.)

Nick Wormald and counting regular graphs.

Asymptotic enumeration of graphs with given degree sequence

How many k-regular graphs are there? This is a very central problem in combinatorics and Nick Wormald was quite interested in its solution ever since his Ph. D.  The talk describes the early history of the problem, the early works by Wormald and McKay from the 90s,  the recent breakthrough by Antia Liebenau and Nick Wormald,  the techniques involved in the old and new proofs and some related results.

A good place to start is with Read’s 1958 formula for the number g_3(n) of 3-regular graphs with n labelled vertices

g_3(n) \sim (3n)! e^{-2}/(3n/2)!288^{n/2}.

Following an important model of Bollobas for creating regular graphs, general formulas were developed for low degrees, By McKay, McKay and Wormald, and others that depend on the probability of a random graph in Bollobas’ model to be simple. (See pictures below). Some results were proven also for the high degree regime and McKay and Wormald gave in 1990 and 1997 unified conjectural formulas for the number of d-regular graphs for a wide range of parameters. Moreover these conjectures extend to a large range of vectors of degree sequences.

In 2017 Anita Liebenau and Nick Wormald proved all these conjectures!!! (Here is a link to the paper.)

The formula for the behavior of the number of d-regular graphs with n vertices is remarkably elegant

e^{1/4}\sqrt{2}d^d(n-1-d)^{n-1-d}(n-1)^{-(n-1)}{{n-1} \choose {d}}^n.

The full result is very general, and the method extends further in various directions.

Here is the link to paper: Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, by Anita Liebenau and Nick Wormald.

A bit psychedelic pictures

    

With Nick Wormald and Yoshi Kohayakawa just before my lecture.

Some important pictures from the Session

Bela Bollobas

Bela Bollobas served as the session chair

Nick Wormald on enumeration of regular graphs

Read’s formula and Bollobas model.

Formulas by McKay and McKay-Wormald (above and below)

General conjectures (above and below)

The Theorem by Liebenau and Wormald (above and below)

 

Balogh and Morris on containers

The Container theorem for triangle-free graphs

The hypergraph container theorem for 3-uniform hypergraphs

The hypergraph container theorem in full generality.

 

An application for the number of subsets of integers without k-term arithmetic progressions.

What was known and expected on the (4,3) problem (above) and the new breakthrough (below)

 

 

Applications of the container method

June Huh on the standard conjectures

Five seemingly unrelated mathematical objects

 

Poincare duality (PD), Hard Lefschetz (HL), and Hodge Riemann (HR).

A 1964 letter from Serre to Grothendieck on young Bombieri

The algebraic setting for the standard conjectures. 

Five cases were the standard conjectures are known and the original open case.

Posted in Combinatorics, ICM2018 | Tagged , , , , , | 2 Comments

Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!

 

Milena+Umesh
Milena Mihail and Umesh Vazirani

I thank Nati Linial, Dan Spielman and Karim Adiprasito for sharing the news with me.

The Mihail-Vazirani conjecture for matroids and Feder-Mihail’s theorem

Consider a collection X of n vectors. A basis is a subset of X of linearly independent vectors that span the subspace spanned by X.  We can define a graph whose vertices are all bases and two bases are adjacent if their symmetric difference has two elements. Mihail and Vazirani conjectured that for every set Y of vertices in this graph the number of edges between Y to its complement \bar Y is at least \min (|Y| |,\bar Y|).

If X consists of the elements of the standard basis in \mathbb R^d and their negatives then the graph we obtain is the graph of the discrete n dimensional discrete cube and the assertion of the Mihail-Vazirani conjecture is well known.

The Mihail-Vazirani conjecture was formulated (and has now been proved) for arbitrary matroids. Think about a matroid as a collection K of subsets (the independent sets of the matroid) of some ground set X that closed under taking subsets (hence a simplicial complex) with the following property: For every Y \subset X, the induced simplicial complex on Y denoted by K(Y)  is pure. In other words, for every Y \subset X, all maximal independent subsets of Y have the same cardinality.

In a pioneering 1992 paper Tomás Feder and Milena Mihail proved the conjecture for balanced matroids.

Mihail and Vazirani conjecture for 0-1 polytopes.

An even more general conjecture by Mihail and Vazirani is still open. It asserts that for every 0-1 polytope, for every set Y of vertices, the number of edges between Y to its complement \bar Y is at least \min (|Y|, |\bar Y|).

The new breakthrough

Here is the link to the paper.

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid by Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant

Let me mention another paper by a subset of the authors on related questions, another paper by Brändén and Huh, who independently proved the strong log-concavity of several of the polynomials appeared in the ALOV  paper, and are be several forthcoming papers by these two groups.

Here is the abstract: We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if X is a pure simplicial complex with positive weights on its maximal faces, we can associate with X a multiaffine homogeneous polynomial p_X such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of p_X.

Spectral negative dependence and Hodge-Riemann

A key paragraph regarding the method is the following:

“Our approach has a close connection to the original plan of Feder and Mihail (1992) who used the negative correlation property of balanced matroids to show that the bases exchange walk mixes rapidly. Unfortunately, most interesting matroids do not satisfy negative correlation. But it was observed [AKH18; HW16; AOV18] that all matroids satisfy a spectral negative dependence property.” AKH18 (a typo, it should be AHK18) is the solution for the Rota-Heron conjecture by Adiprasito, Huh and Katz that relies on the Hodge-Riemann property for matroids that we mentioned in this post. (I still feel in debt for a more detailed blog post about Adiprasito, Huh and Katz’ breakthrough!).”

I think that high dimensional expanders and random walks on them also plays a role in the new development.

Update: Related very recent papers

Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids

Authors: Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant

Log-Concave Polynomials III: Mason’s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids

Authors: Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant

Hodge-Riemann relations for Potts model partition functions

Authors: Petter Brändén, June Huh

Correlation bounds for fields and matroids

Authors: June Huh, Benjamin Schröter, Botong Wang

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , , , , , | 7 Comments