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.

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , | Leave a comment

Real Analysis Introductory Mini-courses at Simons Institute

The Real Analysis ‘Boot Camp’ included three excellent mini-courses.

Inapproximability of Constraint Satisfaction Problems (5 lectures)
Johan Håstad (KTH Royal Institute of Technology)

(Lecture I, Lecture II, Lecture III, Lecture IV, Lecture V)

jh-choclate

Unlike more traditional ‘boot camps’ Johan rewarded answers and questions by chocolates (those are unavailable for audience of the video).

Starting from the PCP-theorem (which we will take as given) we show how to design and analyze efficient PCPs for NP-problems. We describe how an efficient PCP using small amounts of randomness can be turned into an inapproximability result for a maximum constraint satisfaction problem where each constraint corresponds to the acceptance criterion of the PCP. We then discuss how to design efficient PCPs with perfect completeness in some interesting cases like proving the hardness of approximating satisfiable instances of 3-Sat.

We go on to discuss gadget construction and how to obtain optimal reductions between approximation problems. We present Chan’s result on how to take products of PCPs to get hardness for very sparse CSPs and give some preliminary new results using these predicates as a basis for a gadget reduction.

Finally we discuss approximation in a different measure, and in particular the following problem. Given a (2k+1)-CNF formula which admits an assignment that satisfies k literal in each clause, is it possible to efficiently find a standard satisfying assignment?

Analytic Methods for Supervised Learning​ (4 lectures)
Adam Klivans (University of Texas, Austin)

(Lecture I, Lecture II, Lecture III, Lecture IV) additional related lecture by Adam on Moment matching polynomials.

In this mini-course we will show how to use tools from analysis and probability (e.g., contraction, surface area and limit theorems) to develop efficient algorithms for supervised learning problems with respect to well-studied probability distributions (e.g., Gaussians). One area of focus will be understanding the minimal assumptions needed for convex relaxations of certain learning problems (thought to be hard in the worst-case) to become tractable.

Introduction to Analysis on the Discrete Cube (4 lectures)
Krzysztof Oleszkiewicz (University of Warsaw)

(Lecture I, Lecture II, Lecture III, Lecture IV) Here are the slides for the lecture which contain material for 1-2 additional lectures.

The basic notions and ideas of analysis on the discrete cube will be discussed, in an elementary and mostly self-contained exposition. These include the Walsh-Fourier expansion, random walk and its connection to the heat semigroup, hypercontractivity and related functional inequalities, influences, the invariance principle and its application to the Majority is Stablest problem. The mini-course will also contain some other applications and examples, as well as several open questions.

Posted in Analysis, Computer Science and Optimization, Conferences | Tagged , , | Leave a comment

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.

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged | Leave a comment

Polymath 8 – a Success!

mat2

Yitang Zhang

Update (July 22, ’14). The polymath8b paper “Variants of the Selberg sieve, and bounded intervals containing many primes“, is now on the arXiv. See also this post on Terry Tao’s blog. Since the last update, we also had here at HUJI a beautiful learning seminar on small gaps between primes. James Maynard gave a series of three lectures and additional lectures were given by Zeev Rudnick and Tamar Ziegler.

 

Update (Jan 9, ’14, corrected Jan 10):  Polymath8b have just led to an impressive progress: Goldston, Pintz, and Yıldırım showed that conditioned on the  Elliott-Halberstam conjecture (EHC) there are infinitely many primes of bounded gap below 16. Maynard improved it to 12. Polymath8b have just improved it based on a generalized form of the EHC (proposed in 1986 by Bombieri, Friedlander, and  Iwaniec) further to 8.  [Further update:  6 and there are reasons so suspect that further improvement requires major breakthrough - namely getting over the "parity problem".] The unconditional bound for gaps stands now on 270.

Update: A paper by James Maynard entitled “Small gaps between primes” proved that for  every k there are infinitely many intervals of length f(k) each containing at least k primes. He also reduced the gap between infinitely many pairs of primes to 600. The method is also (said to be) much simpler. Amazing!

Terry Tao launched a followup polymath8b to  improve the bounds for gaps between primes based on Maynard’s results.

Update: Here is the paper: A NEW BOUND FOR GAPS BETWEEN PRIMES by D. H. J. Polymath.

Zhang’s breakthrough and Polymath8

The main objectives of the polymath8 project, initiated by Terry Tao back in June, were “to understand the recent breakthrough paper of Yitang Zhang establishing an infinite number of prime gaps bounded by a fixed constant {H}, and then to lower that value of {H} as much as possible.”

