Happy Birthday Richard Stanley!

Richard_Stanley

This week we are celebrating in Cambridge MA , and elsewhere in the world, Richard Stanley’s birthday.  For the last forty years, Richard has been one of the very few leading mathematicians in the area of combinatorics, and he found deep, profound, and fruitful links between combinatorics and other areas of mathematics.  His works enriched and
influenced combinatorics as well as other areas of mathematics, and, in my opinion,
combinatorics matured greatly as a mathematical discipline thanks to his work.

Trivia Quiz

Correct or incorrect?

(1) Richard drove cross-country at least 8 times

(2) In his youth, at a wild party, Richard Stanley found  a proof of FLT consisting of a few mathematical symbols.

(3) Richard  jumped at least once from an airplane

(4) Richard is actively interested in the study of consciousness

(5) Richard found a mathematical way to divide by zero

 

Seven Early Papers by Richard Stanley That You Must Read.

cobcom

Richard’s Green book: Combinatorics and Commutative Algebra

Combinatorics and Commutative Algebra

(1) R. P. Stanley, The upper bound conjecture and Cohen-Macaulay rings.
Studies in Appl. Math. 54 (1975), no. 2, 135–142.

The two seminal papers (1) and (3) (below) showed remarkable and unexpected applications of commutative algebra to combinatorics. In each of these papers a central
conjecture in combinatorics was solved in a completely unexpected way which was the basis for a later remarkable theory. Paper (1) is the starting point for the interrelation between commutative algebra and combinatorics of simplicial complexes and their
topology. In this work Richard Stanley proved the Motzkin-Klee upper bound conjecture for triangulations of spheres. This conjecture asserts that the maximum number
of k-faces for a triangulation of a (d-1)-dimensional sphere with n vertices is attained by the boundary complex of the cyclic d-dimensional polytope with
n vertices. Peter McMullen proved this conjecture for simplicial polytopes and Richard Stanley proved it for arbitrary triangulations of spheres. The key point was that a certain ring (the Stanley-Reisner ring) associated with a simplicial polytope has the Cohen-Macaulay property.

The connection between combinatorics and commutative algebra is
far reaching, and in subsequent works combinatorial problems led to
developments in commutative algebra and techniques from the two areas were
combined.  A more recent important paper by Richard on applications of commutative algebra for the study of face numbers is: R. P. Stanley, Subdivisions and local h-vectors. J. Amer. Math. Soc. 5 (1992), no. 4, 805–851.

And here is, a few weeks old important development in this theory: Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski sums, by Karim A. Adiprasito and Raman Sanyal.

The Cohen-Macaulay property, magic squares and lattice points in polytopes

(2) R. P. Stanley, Magic labelings of graphs, symmetric magic squares,
systems of parameters, and Cohen-Macaulay rings. Duke Math. J. 43 (1976),
no. 3, 511–531.

This paper starts with a theorem about enumeration of certain magic squares. Solving a long-standing open problem, Stanley proved that the generating function for the
number of k by k integer matrices (k– fixed) with nonnegative entries and row sums and column sums equal to nis rational. This is the starting
point of a deep algebraic theory of integral points in polyhedra.

Enters the Hard-Lefshetz Theorem: McMullen’s g-conjecture

(3) R. P. Stanley, The number of faces of a simplicial convex polytope. Adv. in Math. 35 (1980), no. 3, 236–238.

The g-conjecture proposes a complete characterization of face numbers of d-dimensional polytopes. One linear equality that holds among face numbers is, of course, the Euler-Poincaré relation. This relation implies additional [d/2] equalities called the Dehn-Sommerville relations. Peter McMullen proposed an additional system of linear and nonlinear inequalities as a complete characterization of face numbers of polytopes. The sufficiency part of this conjecture was proved by Billera and Lee. Richard Stanley’s brilliant proof for McMullen’s inequalities that established the g-conjecture was based on the Hard Lefschetz Theorem from algebraic topology. Starting from a simplicial polytope P (with rational vertices) we associate to it a toric variety T(P). It turned out that the cohomology ring of this variety is closely related to the Stanley-Reisner ring mentioned above. The Hard Lefschetz Theorem implies an algebraic property of the Stanley-Reisner ring from which McMullen inequalities can be deduced by direct combinatorial reasoning. Richard found a number of other combinatorial applications of the Hard Lefschetz theorem (including the solution of the Erdos-Moser conjecture).

Here is the abstract of Lou Billera’s lecture

LOUIS BILLERA (CORNELL)

Even more intriguing, if rather less plausible…

The title is how Peter McMullen described his own conjectured characterization of the f-vectors of simplicial polytopes in his 1971 lecture notes on the upper bound conjecture written with Geoffrey Shephard. Yet by the end of that decade, the so-called g-conjecture would become the g-theorem, and algebraic combinatorics (as practiced at MIT) would have attracted the attention of mainstream mathematics, almost entirely due to the startling proof given by Richard Stanley.

