Frankl’s Conjecture for Large Families: Ilan Karpas’ Proof

Frankl’s conjecture asserts that a for every finite family of of finite sets that is closed under union, there is an element that belongs to at least half the sets in the family. We mentioned the problem in our very first post, and Tim Gowers ran polymath 11 in attempt to solve it (first post, wikipage). See also this post over GLL and this post.

Here, I want to show Ilan Karpas’ proof (that we mentioned in this post) that the conjecture is correct for “large” families, namely, for families of at least 2^{n-1} subsets of [n]. Karpas’ proof is taken from his paper  Two results on union closed families.

Can Fourier methods solve Frankl’s conjecture? I hope we could have a small discussion about it and related matters, and, in any case, I myself have some comments that I will leave to the comment section.

The theorem

Theorem (Karpas): If B is a union closed family of subsets of [n], and |B| \ge 2^{n-1} then there exists an element k \in [n] such that |\{S \in B: k \in S\}| \ge |B|/2.

Theorem 2 (Karpas): If A is a family of subsets of [n], |A|\le 2^{n-1} with the property

(*) If S\in A and a,b \in S, a\ne b then either S \backslash \{a\}\in A or S \backslash \{b\}\in A.

Then there exists an element k \in [n] such that |\{S \in A: k \in S\}| \le |A|/2.