Polymath8 was a remarkable success! Within two months the best value of H that was 70,000,000 in Zhang’s proof was reduced to 5,414. Moreover, the polymath setting looked advantageous for this project, compared to traditional ways of doing mathematics.

The polymath project gave opportunity to a number of researchers to understand Zhang’s proof and the earlier breakthrough by Daniel Goldston, János Pintz, and Cem Yıldırım. It also gave an opportunity to a larger number of mathematicians to get some feeling about the involved mathematics.

The story

Twin primes are two primes p and p+2. The ancient twin prime conjecture asserts that there are infinitely many twin primes. The prime number theorem asserts that there are (asymptotically)  n/log n primes whose value is smaller than a positive integer n, and this implies that we can find arbitrary large pairs of consecutive primes  p and q such that q-p is at most (log p). Until a few years ago nothing asymptotically better was known. Goldston, Pintz, and Yıldırım (GPY), showed in 2005 that there infinitely many pairs of primes p and q such that q-p is O(\sqrt {\log n}). A crucial idea was to derive information on gaps of primes from the distribution of primes in arithmetic progressions. GPY showed that conditioned on the  Elliott-Halberstam conjecture (EHC) there are infinitely many primes of bounded gaps (going all the way to 16, depending on a certain parameter in the conjecture, but not to 2). Yitang Zhang did not prove the EHC but based on further understanding of the situation found a way to shortcut the conjecture and to prove that there are infinitely many primes of with bounded gaps unconditionally!

Here is a very nice 2007 survey article by Kannan Soundararajan on this  general area of research and the GPY breakthrough. (One thing I recently learned is that  Soundararajan is called by friends and colleagues “Sound”. ) This article starts with a very thoughtful and endearing answer to the quastion: “Why do we care at all? After all primes were meant to be multiplied, not subtracted (or added).”

Here is a short list of thoughts (things I learned, things I wish to understand better…) from following (from distance) Polymath8 and related Internet activity.

1) How information on primes in arithmetic progressions leads to information on gaps between primes?

I do not really understand why the information on primes in arithmetic progressions e.g. the Elliott-Halberstam conjecture lead to the conclusion regarding primes with bounded gaps. I would be very happy to get a feeling for it.

2) The three-primes barrier.

Already GPY  tried to extend their methods to show the existence of three primes in a bounded interval of integers. So far, it is not known how to show that intervals of the form [n,n+o(log n)] contain triples of primes infinitely often. Perhaps, to actually solve the twin prime conjecture we will need to get a breakthrough for triples of primes, but maybe not. See also this MO question asked by Noam Elkies.

Update: Here is another interesting MO question Quantitative lower bounds related to Zhang’s theorem on bounded gaps, asked by Eric Naslund. Eric asks: what can be say based on Zhang’s work about the smallest value  of a pair of primes of distance k apart?

3) Cauchy-Schwarz everywhere;

This may sound silly but the way Cauchy-Schwarz (C-S) inequality is used again and again make you wonder again why C-S is it so useful, and why it is mainly C-S which is so useful.

4) Can detailed statistical understanding of primes in sets other than AP  be useful?

In recent years there was much activity (and I also was interested) in Mobius randomness and analogs of the prime number theorem for various more complicated subsets of integers. (E.g., subsets defined by various properties of the digital expansion.) Can understanding of this kind  also be used for the prime-gaps questions?

5) Usefulness of Deligne’s work on Riemann’s hypothesis for functions fields for questions in analytic number theory.

I knew, of course that Deligne famously proved analogs of the Riemann hypothesis for function fields in great generality but I was not aware that these results have applications to “ordinary” analytic number theory. Again, this is something I would be happy to know a little more about. There is a nice recent post on the Riemann hypothesis in various settings on “What’s new”.

6) Parity problem.  (Added Nov 27) There is a difficult “parity problem” which seems to be a difficult obstacle for getting the gap to two. (And for various related goals). Terry Tao wrote about it in 2007 in this post. In polymath8b VII an attempt to cross the “parity barrier” was  made but (as people expected) it turned out that the parity barrier indeed shows up causes this attempt to fail. (Update July 14:) This is further explained in this new post over Tao’s blog.