I will briefly describe some of the events leading to this proof and some of its still developing consequences.

Enumeration

Enumeration is Richard’s true mathematical love.

 

ec1

Richard’s monumental books EC1 and EC2 (The picture is of EC1 and a young fan)

(4) A baker’s dozen of conjectures concerning plane partitions, in Combinatoire Énumérative (G. Labelle and P. Leroux, eds.), Lecture Notes in Math., no. 1234, Springer-Verlag, Berlin/Heidelberg/New York, 1986, pp. 285-293.

13 beautiful conjectures on counting plane partitions with various forms of symmetry.

(5) Generating functions, in Studies in Combinatorics (G.-C. Rota, ed.), Mathematical Association of America, 1978, pp 100-141.

For me this was the best introduction to generating functions, clear and inspiring. The entire MAA 1978 Rota’s blue little volume on combinatorics is great. Buy it!

Posets everywhere

(5) Supersolvable latticesAlgebra Universalis 2 (1972), 197-217.

This paper provides a profound link between group theory and the study of
partially ordered sets. It can be seen as a starting point of Stanley’s own work on the Cohen-Macaulay property and it had much influence on later works on combinatorial properties of lattices of subgroups by Quillen and many others, and also on the study of POSETS (=partially ordered sets) arising from arrangements of hyperplanes. The algebraic notion of supersolvable groups is translated to an important combinatorial notion for partially ordered sets. (There is a more detailed paper which I could not find online: R. P. Stanley, Supersolvable semimodular lattices. Mobius algebras (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1971), pp. 80–142. Univ. Waterloo, Waterloo, Ont., 1971.)

 Combinatorics and representation theory

(6) On the number of reduced decompositions of elements of Coxeter groupsEuropean J. Combinatorics 5 (1984), 359-372.

This paper gives an important result proved using representation theory. It is one of
many results by Stanley on connections between enumerative combinatorics,
representation theory, and invariant theory. Again, this paper represents an exciting area of research about the connection of enumerative combinatorics and representation theory that I am less familiar with.  A very inspiring survey paper is: Invariants of finite groups and their applications to combinatoricsBull. Amer. Math. Soc. (new series) 1 (1979), 475-511.

Here are abstracts of two lectures from the meeting on some recent developments in combinatorial representation theory and symmetric functions.

 

GRETA PANOVA (UCLA)

The Kronecker coefficients: an unexpected journey

Kronecker coefficients live at the intersection of representation theory, algebraic combinatorics and, most recently, complexity theory. They count the multiplicities of irreducible representations in the tensor product of two other irreducible representations of the symmetric group. While their journey started 75 years ago, they still haven’t found their explicit positive combinatorial formula, and present a major open problem in algebraic combinatorics. Recently, they were given a new role in the field of Geometric Complexity Theory, initiated by Mulmuley and Sohoni, where certain conjectures on the complexity of computing and deciding positivity of Kronecker coefficients are part of a program to prove the “”P vs NP”” problem.

We will take the Kronecker coefficients to asymptotics land and bound them. As an unexpected consequence of this trip, we find bounds for the difference of consecutive coefficients in the q-binomial coefficients (as polynomial in q), generalizing Sylvester’s unimodality theorem and connecting with results of Richard Stanley.
Joint work with Igor Pak.

THOMAS LAM (U MICHIGAN)

Truncations of Stanley symmetric functions and amplituhedron cells

Stanley symmetric functions were invented (by Stanley) with applications to the enumeration of reduced words in the symmetric group in mind. Recently, the “amplituhedron” was introduced in the study of scattering amplitudes in N=4 super Yang Mills. I will talk about a formula for the cohomology class of a (tree) amplituhedron variety as the truncation of an affine Stanley symmetric function.

Two combinatorial applications of the Aleksandrov-Fenchel inequalities;

(7)  Two combinatorial applications of the Aleksandrov-Fenchel inequalitiesJ. Combinatorial Theory (A) 31 (1981), 56-65.

In this amazing paper Stanley used inequalities of classical convexity
to settle an important conjecture on probability of events in partially
ordered sets. A special case of the conjecture was settled earlier by Ron
Graham using the FKG inequality. The profound relation between classical
convexity inequalities, combinatorial structures, polytopes, and
probability theory was further studied by many authors including Stanley
himself and there is much more to be done.

I see that I ran out of my seven designated slots. Certainly you should read Richard’s combinatorial constructions of polytopes, like Two poset polytopesDiscrete Comput. Geom. 1 (1986), 9-23, and his papers on arrangements. Let me mention a more recent paper of Stanley in this general area:   A polytope related to empirical distributions, plane trees, parking functions, and the associahedron (with J. Pitman)Discrete Comput. Geom.27 (2002), 603-634.

