Let $A$ be a set of cardinality $4n$. We define a pairing in $A$ to be a partition of $A$ into sets of cardinality $2$. What is the minimum number of pairings in $A$ such that every subset of $A$ of cardinality $4$ is the union of two pairs from at least one pairing?


This question is motivated by the computational problem of producing such a set of pairings. An answer may be a proof that the minimum number of pairings with this property is or is not $\mathcal O (n^2)$.



Minimum number of pairings that make all quadruples
It is a nice exercise in number theory.


Let $p$ be a prime slightly above $4n$. Let $1\le x<y<z<t\le 4n$.


Note that $0<(y+t)-(x+z)<4n<p$.


Now, there exists $a\in \mathbb Z\_p$ such that $(x+a)(z+a)=(y+a)(t+a)$ in $\mathbb Z\_p$ (this equation only pretends to be quadratic; in fact it is linear in $a$ with non-zero (in $\mathbb Z\_p$) coefficient $(y+t)-(x+z)$ at $a$). Also, we cannot have both parts $0$ simultaneously. Thus, if we consider $p^2-p$ pairings $P\_{a,b}$ in $\mathbb Z\_p\setminus\{-a\}$ given by $u\sim v\Longleftrightarrow (u+a)(v+a)=b$, we will have $x\sim z$ and $y\sim t$ simultaneously for some $a\in\mathbb Z\_p, b\in\mathbb Z\_p^\*$. To reduce $P\_{a,b}$ to $[1,4n]$, just make all pairs in $P\_{a,b}$ for which both $u,v$ are in the range and then pair the remaining set of numbers of even cardinality in any way you want.


That seems pretty economical. If $N=4n$, then it is essentially $N^2$ while the trivial lower bound is roughly speaking $(N^4/24)/((N/2)^2/2)=N^2/3$. You can try to fight for this $3$, of course, but without me :-)