7) (Added Nov 27) One thing I am curious about is the following. Consider a random subset of primes (taking every prime with probability p, independently, and say p=1/2). Now consider only integers involving these primes. I think that it is known that this system of “integers” satisfies (almost surely) PNT but not at all RH. We can consider the properties BV (Bombieri Vinogradov), or more generally EH(θ) and the quantities H_m. For such systems does BV typically hold? or it is rare like RH. Is Meynard’s implication applies in this generality? Nicely here we can hope even for infinite consecutive primes. Update: after thinking about it further and a little discussion over polymath8b it looks that current sieve methods, and some of the involved statements, rely very strongly on both the multiplicative and additive structure of the integers and do not allow extensions to other systems of “integers.”

Posted in Mathematics over the Internet, Number theory, Open problems | Tagged , , , , | 9 Comments

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.)

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , , | Leave a comment

Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found

The upper bound theorem asserts that among all d-dimensional polytopes with n vertices, the cyclic polytope maximizes the number of facets (and k-faces for every k). It was proved by McMullen for polytopes in 1970, and by Stanley for general triangulations of spheres in 1975. This theorem is related to a lot of mathematics (and also computational geometry) and there are many interesting extensions and related conjectures.

Richard Stanley posted (on his  homepage which is full with interesting things) an article describing How the proof of the upper bound theorem for triangulations of spheres was found.

It is interesting how, for Richard, the work oמ face-numbers of polytopes started with his work on integer points in polytopes and especially the Anand-Dumir-Gupta” conjecture on enumeration of “magic squares.” (See this survey article by Winfried Bruns.)  Integer points in polytopes, and face numbers represent the two initial chapters of Richard’s “green book” on Commutative algebra and combinatorics. Both these topics are related to commutative algebra and to the algebraic geometry of toric varieties.

CCA

See also these relevant posts “(Eran Nevo) The g-conjecture II: The commutative algebra connection,), (Eran Nevo) The g-conjecture I, and How the g-conjecture came about. Various results and problems related to the upper bound theorem can be found in Section 2 of my paper Combinatorics with a Geometric Flavor.

Posted in Combinatorics, Convex polytopes | Tagged , | 2 Comments

Simons@UCBerkeley

raghu
Raghu Meka talking at the workshop 

I spend the semester in Berkeley at the newly founded Simons Institute for the Theory of Computing. The first two programs demonstrate well the scope of the center and why it is needed. One program on real analysis in computer science seems to demonstrate very theoretical aspects of the theory of computing and its relations with pure mathematics. The second program is on big data analysis, a hot topic in statistics, machine learning and many areas of science, technology, and beyond. And one surprise is that there is a lot in common to these two areas. Next semester, there will be one special program on quantum Hamiltonian complexity which again may seem in the very far-theoretic side of TOC as it largely deals with computational classes between NP and QMA, (far beyond what we seem relevant to real-life), and yet this study is related to classical efficient algorithms in condensed matter physics, with connections to real-life physics and technology. The other special program in Spring 2014 is on evolution (evolutionary biology and TOC)!

The program I am mainly involved with is on real analysis in computer science. It started with a very successful and interesting workshop Real Analysis in Testing, Learning and Inapproximability. This week (Spet 9-13) there is a “Boot camp on real analysis” with three mini-courses. The amount of activity in the center and around it is too vast to allow any sort of live-blogging but I do hope to share with you a few things over the semester. Two things for now: Kalvin Lab, the building where the institute is located is beautiful! The video coverage of talks, (both the live streaming and the video archives) is of very high quality (reflecting both the excellent equipment and the people that operate it).

It is always a special feeling to witness the first days of the academic year whether it is in Israel or in the US. Many students returning to school, many first-year students, at times, accompanied by their proud parents, and quite a few colleagues who share this excitement and are just as surprised on how younger and younger these students are becoming (and some other colleagues, who this year are proud parents themselves). This time, I spent a few days in Yale and saw the excitement there, and then continued with the same “high” mood on the first days of school here at Berkeley.

Posted in Conferences, Updates | 1 Comment

Analysis of Boolean functions – week 2

Post on week 1; home page of the course analysis of Boolean functions

Lecture II:

We discussed two important examples that were introduced by Ben-Or and Linial: Recursive majority and  tribes.

Recursive majority (RM): F_m is a Boolean function with 3^m variables and F_{m+1} (x,y,z) = F_1(F_m(x),F_m(y),F_m(z)). For the base case we use the majority function F_1(x,y,z)=MAJ(x,y,z).

Tribes: Divide your n variables into s pairwise disjoint sets (“tribes”) of cardinality t. f=1 if for some tribe all variables equal one, and thus T=0 if for every tribe there is a variable with value ’0′.