More

(Mostly from RS’s homepage.)

Chess and Mathematics

(12 page  PDF file) An excerpt (version of 1 November 1999) from a book Richard is writing with Noam Elkies.

An unusual method for proving the Riemann hypothesis.

Professor Eubanks in Zetaland

Richard Stanley’s Mathoverflow question on MAGIC

Magic trick based on deep mathematics

 

Richard the Catalan

(From RS’s homepage)

Excerpt (27 page PDF file) from EC2  on problems related to Catalan numbers (including 66 combinatorial interpretations of these numbers).

Solutions to Catalan number problems from the previous link (23 page PDF file).

Catalan addendum (Postscript or PDF) (version of 25 May 2013; 96 pages). An addendum of new problems (and solutions) related to Catalan numbers. Current number of combinatorial interpretations of Cn207.

The material on Catalan numbers is being collected into a monograph, to be published by Cambridge University Press in late 2014 or early 2015.

 

bgs

Influence, Threshold, and Noise

 

poster4.1

My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps I can practice the lecture on you, my readers, not just with the slides (here they are) but also roughly what I plan to say, some additional info, and some pedagogical hesitations. Of course, remarks can be very helpful.

I can also briefly report that there are plenty of exciting things happening around that I would love to report about – hopefully later in my travel-free summer. One more thing: while chatting with Yuval Rabani and Daniel Spielman I realized that there are various exciting things happening in algorithms (and not reported so much in blogs). Much progress has been made on basic questions: TSP, Bin Packing, flows & bipartite matching, market equilibria, and k-servers, to mention a few, and also new directions and methods. I am happy to announce that Yuval kindly agreed to write here an algorithmic column from time to time, and Daniel is considering contributing a guest post as well.

The second AMS-IMU meeting

Since the early 70s, I have been a devoted participants in our annual meetings of the Israeli Mathematical Union (IMU), and this year we will have the second joint meeting with the American Mathematical Society (AMS). Here is the program. There are many exciting lectures. Let me mention that Eran Nevo, this year Erdős’ prize winner, will give a lecture about the g-conjecture. Congratulations, Eran! Among the 22 exciting special sessions there are a few related to combinatorics, and even one organized by me on Wednsday and Thursday.

Combinatorics
Contact person: Gil Kalai, gil.kalai@gmail.com
TAU, Dan David building, Room 103
 Wed, 10:50-11:30 Van H. Vu (Yale University) Real roots of random polynomials (abstract)
Wed, 11:40-12:20 Oriol Serra (Universitat Politecnica de Catalunya, Barcelona)  Arithmetic Removal Lemmas (abstract)
 Wed, 12:30-13:10 Tali Kaufman (Bar-Ilan University)  Bounded degree high dimensional expanders (abstract)
 Wed, 16:00-16:40 Rom Pinchasi (Technion)  On the union of arithmetic progressions (abstract)
Wed, 16:50-17:30  Isabella Novik (University of Washington, Seattle) Face numbers of balanced spheres, manifolds, and pseudomanifolds (abstract)
 Wed, 17:40-18:20 Edward Scheinerman (Johns Hopkins University, Baltimore) On Vertex, Edge, and Vertex-Edge Random Graphs (abstract)
 Thu, 9:20-10:00 Yael Tauman Kalai (MSR, New England) The Evolution of Proofs in Computer Science (abstract)
 Thu, 10:10-10:50  Irit Dinur (Weitzman Institute)  Lifting locally consistent solutions to global solutions (abstract)
 Thu, 11:00-11:40 Benny Sudakov (ETH, Zurich) The minimum number of nonnegative edges in hypergraphs (abstract)

 

And now for my own lecture.

Influence, Threshold, and Noise:

Continue reading

Levon Khachatrian’s Memorial Conference in Yerevan

lk

Workshop announcement

Levon 7

The National Academy of Sciences of Armenia together American University of Armenia are organizing a memorial workshop on extremal combinatorics, cryptography and coding theory dedicated to the 60th anniversary of the mathematician Levon Khachatrian.  Professor Khachatrian started his academic career at the Institute of Informatics and Automation of National Academy of Sciences. From 1991 until the end of his short life in 2002 he spent at University of Bielefeld, Germany where Khachatrian’s talent flourished working with Professor Rudolf Ahlswede. Professor Khachatrian’s most remarkable results include solutions of problems dating back over 40 years in extremal combinatorics posed by the world famous mathematician Paul Erdos.  These problems had attracted the attention of many top people in combinatorics and number theory who were unsuccessfully in their attempts to solve them. At the workshop in Yerevan we look forward to the participation of invited speakers (1 hour presentations), researchers familiar with Khachatrian’s work, as well as contributed papers in all areas of extremal combinatorics, cryptography and coding theory.

