Let $\mathcal{F}$ be a family of $4$-element subsets of a set of size $5^m$, where $m$ is a fixed positive integer. If the intersection of any two sets in $\mathcal{F}$ does not have size exactly $2$, find the maximal value of $|\mathcal{F}|$.
Problem
Source: Bulgaria NMO 2024, Problem 5
Tags: combinatorics
20.04.2024 06:02
The maximum value of $|\mathcal{F}|$ is $\frac12{n \choose 2}$, where $n=5^m$. Note that this is the value at which, on average, each pair of elements is contained in exactly three subsets of $\mathcal{F}$. We start with a construction attaining equality. We can consider the set $S$ to be the set of vectors of length $m$ whose coordinates are integers modulo 5 (properly speaking, these are the points of the $m$-th dimensional affine space of order 5). For every pair of points $a$ and $b$, there is a unique line (arithmetic progression of length 5) that contains it, which is $a$, $b=a+(b-a)$, $a+2(b-a)$, $a+3(b-a)$, $a+4(b-a)$. Take the set $\mathcal{F}$ to be all subsets of lines of size 4 (all subsets of the form $\ell\setminus\{p\}$). Every pair of points is in exactly three sets of $\mathcal{F}$. Two sets of $\mathcal{F}$ which do not come from the same line have intersection at most 1, while two sets which do come from the same line have intersection 3. In no case are there two sets from $\mathcal{F}$ with intersection 2. Now we will prove that for any family $\mathcal{F}$ as in the statement we have $|\mathcal{F}|\leq\frac12{n \choose 2}$. We define a pyramid to be a family of $k\geq 3$ sets in $\mathcal{F}$ which have common intersection of size 3. We call the three elements in the common intersection the base of the pyramid. A maximal pyramid is a pyramid which contains all sets in $\mathcal{F}$ which contain the base. We say that a pair of points $ab$ is contained in a pyramid if it is contained in some set of the pyramid. In particular, one of $a$ or $b$ must be in the base of the pyramid. We make the following claims: - If a pair of points $uv$ is contained in a maximal pyramid, then every set in $\mathcal{F}$ containing $ab$ belongs to the pyramid. - Any pair of elements $uv$ not contained in a pyramid is contained in at most 3 sets in $\mathcal{F}$. - Within a maximal pyramid, on average each pair of points is contained in fewer than 3 sets in $\mathcal{F}$. For the first claim, let $abc$ be the base of the pyramid, and let $abcd_1, abcd_2, abcd_3$ be three of the elements of $\mathcal{F}$. Wlog we have either $uv=ab$ or $uv=ad_1$. In the first case, any edge containing $ab$ has intersection size at least 2 with each edge of the pyramid, so it must intersect each edge in at least one other point. Because the edge cannot contain all of $d_1d_2d_3$, it must contain $c$ and therefore contains the entire base of the pyramid. This means that the set belongs to the maximal pyramid. In the second case, every edge containing $uv$ intersects $abcd_1$ in at least two points, so it must contain one of $b$ or $c$, reducing to the previous case. For the second claim, let $uvx_1y_1$ and $uvx_2y_2$ be two sets in $\mathcal{F}$. Because the intersection of any two sets of $\mathcal{F}$ is not exactly 2, there must be a common vertex between $x_1y_1$ and $x_2y_2$, wlog $x_1=x_2=x$. No other set of $\mathcal{F}$ can contain $u$, $v$ and $x$, otherwise they would form a pyramid. Therefore it must intersect the two existing sets at $y_1$ and $y_2$, yielding a unique possibility $uvy_1y_2$, and ruling out a fourth set containing $uv$. For the third claim, if a maximal pyramid $\{abcd_i\}_{i=1}^k$ has $k$ sets, then it contains 3 pairs of vertices $ab,bc,ca$ which are each contained in all $k$ sets, and $3k$ pairs of vertices $ad_i, bd_i, cd_i$ which are each contained in one set. The average number of sets in which each pair is contained is $\frac{6k}{3k+3}<3$. We conclude that on average each pair of points is contained in at most $3$ sets of $\mathcal{F}$, proving our bound on $|\mathcal{F}|$.
03.06.2024 16:20
Answer: $\frac{1}{2}\binom{5^m}{2}$ Construction: Assign the elements to vectors in $[0,4]^m$ and reckon addition $\pmod{5}$. We will take all subsets of the form $$\{P,P+Q,P+2Q,P+3Q\}$$for all $P$ and $Q\neq 0$ in $[0,4]^m$. Notice that if terms $A,B,C,D$ form an A.P. then the only other permutations that form an A.P. are $D,C,B,A$, $B,D,A,C$, and $C,A,D,B$. Thus we have at least ${5^m(5^m-1)}/4$ distinct quadruplets. It can be readily verified that if two A.P. quadruplets share two elements then they share at least one more. Bound: We claim we can establish a involution dividing each set into two unique pairs of two. We claim in fact that we can divide each set of four into two pairs unique of all pairs that have previously been created. All the sets that have intersection three with this set must share an element outside of this set. The rest is just casework and is excluded.