We note that this is not an odd function i.e. it is not symmetric with respect to switching ’0′ and ’1′. To have \mu=1/2 we need to set t=\log_2n - \log_2\log_2n+c. We computed the influence of every variable to be C log n/n. The tribe function is a depth-two formula of linear size and we briefly discussed what are Boolean formulas and Boolean circuits (These notions can be found in many places and also in this post.).

I states several conjectures and questions that Ben-Or and Linial raised in their 85 paper:

Conjecture 1: For every balanced Boolean function with n variables there is a variable k whose influence is \Omega (\log n/n).

Conjecture 2: For every balanced Boolean function with n variables there is a set S of n/log n variables whose influence I_S(f) is 1-o(1).

Question 3: To what extent can the bound in Conjecture 2 be improved if the function f is odd. (Namely, f(1-x_1,1-x_2,\dots, 1-x_n)=1-f(x_1,x_2,\dots, x_n).)

Our next theme was discrete isoperimetric results.  I noted the connection between total influence and edge expansion and proved the basic isoperimetric inequality: If μ(f)=t then I(f) ≥ 4 t(1-t). The proof uses the canonical paths argument.

Lecture III:

We proved using “compression” that sharp bound on I(f) as a function of t=μ(f). We made the analogy between compression and Steiner symmetrization – a classic method for proving the classical isoperimetric theorem. We discussed similar results on vertex boundary and on Talagrand-Margulis boundary (to be elaborated later in the course).

Then We proved the Harris-Kleitman inequality and showed how to deduce the fact that intersecting family of subsets of [n] with the property that the family of complements is also intersecting has at most 2^{n-2} sets.

The next topic is spectral graph theory. We proved the Hoffman bound for the largest size of an independent set in a graph G.

I mentioned graph-Laplacians and the spectral bound for expansions (Alon-Milman, Tanner)..

The proofs mentioned above are so lovely that I will add them on this page, but sometime later.

Next week I will introduce harmonic analysis on the discrete cube and give a Fourier-theoretic explanation for  the additional log (1/t) factor in the edge isoperimetric inequality.

Important announcement: Real analysis boot camp in the Simons Institute for the Theory of Computing, is part of the program in Real Analysis and Computer Science. It is taking place next week on September 9-13 and has three lecture series. All lecture series are related to the topic of the course and especially:

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , | Leave a comment

Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture

Borsuk asked in 1933 if every bounded set K of diameter 1 in R^d can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. Many interesting open problems remain.  The first two posts in the series “Around Borsuk’s Conjecture” are here and here. See also these posts (I,II,III, IV), and the post “Surprises in mathematics and theory” on Lipton and Reagan’s blog GLL.

Can we save the conjecture? We can certainly try, and in this post I would like to examine the possibility that Borsuk’s conjecture is correct except from some “coincidental” sets. The question is how to properly define “coincidental.”

Let K be a set of points in R^d and let A be a set of pairs of points in K. We say that the pair (K, A) is general if for every continuous deformation of the distances on A there is a deformation K’ of K which realizes the deformed distances.

(This condition is related to the “strong Arnold property” (aka “transversality”) in the theory of Colin de Verdière invariants of graphs; see also this paper  by van der Holst, Lovasz and Schrijver.)

Conjecture 1: If D is the set of diameters in K and (K,D) is general then K can be partitioned into d+1 sets of smaller diameter.

We propose also (somewhat stronger) that this conjecture holds even when “continuous deformation” is replaced with “infinitesimal deformation”.

The finite case is of special interest:

A graph embedded in R^d is stress-free if we cannot assign non-trivial weights to the edges so that the weighted sum of the edges containing any  vertex v (regarded as vectors from v) is zero for every vertex v. (Here we embed the vertices and regard the edges as straight line segments. (Edges may intersect.) Such a graph is called a “geometric graph”.) When we restrict Conjecture 1 to finite configurations of points we get.

Conjecture 2: If G is a stress free geometric graph of diameters in R^d  then G is (d+1)-colorable.

A geometric graph of diameters is a geometric graph with all edges having the same length and all non edged having smaller lengths. The attempt for “saving” the Borsuk Conjecture presented here and Conjectures 1 and 2 first appeared in a 2002 collection of open problems dedicated to Daniel J. Kleitman, edited by Douglas West.

When we consider finite configurations of points  we can make a similar conjecture for the minimal distances:

Conjecture 3: If the geometric graph of pairs of vertices realizing the minimal distances of a point-configuration in R^d is stress-free, then it is (d+1)-colorable.

We can speculate that even the following stronger conjectures are true:

Conjecture 4: If G is a stress-free geometric graph in R^d so that all edges in G are longer than all non-edges of G, then G is (d+1)-colorable.

Conjecture 5: If G is a stress-free geometric graph in R^d so that all edges in G are shorter than all non-edges of G, then G is (d+1)-colorable.

We can even try to extend the condition further so edges in the geometric graph will be larger (or smaller) than non-edges only just “locally” for neighbors of each given vertex.

Comments:

1) It is not true that every stress-free geometric graph in R^d is (d+1)-colorable, and not even that every stress-free unit-distance graph is (d+1)-colorable. Here is the (well-known) example referred to as the Moser Spindle. Finding conditions under which stress-free graphs in R^d are (d+1)-colorable is an interesting challenge.

MoserSpindle_700

2) Since a stress-free graph with n vertices has at most dn - {{d+1} \choose {2}} edges it must have a vertex of degree 2d-1 or less and hence it is 2d colorable. I expect this to be best possible but I am not sure about it. This shows that our “saved” version of Borsuk’s conjecture is of very different nature from the original one. For graphs of diameters in R^d the chromatic number can, by the work of Jeff and me be exponential in \sqrt d.

3) It would be interesting to show that conjecture 1 holds in the non-discrete case when  d+1 is replaced by 2d.

4) Coloring vertices of geometric graphs where the edged correspond to the minimal distance is related also the the well known Erdos-Faber-Lovasz conjecture.ERDSFA~1.

See also this 1994 article by Jeff Kahn on Hypergraphs matching, covering and coloring problems.

5) The most famous conjecture regarding coloring of graphs is, of course, the four-color conjecture asserting that every planar graph is 4-colorable that was proved by Appel and Haken in 1976.  Thinking about the four-color conjecture is always both fascinating and frustrating. An embedding for maximal planar graphs as vertices of a convex 3-dimensional polytope is stress-free (and so is, therefore, also a generic embedding), but we know that this property alone does not suffice for 4-colorability. Finding further conditions for  stress-free graphs in R^d that guarantee (d+1)-colorability can be relevant to the 4CT.

An old conjecture of mine asserts that

Conjecture 6: Let G be a graph obtained from the graph of a d-polytope P by triangulating each (non-triangular) face with non-intersecting diagonals. If G is stress-free (in which case the polytope P is called “elementary”) then G is (d+1)-colorable.

Closer to the conjectures of this post we can ask:

Conjecture 7: If G is a stress-free geometric graph in R^d so that for every edge  e of G  is tangent to the unit ball and every non edge of G intersect the interior of the unit ball, then G is (d+1)-colorable.

A question that I forgot to include in part I.

What is the minimum diameter d_n such that the unit ball in R^n can be covered by n+1 sets of smaller diameter? It is known that 2-C'\log n/n \le d_n\le 2-C/n for some constants C and C’.

Posted in Combinatorics, Convexity, Geometry, Open problems | Tagged , , , | Leave a comment

Analysis of Boolean Functions – week 1

Home page of the course.

In the first lecture I defined the discrete n-dimensional cube and  Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets.

1) The largest possible intersecting family of subsets of [n];

2) The largest possible intersecting family of subsets of [n] so that the family of complements is also intersecting;

3) The largest possible family of graphs on v vertices such that each two graphs in the family contains a common triangle;

4) Chvatal’s conjecture regarding the maximum size of an intersecting family of sets contained in an ideal of sets;

5) Erdos-Ko-Rado Theorem.

Exercise: Prove one of the following

a) The Harris-Kleitman’s inequality

b) (from the H-K inequality) Every family of subsets of [n] with the property that every two sets have non-empty intersection and no full union contains at most 2^{n-2} sets.

More reading: this post :”Extremal combinatorics I: extremal problems on set systems“. Spoiler: The formulation of Chvatal’s conjecture but also the answer to the second exercise can be found on this post: Extremal combinatorics III: some basic theorems. (See also peoblen 25 in the 1972 paper Selected combinatorial research problems by Chvatal, Klarner and Knuth.)

feige

I moved to discuss the problem of collective coin flipping and the notion of influence as defined by Ben-Or and Linial. I mentioned the Baton-passing protocol, the Alon-Naor result, and Feige’s two-rooms protocol.

More reading: this post :” Nati’s influence“. The original paper of Ben-Or Linial:  Collective coin flipping, M. Ben-Or  and N. Linial, in “Randomness and    Computation” (S. Micali ed.) Academic Press, New York, 1989, pp.    91-115.

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged , , , | 1 Comment