The American University of Armenia (www.aua.am) is proud to host the workshop.

Workshop chair:  Gurgen Khachatrian

For any inquiries please send E-mail to: gurgenkh@aua.am

Levon 5

Amazing: Peter Keevash Constructed General Steiner Systems and Designs

KONICA MINOLTA DIGITAL CAMERA

Here is one of the central and oldest problems in combinatorics:

Problem: Can you find a collection S of q-subsets from an n-element set X set so that every r-subset of X is included in precisely λ sets in the collection?

A collection S  of this kind are called a design of parameters (n,q,r, λ),  a special interest is the case  λ=1, and in this case S is called a Steiner system.

For such an S to exist n should be admissible namely {{q-i} \choose {r-i}} should divide \lambda {{n-i} \choose {r-i}} for every 1 \le i \le r-1.

There are only few examples of designs when r>2. It was even boldly conjectured that for every q r and λ if n is sufficiently large than a design of parameters  (n,q,r, λ) exists but the known constructions came very very far from this.   … until last week. Last week, Peter Keevash gave a twenty minute talk at Oberwolfach where he announced the proof of the bold existence conjecture. Today his preprint the existence of designs, have become available on the arxive.

Brief history

The existence of designs and Steiner systems is one of the oldest and most important problems in combinatorics.

1837-1853 – The existence of designs and Steiner systems was asked by Plücker(1835), Kirkman (1846) and Steiner (1853).

1972-1975 – For r=2 which was of special interests, Rick Wilson proved their existence for large enough admissible values of n.

1985 -Rödl proved the existence of approximate objects (the property holds for (1-o(1)) r-subsets of X) , thus answering a conjecture by Erdös and Hanani.

1987  – Teirlink proved their existence for infinitely  many values of n when r and q are arbitrary and  λ is a certain large number depending on q and r but not on n. (His construction also does not have repeated blocks.)

2014 – Keevash’s  proved the existence of Steiner systems for all but finitely many admissible  values of n for every q and r. He uses a new method referred to as Randomised Algebraic Constructions.

Update: Just 2 weeks before Peter Keevash announced his result I mentioned the problem in my lecture in “Natifest” in a segment of the lecture devoted to the analysis of Nati’s dreams. 35:38-37:09.

Update: Some other blog post on this achievement: Van Vu Jordan Ellenberg, The aperiodical . A related post from Cameron’s blog Subsets and partitions.

Update: Danny Calegary pointed out a bird-eye similarity between Keevash’s strategy and the strategy of the  recent Kahn-Markovic proof of the Ehrenpreis conjecture http://arxiv.org/abs/1101.1330 , a strategy used again by Danny and Alden Walker to show that random groups contain fundamental groups of closed surfaces http://arxiv.org/abs/1304.2188 .

Many triangulated three-spheres!

The news

Eran Nevo and Stedman Wilson have constructed \exp (K n^2) triangulations with n vertices of the 3-dimensional sphere! This settled an old problem which stood open for several decades. Here is a link to their paper How many n-vertex triangulations does the 3 -sphere have?

Quick remarks:

1) Since the number of facets in an n-vertex triangulation of a 3-sphere is at most quadratic in n, an upper bound for the number of triangulations of the 3-sphere with n vertices is \exp(n^2 \log n). For certain classes of triangulations, Dey removed in 1992  the logarithmic factor in the exponent for the upper bound.

2) Goodman and Pollack showed in 1986 that the number of simplicial 4-polytopes with n vertices is much much smaller \exp (O(n\log n)). This upper bound applies to simplicial polytopes of every dimension d, and Alon extended it to general polytopes.

3) Before the new paper the world record was the 2004 lower bound by Pfeifle and Ziegler – \exp (Kn^{5/4}).

4) In 1988 I constructed \exp (K n^{[d/2]}) triangulations of the d-spheres with n vertices.  The new construction gives hope to improve it in any odd dimension by replacing [d/2] by [(d+1)/2] (which match up to logn the exponent in the upper bound). [Update (Dec 19) : this has now been achieved by Paco Santos (based on a different construction) and Nevo and Wilson (based on extensions of their 3-D constructions). More detailed to come.]

NatiFest is Coming

Nati Poster_Final

The conference Poster as designed by Rotem Linial

A conference celebrating Nati Linial’s 60th birthday will take place in Jerusalem December 16-18. Here is the conference’s web-page. To celebrate the event, I will reblog my very early 2008 post “Nati’s influence” which was also the title of my lecture in the workshop celebrating Nati’s 50th birthday.

Nati’s Influence

When do we say that one event causes another? Causality is a topic of great interest in statistics, physics, philosophy, law, economics, and many other places. Now, if causality is not complicated enough, we can ask what is the influence one event has on another one.  Michael Ben-Or and Nati Linial wrote a paper in 1985 where they studied the notion of influence in the context of collective coin flipping. The title of the post refers also to Nati’s influence on my work since he got me and Jeff Kahn interested in a conjecture from this paper.

