Joel David Hamkins’ 1000th MO Answer is Coming

joel

Update (May 2014): The second MO contributor to answer 1000 questions is another distinguished mathematician (and a firend) Igor Rivin.

Joel David Hamkins’ profile over MathOverflow reads: “My main research interest lies in mathematical logic, particularly set theory, focusing on the mathematics and philosophy of the infinite. A principal concern has been the interaction of forcing and large cardinals, two central concepts in set theory. I have worked in group theory and its interaction with set theory in the automorphism tower problem, and in computability theory, particularly the infinitary theory of infinite time Turing machines. Recently, I am preoccupied with the set-theoretic multiverse, engaging with the emerging field known as the philosophy of set theory.”

Joel is a wonderful MO contributor, one of those distinguished mathematicians whose arrays of MO answers in their areas of interest draw coherent deep pictures for these areas that you probably cannot find anywhere else. And Joel is also a very highly decorated and prolific MO contributor, whose 999th answer appeared today!!

Here is a very short selection of Joel’s answers. To (MO founder) Anton Geraschenko’s question What are some reasonable-sounding statements that are independent of ZFC? Joel answered; “If a set X is smaller in cardinality than another set Y, then X has fewer subsets than Y.” Joel gave a very thorough answer to  my question on Solutions to the Continuum Hypothesis; His 999th answer is on the question Can an ultraproduct be infinite countable? (the answer is yes! but this is a large cardinal assumption.) Update: Joel’s 1000th answer on a question about logic in mathematics and philosophy was just posted.

Joel also wrote a short assay, the use and value of MathOverflow over his blog. Here it is:

The principal draw of mathoverflow for me is the unending supply of extremely interesting mathematics, an eternal fountain of fascinating questions and answers. The mathematics here is simply compelling.

I feel that mathoverflow has enlarged me as a mathematician. I have learned a huge amount here in the past few years, particularly concerning how my subject relates to other parts of mathematics. I’ve read some really great answers that opened up new perspectives for me. But just as importantly, I’ve learned a lot when coming up with my own answers. It often happens that someone asks a question in another part of mathematics that I can see at bottom has to do with how something I know about relates to their area, and so in order to answer, I must learn enough about this other subject in order to see the connection through. How fulfilling it is when a question that is originally opaque to me, because I hadn’t known enough about this other topic, becomes clear enough for me to have an answer. Meanwhile, mathoverflow has also helped me to solidify my knowledge of my own research area, often through the exercise of writing up a clear summary account of a familiar mathematical issue or by thinking about issues arising in a question concerning confusing or difficult aspects of a familiar tool or method.

Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts. This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk. This kind of knowledge has helped me to improve my mathematical writing in general.

So, thanks very much mathoverflow! I am grateful.

Thanks very much, Joel,  for your wonderful mathoverflow answers and questions!

JDH

Posted in Mathematical logic and set theory, Mathematics over the Internet | Tagged , | 3 Comments

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 .

Posted in Combinatorics, Open problems | Tagged , , | 11 Comments

Many Short Updates

Things in Berkeley and later here in Jerusalem were very hectic so I did not blog much since mid October. Much have happened so let me give brief and scattered highlights review.

Two “real analysis” workshops at the Simons Institute – The first in early October was on Functional Inequalities in Discrete Spaces with Applications and the second in early December was on Neo-classical methods in discrete analysis. Many exciting lectures! The links lead to the videotaped  lectures. There were many other activities at the Simons Institute also in the parallel program on “big data” and also many interesting talks at the math department in Berkeley, the CS department and MSRI.

inequality

To celebrate the workshop on inequalities, there were special shows in local movie theaters

My course at Berkeley on analysis of Boolean functions – The course went very nicely. I stopped blogging about it at weak 7. Just before a lecture on MRRW upper bounds for binary codes, a general introductory lecture on social choice, and then several lectures by Guy Kindler (while I was visiting home) on the invariance principle and majority is stablest theorem.  The second half of the course covered sharp threshold theorems, applications for random graphs, noise sensitivity and stability, a little more on percolation and a discussion of some open problems.

nams

Back to snowy Jerusalem, Midrasha, Natifest, and Archimedes. I landed in Israel on Friday toward the end of the heaviest  snow storm in Jerusalem. So I spent the weekend with my 90-years old father in law before reaching Jerusalem by train. While everything at HU was closed there were still three during-snow mathematics activities at HU. There was a very successful winter school (midrasha) on analytic number theory which took place in the heaviest storm days.  Natifest was a very successful conference and I plan to devote to it a special post, but meanwhile, here is a link to the videotaped lectures and a picture of Nati with Michal, Anna and Shafi. We also had a special cozy afternoon event joint between the mathematics department and the department for classic studies  where Reviel Nets talked about the Archimedes Palimpses.

royal

The story behind Reviel’s name is quite amazing. When he was born, his older sister tried to read what was written in a pack of cigarettes. It should have been “royal” but she read “reviel” and Reviel’s parents adopted it for his name.

archimedes

Posted in Conferences, Updates | 4 Comments

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

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

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

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

More around Borsuk

Piotr Achinger told me two things abour Karol Borsuk:

 

From Wikipedea: Dunce hat Folding. The blue hole is only for better view

Borsuk trumpet

is  another name for the contractible non-collapsible space commonly called also the “dunce hat“. (See also this post.) For a birthday conference of Borsuk, a cake of this shape was baked and served.

 Hodowla zwierzątek

(polish, in English: Animal Husbandry) is (from Wikipedea, here is the link) a dice game invented and published by Karol Borsuk at his own expense in 1943, during the German occupation of Warsaw. Sales of the game were a way for Borsuk to support his family after he lost his job following the closure by the German occupation authorities of Warsaw University. The original sets were produced by hand by Borsuk’s wife, Zofia. The author of the drawings of animals was Janina Borsuk née Śliwicka. The game was one of the first in the world to feature a 12-sided dice.

Posted in Updates | Tagged | 4 Comments

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.

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

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