The implication from Theorem 2 to Theorem 1 is very easy. If B is a union-closed family and A is the complement of B, then B satisfies (*). (Otherwise,  S \backslash \{a\}\in B and S \backslash \{b\}\in B and their union S must be in B. If B has at least 2^{n-1} elements then A has at most 2^{n-1} elements. If |\{S \in A: k \in S\}| \le |A|/2, then |\{S \in B: k \in S\}| \ge |B|/2. We note that Condition (*) is weaker than the assertion that A is union closed and indeed the assertion of Theorem 2 is sharp do not hold when |A| is large. (See remark below.)

Background (a little more than needed)

Edge boundary/influence terminology

For a family A of subsets of [n] its edge-boundary is defined by E(A,\bar A)= \{(S,T)  d(S,T)=1, S \in A, T \notin A\}

The total influence of A is defined by I(A) = \frac {1}{2^{n-1}}|E(A,\bar A)|

Up and down edge boundaries:

E^-(A,\bar A)= \{(S,T) : d(S,T)=1, S \in A, T \notin A, T \subset S \}

E^+(A,\bar A)= \{(S,T) : d(S,T)=1, S \in A, T \notin A, S \subset T \}

I^+(A) =2^{-(n-1)}|E^+(A,\bar A)|

I^-(A) =2^{-(n-1})|E^-(A,\bar A)|

Directional boundaries and individual influences

We now define:

I_k^-(A)= 2^{-(n-1)}|\{S \in A, k \in S, S \backslash\{k\} \notin A \}|,

I_k^+(A)=2^{-(n-1)}|\{S \in A, k \notin S, S \cup \{k\} \notin A \}|,

The influence of k on A is defined by:


Note that the assertion for Frankl’s conjecture is equivalent to: For every union-closed family B there is k such that I_k^-(B) \ge I_k^+(B). Equivalently for every family A whose complement is union-closed (such families are called “simply rooted”) there is k such that I_k^+(A) \le I_k^-(A).


Now, fix a family A of subsets of [n], for S \in A, h_k(S) = 1, if S \delta \{k\}\not in A and h_k(S) = 0 otherwise. h^+_k(S)=1 if k \in S and h_k(S) = 1. (In other words, k \in S and S \backslash \{k\}\notin A.) h^-_k(S)=1 if k \notin S and h_k(S) = 1. (In other words, k \notin S, and S \cup \{k\}\notin A.) Define also h(S) = h_1(S)+h_2(S)+\cdots h_n(S), h^+(S) = h^+_1(S)+h^+_2(S)+\cdots + h^+_n(S), h^-(S) = h^-_1(S)+h^-_2(S)+\cdots + h^-_n(S).

Note that I_k^+(A)=2^{-(n-1)}\sum_{S \in A} h_k^+(S), and similarly for other types of influences.


Let f:\{0,1\}^n \to \{-1,1\} be a Boolean function defined as follows: f(x)=-1 if x represents a set in A, and f(x)=1, otherwise.

We write \hat A(S)=\hat f(S).

It is well known and easy to see that \hat A(\{k\})=I^+_k(A)-I^-_k(A).

Parseval’s formula gives \sum \hat A^2(S)=1. It follows easily from Parseval’s formula that I_k(A)=\sum \{\hat A^2(S):k \in S\},  and hence I(A)=\sum \hat A^2(S)|S|.

The proof:

We write |A|=(1/2-\delta) 2^n.

Our assumption (*) on A is that if S\in A and a,b \in S, a\ne b then either S \backslash \{a\}\in A or S \backslash \{b\}\in A. In other words h^+(S) \le 1 for every S \in A. This implies that

(1) I^+(A) \le 2^{-(n-1)}|A|=(1-2\delta ).

We assume that Frankl’s conjecture is false namely that \hat I^+_k(A) > I^-_k(A), for every k, or equivalently that

(2)  I_k^+(A)- I^-_k(A) = \hat A(\{k\}) > 0, k=1,2,\dots ,n.

Summing over all ks it follows that I^-(A) < I^+(A) hence

(3) I(A)  < 2I^+(A) \le 2-4\delta.

From I(A)=\sum \hat A^2(S)|S|, it follows that

(4)  I(A) \ge 2 - \sum\hat A^2(\{k\}) - 2\hat A^2 (\emptyset ).

Note that

(5) \hat A^2(\emptyset )=4\delta^2


(6) \sum \hat A^2(\{k\}) \le \sum \hat A (\{k\}) = I^+(A)-I^-(A)

Combining (4,5,6)  we get

I^+(A)+I^-(A) \ge 2 - I^+(A)-I^-(A) - 4(\delta^2), or

(7) 2I^+(A) \ge 2-8\delta^2.

(1) and (7) gives 1-2\delta >1-4\delta^2, a contradiction.


Posted in Combinatorics, Mathematics over the Internet, Open problems | Tagged , , , | 11 Comments

Test your intuition 33: Why is the density of any packing of unit balls decay exponentially with the dimension?

Test your intuition: What is the simplest explanation you can give to the fact that the density of every packing of unit balls in R^d is exponentially small in d?

Answers are most welcome.

Of course, understanding the asymptotic behavior of the density \rho_d of densest packing of unit spheres in R^d is a central  problem in geometry. It is a long standing hope (perhaps naïve) that algebraic-geometry codes will eventually lead to examples showing that \rho_d \ge (2-\delta)^{-d} giving an exponential improvement of Minkowsky’s 1905 bound.  (For more on sphere packing asymptotically and in dimensions 8 and 24 see this post.)

The result by Serge Vlăduţ from the previous post can be seen (optimistically) as a step in the direction of exponential improvement to Minkowski’s bound.



Posted in Combinatorics, Geometry, Test your intuition | Tagged , | 4 Comments

Serge Vlăduţ : Lattices with exponentially large kissing numbers

   (I thank Avi Wigderson for telling me about it.) Serge Vlăduţ just arxived a paper with examples of lattices in R^n such that the kissing number is exponential in n. The existence of such a lattice is a very old open problem and the best record was an example where the kissing number is n^{\log n}. (This is based on a 1959 construction of Barnes and Wall and can be found in the famous book by Conway and Sloane.) Noga Alon found in 1997 collections of spheres so that each one touches subexponentially many others. Vlăduţ’s result is very exciting!

A crucial step was a result by Ashikhmin,  Barg, and Vlăduţ from 2001 showing that certain algebraic-geometry binary linear codes have exponentially many minimal weight vectors. (This result disproved a conjecture by Nati Linial and me.) This follows by applying in a very clever way early 80s constructions going back to Bos, Conway, Sloane and Barnes and Sloane, and this requires some subtle selection of the AG-codes that can be used. To quote the author: “In order to apply Constuctions D and E we need specific good curves (the curves in the Garcia Stichtenoth towers do not perfectly match our construction) and some Drinfeld modular curves  perfectly suit our purposes.”

These lines of ideas and appropriate AG-codes look to me the most promising avenue towards exponential lower bound for the Borsuk problem. (See, e.g.,  this paper and this post) We need for that purpose AG codes X where the maximum weight occurs exponentially often (this need not be difficult) and that every subset of vectors that misses the maximum distance is exponentially smaller than |X|.


Posted in Combinatorics, Geometry | Tagged | 3 Comments

Peter Keevash and Eoin Long: Forbidden vector-valued intersections

Peter Keevash and Eoin Long arxived some time ago a very nice paper:  Forbidden vector-valued intersections, which settled a problem that was first posed here on the blog. Here is the abstract.

We solve a generalised form of a conjecture of Kalai motivated by attempts to improve the bounds for Borsuk’s problem. The conjecture can be roughly understood as asking for an analogue of the Frankl-Rödl forbidden intersection theorem in which set intersections are vector-valued. We discover that the vector world is richer in surprising ways: in particular, Kalai’s conjecture is false, but we prove a corrected statement that is essentially best possible, and applies to a considerably more general setting. Our methods include the use of maximum entropy measures, VC-dimension, Dependent Random Choice and a new correlation inequality for product measures.

Actually, the original motivation for the problem was related to the cap-set problem. (Item 19 in the third post on the cap-set problem and the Frankl-Rodl’s theorem).  In 2009 I wrote three posts (ABC) with some ideas on connections between the cap-set problem and Frankl-Wilson/Frankl-Rodl’s theorem. The first post also dicusses various ways in which Frankl-Rodl’s theorem is more general than Frankl-Wilson.

Other related posts and papers:  Frankl-Wilson theorem; A 2014 paper by Keevash and Long Frankl-Rödl type theorems for codes and permutations;  Posts (I, II) on the startling solution of the cap-set prolems following the works of Croot, Lev, Pach, Ellenberg, and Gijswijt.


Posted in Combinatorics | Tagged , | Leave a comment

Peter Keevash: More and Easier Designs!

Peter Keevash just posted on the arxiv a couple of new papers on designs. The first is a rewritten version of his original paper The existence of designs with a much simpler proof. The second paper The existence of designs II contains several new startling results, such as the existence of resolvable hypergraph designs, large sets of hypergraph designs and decompositions of designs by designs. This is great!

Continue reading

Posted in Combinatorics | Tagged | Leave a comment

Monday February 19: Quantum Coding and High Dimensional Expanders

Tonight at 8:00 Israel time TCS+ Dor Misner on 2-to-2 games.


On Monday, February 19, we will have a special day on “Quantum Coding and High Dimensional Expanders” organized by Gilles Zemor.

Sandwiches will be served for lunch, alongside cut vegetables and pastries.

Our calendar:

Place: Room 130, IIAS, Feldman Building, Givat Ram


10:00 – 11:00 Gilles Zemor. Background on quantum computing and coding.

11:30 – 12:30 Gilles Zemor. Quantum stabilizer codes and quantum LDPC codes.

14:00 – 15:00 Dorit Aharonov. Quantum locally testable codes.

15:15 – 16:15 Gilles Zemor. Quantum LDPC codes and high-dimensional expanders.

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

Alef’s Corner: There is Still a Small Gap in the Proof

Image | Posted on by | Leave a comment

My Argument Against Quantum Computers: An Interview with Katia Moskvitch on Quanta Magazine

Quanta Magazine published an interview with me about quantum computers. It was a pleasure discussing this issue with Katia Moskvitch and I enjoyed also the photo session with David Vaaknin who also took a video of me explaining the importance of quantum noise.

For more information, here are links to my 2014 paper with Guy Kindler, my paper The Quantum Computer Puzzle on the Notices of AMS, its arxived expanded version, and my ICM2018 paper. Last but not least my cartoon post: If Quantum Computers are not Possible Why are Classical Computers Possible?

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , , , | 8 Comments

The Semester Break activities of the High Dimensional Combinatorics and Expanders Special Year

UPDATE: Schedule change! An additional workshop On February 5 and shift in dats of the others. Here is the calendar

We have now at HUJI a semester break, but the special semester in High dimensional combinatorics and IIAS leaded by Tali Kaufman and Alex Lubotzky is extremely active.

The Monday program continues during the semester break (Jan 26 to March 18) in the form of “special days”, each devoted to a certain topic. (On a very basic level.)

The first special day, this Monday, January 29, is organized by Anna Gundert and Uli Wagner.
The topic is pseudo-randomness. On January 30 there is an Action now day (less basic); on February 05: Stability and property testing February 12: High dimensional Ranom walks day; On February 19: Error correcting codes and high dimensional expanders; on.

I will update about the later special days later.

On Monday, February 12, we will have a special day on “High Dimensional Random Walks” organized by Ron Rosenthal.

Place: Room 130, IIAS, Feldman Building, Givat Ram
10:00-11:00     Dudi Mass –  Random walks by decreasing differences method 

11:30-12:30     Ron Rosenthal – Random walks on oriented cells – part I

13:45- 14:45    Izhar Oppenheim –  Decomposition Theorem for high dimensional random walks

15:00-16:00     Amitay Kamber –  Cutoff of random walks on hyperbolic surfaces and Ramanujan complexes

16:30-17:30     Ron Rosenthal – Random walks on oriented cells – part II

Continue reading

Posted in Combinatorics, Updates | Tagged | 1 Comment

Akshay Venkatesh Lectures at HUJI – Ostrowski’s Prize Celebration, January 24&25

Thursday January 25, 14:15-15:45 Ostrowski’s prize ceremony and Akshay Venkatesh’s prize lecture: Period maps and Diophantine problems

Followed by a Basic notion lecture by Frank Calegary 16:30-17:45: The cohomology of arithmetic groups and Langlands program

Wednesday January 24, 18:00-17:00: Akshay Venkatesh lectures on Cryptography and the geometry of algebraic equations. Lecture accessible also to second and third year undergraduate students.


Posted in Algebra and Number Theory, Computer Science and Optimization, Geometry, Updates | Tagged , , | Leave a comment