Influence

The word “influence” (dating back, according to Merriam-Webster dictionary, to the 14th century) is close to the word “fluid”.  The original definition of influence is: “an ethereal fluid held to flow from the stars and to affect the actions of humans.” The modern meaning (according to Wictionary) is: “The power to affect, control or manipulate something or someone.”

Ben-Or and Linial’s definition of influence

Collective coin flipping refers to a situation where n processors or agents wish to agree on a common random bit. Ben-Or and Linial considered very general protocols to reach a single random bit, and also studied the simple case where the collective random bit is described by a Boolean function f(x_1,x_2,\dots,x_n) of n bits, one contributed by every agent. If all agents act appropriately the collective bit will be ‘1’ with probability 1/2. The purpose of collective coin flipping is to create a random bit R which is immune as much as possible against attempts of one or more agents to bias it towards ‘1’ or ‘0’. Continue reading

Analysis of Boolean Functions – Week 7

Lecture 11

The Cap Set problem

We presented Meshulam’s  bound 3^n/n for the maximum number of elements in a subset A of (\mathbb{Z}/3Z)^n not containing a triple x,y,x of distinct elements whose sum is 0.

The theorem is analogous to Roth’s theorem for 3-term arithmetic progressions and, in fact, it is a sort of purified analog to Roth’s proof, as some difficulties over the integers are not presented here.  There are two ingredients in the proof: One can be referred to as the “Hardy-Littlewood circle method” and the other is the “density increasing” argument.

We first talked about density-increasing method and showed how KKL’s theorem for influence of sets follows from KKL’s theorem for the maximum individual influence. I mentioned what is known about influence of large sets and what is still open. (I will devote to this topic a separate post.)

Then we went over Meshulam’s proof in full details. A good place to see a detailed sketch of the proof is in this post  on Gowers’ blog.

Let me copy Tim’s sketch over here:

Sketch of proof (from Gowers’s blog).

Next, here is a brief sketch of the Roth/Meshulam argument. I am giving it not so much for the benefit of people who have never seen it before, but because I shall need to refer to it. Recall that the Fourier transform of a function f:\mathbb{F}_3^n\to\mathbb{C} is defined by the formula

\hat{f}(r)=\mathbb{E}f(x)\omega^{r.x},

where \mathbb{E} is short for 3^{-n}\sum, \omega stands for \exp(2\pi i/3) and r.x is short for \sum_ir_ix_i. Now

\mathbb{E}_{x+y+z=0}f(x)f(y)f(z)=f*f*f(0).

(Here \mathbb{E} stands for 3^{-2n}\sum, since there are 3^{2n} solutions of x+y+z=0.) By the convolution identity and the inversion formula, this is equal to \sum_r\hat{f}(r)^3.

Now let f be the characteristic function of a subset A\subset\mathbb{F}_3^n of density \delta. Then \hat{f}(0)=\delta. Therefore, if A contains no solutions of x+y+z=0 (apart from degenerate ones — I’ll ignore that slight qualification for the purposes of this sketch as it makes the argument slightly less neat without affecting its substance) we may deduce that

\sum_{r\ne 0}|\hat{f}(r)|^3\geq\delta^3.

Now Parseval’s identity tells us that

\sum_r|\hat{f}(r)|^2=\mathbb{E}_x|f(x)|^2=\delta,

from which it follows that \max_{r\ne 0}|\hat{f}(r)|\geq\delta^2.

Recall that \hat{f}(r)=\mathbb{E}_xf(x)\omega^{r.x}. The function x\mapsto\omega^{r.x} is constant on each of the three hyperplanes r.x=b (here I interpret r.x as an element of \mathbb{F}_3). From this it is easy to show that there is a hyperplane H such that \mathbb{E}_{x\in H}f(x)\geq\delta+c\delta^2 for some absolute constant c. (If you can’t be bothered to do the calculation, the basic point to take away is that if \hat{f}(r)\geq\alpha then there is a hyperplane perpendicular to r on which A has density at least \delta+c\alpha, where c is an absolute constant. The converse holds too, though you recover the original bound for the Fourier coefficient only up to an absolute constant, so non-trivial Fourier coefficients and density increases on hyperplanes are essentially the same thing in this context.)

Thus, if A contains no arithmetic progression of length 3, there is a hyperplane inside which the density of A is at least \delta+c\delta^2. If we iterate this argument 1/c\delta times, then we can double the (relative) density of A. If we iterate it another 1/2c\delta times, we can double it again, and so on. The number of iterations is at most 2/c\delta, so by that time there must be an arithmetic progression of length 3. This tells us that we need lose only 2/c\delta dimensions, so for the argument to work we need n\geq 2/c\delta, or equivalently \delta\geq C/n.

 

