Small doubling, atomic structure and ℓ-divisible set families
- Mathematics, ETH Zurich
- More about Lior Gishboliner
- Mathematics, ETH Zurich
- More about Benny Sudakov
- Department of Mathematics and Mathematical Statistics, University of Umeå
- More about Istvan Tomon
Editorial introduction
Small doubling, atomic structure and ℓ-divisible set families, Discrete Analysis 2022:11, 16 pp.
The following fact is a well-known and simple illustration of the power of linear algebra in solving combinatorial problems. Let A be a collection of subsets of {1,2,…,n} such that any two subsets in the collection have an intersection of even size. Then |A|≤2⌊n/2⌋, with equality attained if A consists of all sets A that are unions of the sets {1,2},{3,4},…, where the last set in the sequence is {n−1,n} if n is even, and {n−2,n−1} if n is odd.
This can be proved by associating with each set A its characteristic function, and regarding each function as an element of Fn2. If x and y are elements of Fn2, then we can define their scalar product ⟨x,y⟩ to be ∑ni=1xiyi, and the question we started with is then equivalent to asking how many vectors it is possible to choose if all scalar products are zero.
If A⊂Fn2 and we choose a maximal linearly independent set x1,…,xm of A, then every element x of A satisfies m linearly independent conditions ⟨xi,x⟩=0, so A lives inside a subspace of codimension at least m and therefore dimension at most n−m. It follows that m≤n−m and therefore that m≤⌊n/2⌋, which gives the required bound on |A|.
An obvious follow-up question is to ask what happens if the size of every intersection is a multiple of 3, or more generally of ℓ for some positive integer ℓ. The obvious generalization of the construction above gives a lower bound of 2⌊n/ℓ⌋, but the simple argument for the upper bound no longer works, and indeed in 1983 Frankl and Odlyzko constructed families that are considerably larger.
They also conjectured that the lower bound holds if one strengthens the hypothesis by assuming that larger intersections have sizes divisible by ℓ. That is, they conjectured that for every ℓ there exists k such that if A is a collection of subsets of {1,2,…,n} such that any k sets in A have an intersection of cardinality divisible by ℓ, then |A|≤2⌊n/ℓ⌋.
This paper proves the conjecture of Frankl and Odlyzko. Along the way, the authors prove a lemma of independent interest, the statement of which has a similar flavour to that of Freiman’s theorem – hence the phrase “small doubling” in the title of the paper. Given two vectors x,y∈{0,1}n write x.y for their pointwise product, which corresponds to the intersection of the corresponding subsets of {1,2,…,n}. Also, given a subset X⊂{0,1}n, write dim(X) for the dimension of the subspace spanned by X. The lemma concerns what can be said about X if dim(X.X) is not much larger than dim(X) – more precisely, the assumption is that dim(X.X)−dim(X)≤h for some constant h.
A simple example of such a set is to take disjoint subsets A1,…,Ar of {1,2,…,n} and to take the space V of all vectors that are constant on each set Ai, and to add to it a subspace W of dimension √h of vectors supported outside A1∪⋯∪Ar. The space V+W has dimension r+√h, and the space (V+W)(V+W)=V.V+W.W=V+W.W has dimension r+dim(W.W), which is at most r+h, since if w1,…,wt is a basis of W, then the vectors wi.wj are a basis of W.W.
The lemma proved by the authors is that, at least qualitatively speaking, all examples are of this kind. They show that if dim(X.X)−dim(X)≤h, then there exist disjoint subsets A1,…,Ar⊂{1,2,…,n} with r=dim(X) such that every vector in X is constant on each Ai, and the restrictions of the x∈X to the complement of A1∪⋯∪Ar span a subspace of dimension at most 2h.