Lecture 12

Error-Correcting Codes

We discussed error-correcting codes. A binary code C is simply a subset of the discrete n-dimensional cube. This is a familiar object but in coding theory we asked different questions about it. A code is linear if it forms a vector space over (Z/2Z)^n. The minimal distance of a code is the minimum Hamming distance between two distinct elements, and in the case of linear codes it is simply the minimum weight of a non-zero element of the codes. We mentioned codes over larger alphabets, spherical codes and even codes in more general metric spaces. Error-correcting codes are among the most glorious applications of mathematics and their theory is related to many topics in pure mathematics and theoretical computer science.

1) An extremal problem for codes: What is the maximum size of a binary code of length n with minimal distance d. We mentioned the volume (or Hamming) upper bound and the Gilbert-Varshamov lower bound. We concentrated on the case of codes of positive rate.

2) Examples of codes: We mentioned the Hamming code and the Hadamard code and considered some of their basic properties. Then we mentioned the long code which is very important in the study of Hardness of computation.

3) Linearity testing. Linearity testing is closely related to the Hadamard code. We described Blum-Luby-Rubinfeld linearity test and analyzed it. This is very similar to the Fourier theoretic formula and argument we saw last time for the cap problem.

We start to describe Delsartes linear Programming method to be continued next week.

Analysis of Boolean Functions week 5 and 6

Lecture 7

First passage percolation

1)  Models of percolation.

We talked about percolation introduced by Broadbent and Hammersley in 1957. The basic model is a model of random subgraphs of a grid in n-dimensional space. (Other graphs were considered later as well.) Here, a grid is a graph whose vertices have integers coordinates and where two vertices are adjacent if their Euclidean distance is one. Every edge of the grid-graph is taken (or is “open” in the percolation jargon) with the same probability p, independently. We mentioned some basic questions – is there an infinite component? How many infinite components are there? What is the probability that the origin belongs to such an infinite component as a function of p?

I mentioned two results: The first  is Kesten’s celebrated result that the critical probability for planar percolation is 1/2. The other by Burton and Keane is that in very general situations almost surely there is a unique infinite component or none at all. This was a good point to mention a famous conjecture- The dying percolation conjecture (especially in dimension 3) which asserts that at the critical probability there is no infinite component.

We will come back to this basic model of percolation later in the course, but for now we moved to a related more recent model.

2) First passage percolation

We talked about first passage percolation introduced by Hammersley and Welsh in 1965. Again we consider the infinite graph of a grid and this time we let the length of every edge be 1 with probability 1/2 and 2 with probability 1/2 (independently). These weights describe a random metric on this infinite graph that we wish to understand. We consider two vertices (0,0) and (v,0) (for high dimension the second entry can account for a (d-1) dimensional vectors, but we can restrict our attention to d=2) and we let D(x) be the distance between these two vectors. We explained how D is an integer values function on a discrete cube with Liphshitz constant 1. The question we want to address is : What is the variance of D?

Why do we study the variance, when we do not know exactly the expectation, you may ask? (I remember Lerry Shepp asking this when I talked about it at Bell Labs in the early 90s.) One answer is that we know that the expectation of D is linear, and for the variance we do not know how it behaves. Second, we expect that telling the expectation precisely will depend on the model while the way the variance grows and perhaps D‘s limiting distribution, will be universal (say, for dimension 2). And third, we do not give up on the expectation as well. 

Here is what we showed:

1) From the inequality var(D)=\sum_{S\ne \emptyset}\hat D^2(S)\le\sum \hat D^2(S)|S| we derived Kesten’s bound var (D) =O(v).

2) We considered the value s so that \mu(D>s)=t, and showed by the basic inequality above that the variance of D conditioned on D>s is also bounded by v. This corresponds to exponential tail estimate proved by Kesten.

3) Using hypercontractivity we showed that the variance of D conditioned on D>s is actually bounded above by v/log (1/t) which corresponds to Talagrand’s sub-Gaussian tail-estimate.

4) Almost finally based on a certain very plausible lemma we used hypercontructivity to show that most Fourier coefficients of D are above the log v level, improving the variance upper bound to O(v/log v).

5) Since the plausible lemma is still open (see this MO question) we showed how we can “shortcut” the lemma and prove the upper bound without it.

The major open question

It is an open question to give an upper bound of v^{1-\epsilon} or even v^{2/3} which is the expected answer in dimension two. Michel Ledoux wisely proposes to prove it just for directed percolation in the plane (where all edges are directed up and right) from (0,0) to (v,v) where the edge length is Gaussian or Bernoulli.

Lecture 8

Three Further Applications of Discrete Fourier Analysis (without hypercontractivity)

The three next topics will use Fourier but not hypercontractivity. We start by talking about them.

1) The cap-set problem, some perspective and a little more extremal combinatorics

We talked about Roth theorem, the density Hales Jewett theorem,  the Erdos-Rado delta-system theorem and conjecture. We mentioned linearity testing.

2) Upper bounds for error-correcting codes

This was a good place to mention (and easily prove) a fundamental property used in both these cases:  The Fourier transform of convolutions of two functions f and g is the product of the Fourier transform of f and of g.

3) Social choice and Arrow’s theorem

The Fourier theoretic proof for Arrow’s theorem uses only Parseval’s formula so we are going to start with that.

Fourier-theoretic proof of Arrows theorem and related results.

We talked a little about Condorcet(we will later give a more detailed introduction to social choice). We mentioned Condorcet’s paradox, Condorcet’s Jury Theorem, and the notion of Condorcet winner.

Next we formulated Arrow’s theorem.  Lecture 9 was devoted to a Fourier-theoretic proof of Arrow theorem (in the balanced case). You can find it discussed in this blog post by Noam Nisan.  Lecture 10 mentioned a few further application of the Fourier method related to Arrow’s theorem, as well as a simple combinatorial proof of Arrow’s theorem in full generality. For the Fourier proof of Arrow’s theorem we showed that a Boolean function with all its non-zero Fourier coefficients on levels 0 and 1 is constant, dictatorship or anti-dictatorship. This time we formulated FKN theorem and showed how it implies a stability version of Arrow’s theorem in the neutral case.

Analysis of Boolean Functions – week 4

Lecture 6

Last week we discussed two applications of the Fourier-Walsh plus hypercontractivity method and in this lecture we will discuss one additional application:

The lecture was based on a 5-pages paper by Ehud Friedgut and Jeff Kahn: On the number of copies of one hypergraph in another  Israel Journal of Mathematics Vol. 105 (1998) pp. 251-256.

In this application our method  has nice but not optimal consequences, and another method – applying Shearer’s inequality, gives the optimal result.

1) The question: Given a hypegraph H with k vertices what is the maximum number of labeled copies of H inside a hypegraph G with \ell edges.

There are cases where the answer is known with great precision. The Kruskal-Katona theorem gives the answer when H is the hypegraph whose edges are all the r-subsets of a vertex set V of size k.

In our study  we will fix H and care only about the asymptotic behavior as a function of \ell. We have a simple upper bound of \ell^k and the question is to identify the correct exponent.

2) Stable sets and fractional stable sets. A stable set S in a hypergraph H (also called independent set) is a set of vertices so that every edge contains at most one vertex from S. The stable number \alpha(H) of a hypergraph H is the maximum size of a stable set.

Now comes an idea which is very important in graph theory, of considering the linear programming relaxation of combinatorial parameters. A fractional stable set is an assignment of non negative weights to the vertices, so the sum of weights in every edge is at most one. So this is a “fuzzy set” of a kind the membership of a vertex to a set is described by a number in the interval [0,1] rather than the set {0,1}. The size of a fractional stable set is the sum of weights of all vertices. The fractional stable number \alpha^*(H) is the minimum size of a fractional stable set.

3) Cover and fractional cover numbers

We next described covering and fractional covering (of vertices by edges) in hypergraphs, the covering number \rho(H) of a hypergraph H and the fractional covering number \rho^*(H). Linear programming duality gives that the fractional stable number  is equal to the fractional covering number.

4) The answer:

Friedgut-Kahn theorem: The number of copies of H is a hypergraph G with \ell edges is O(\ell^{\rho^*(H)}) and this bound is sharp.

The case of graphs was proved (in a different language) by Noga Alon in his M. Sc. thesis, and Noga’s first publication  On the number of subgraphs of prescribed type pf graphs with a given number of edges,( Israel J. Math. 38(1981), 116-130).) Part of the challenge was to find the right extension for Alon’s theorem.

5) The lower bound.

Next we explained the nice and simple construction giving the lower bound, which is based on the weights realizing the fractional stable number of H.

6) Bonami’s inequality in a dual form

Our next thing was to state a consequence of Bonami’s hypercontractive inequality, which is a direct extension of Chinchine inequality. Then we showed a weaker upper bound than the actual theorem based on the Bonami inequality .

It is an interesting open question to apply harmonic analysis to the general case. (I believe it is tractable.)

7) Traces and Shearer’s lemma

Next we defined the trace of a hypergraph on a subset W of vertex-set V and stated Shearer’s lemma.

8) More about traces and a little more extremal combinatorics

Not having enough time to complete the proof of Friedgut-Kahn theorem using Shearer’s lemma, we proved the fundamental Sauer-Shelah inequality (see this post), and stated Frankl’s conjecture (see this post, and this one  (sec 3d) ).

Lecture 7

We started with the proof of the Friedgut-Kahn bound using Shearer’s lemma. Then we explained the simple connection between influences and traces and mentioned the connection of Shearer’s lemma (and the Loomis-Whitney theorem) to edge-sioperimetry.

Our next application: First Passage percolation. We gave a short introduction to models of percolation and started to discuss our fourth application of the Fourier+hypercontractivity method: An upper bound for the variance of first passage percolation. Here the method gives the best known result, but unlike KKL’s theorem the result is not sharp. We are third way toward a proof so I may write about it next time. The discussion of first passage percolation is based on the paper First Passage Percolation Has Sublinear Distance Variance by Benjamini, Kalai and Schramm.

Analysis of Boolean Functions – Week 3

Lecture 4

In the third week we moved directly to the course’s “punchline” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity.

Before that we  started with  a very nice discrete isoperimetric question on a graph which is very much related to the graph of the discrete cube.

Consider the graph G whose vertices are 0-1 vectors of length n with precisely r ‘1’s, and with edges corresponding to vertices of Hamming distance two. (Which is the minimal Hamming distance between distinct vertices.) Given a set A of m vertices, how small can E(A, \bar A) be? (We already talked about intersecting families of sets of constant size – the Erdos-Ko-Rado theorem and, in general, it is a nice challenge to extend some of the ideas/methods of the course to constant weight situation.)

And now for the main part of the lecture.

1) Basics harmonic analysis on the discrete cube. We considered the vector space of real functions on the discrete cube \Omega_n and defined an inner product structure. We also defined the p-th norm for 1\le p\le \infty. Next we defined the Fourier-Walsh functions and showed that they form a orthonormal basis. This now leads to the Fourier-Walsh expansion for an arbitrary real function f on the discrete cube f=\sum_{S\subset[n]}\hat f(S)W_S, and we could easily verify Parseval formula.

2) Influence and Fourier. If f is a real function on \Omega_n and f=\sum \hat f(S)W_S its Fourier-Walsh expansion. We showed that I_k(f)=\sum_{S:k \in S}\hat f^2(S). It follows that I(f)=\sum_S\hat f^2(S)|S|. The Fourier-theoretic proof for I(f) ≥ 4 t (1-t) where t=μ(f) now follows easily.

3) Chinchine, hypercontractivity and the discrete isoperimetric inequality.

Next we discussed what will it take to prove the better estimate I(f) ≥ K t log t. We stated Chinchine inequality, and explained why is Chinchine inequality relevant: For Boolean functions the pth power of the p-norm does not depend on p. (It always equals t.) Therefore if t is small, the p-th norms themselves much be well apart! After spending a few moments on the history of the inequality (as told to me by Ron Blei) we discussed what kind of extension do we need, and stated  the Bonami-Gross-Beckner inequality. We use Bonami’s inequality to proof of the inequality I(f) ≥ K t log t and briefly talked about what more does it give.

Lecture 5

1) Review and examples. We reviewed what we did in the previous lecture and considered a few examples: Dictatiorship; the AND function (an opportunity to mention the uncertainty principle,) and MAJORITY on three variables. We also mentioned another connection between influences and Fourier-Walsh coefficients: for a monotone (non decreasing) Boolean function f, I_k(f) = -2\hat f(\{k\}).

2) KKL’s theorem

KKL’s theorem: There is an absolute constant K so that for every Boolean function f, with t=μ(f), there exists k, 1 ≤ k ≤ n such that

I_k(f) \ge K t (1-t) logn/n.

To prove of KKL’s theorem: we repeat, to a large extent, the steps from Lecture 4 (of course, the proof of KKL’s theorem was where this line of argument came from.) We showed that if all individual influences are below 1/sqrt n than I(f) \ge K t(1-t) \log n.

We mentioned one corollary: For Boolean function invariant under a transitive group of permutations, all individual influences are equal and therefore I(f) \ge K t (1-t)\log n.

3) Further problems

In the  last part of the lecture we mentioned seven problems regarding influence of variables and KKL’s theorem (and I added two here):

1) What can be said about balanced Boolean functions with small total influence?

2) What can be said about Boolean functions for which I(f) ≤ K t log (1/t), for some constant K, where t=μ(f)?

3) What can be said about the connection between the symmetry group and the minimum total influence?

4) What can be said about Boolean functions (1/3 ≤ μ(f)≤ 2/3, say) for which \max I_k(f) \le K log n/n.?

5) What more can be said about the vector of influences (I_1(f),I_2(f), \dots I_n(f))?

6)* What is the sharp constant in KKL’s theorem?

7)* What about edge expansions of (small) sets of vertices in general graphs?

8) Under what conditions I(f) \ge n^\beta for β >0.

9) What about influence of larger sets? In particular, what is the smallest t (as a function of n ) such that if \mu(f)=t there is a set S of variables S ≤ 0.3n with I_S(f) \ge 0.9?

(This post  is a short version, I will add details later on.)