Intersecting 4-sets - MathOverflow

Intersecting 4-sets

2012-11-06T02:23:03Z

Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements?

To see that $N$ is achievable, choose $\lfloor n/2\rfloor$ disjoint pairs and then take each 4-set consisting of two of the pairs. But this is not the unique way of doing it in general.

EDIT: Patricia has provided a counterexample with $n=7$, so I'll remove odd $n$ from the question. Is there a counterexample for even $n$?

Answer by Patricia Hersh for Intersecting 4-sets

2012-11-06T02:35:59Z

How about $n=7$, so $N={3\choose 2} = 3$, with subsets $S_1 = \{ 1,2,3,4\}$ and $S_2 = \{ 1,2,5,6\} $ and $S_3 = \{ 3,4,5,6 \} $ and $S_4 = \{ 1, 3, 5, 7 \} $.

Added later: this example can be modified to $n=8$ by taking $S_1 = \{ 1,2,3,4 \}, $ $S_2 = \{ 1,2,5,6\} $, $S_3 = \{ 1,2,7,8 \} $, $S_4 = \{ 3,4,5,6\} $, $S_5 = \{ 3,4,7,8 \} $, $S_6 = \{ 5,6,7,8 \} $ and $S_7 = \{ 1,3,5,7\} $ while $N=6$ in that case.

Answer by Tony Huynh for Intersecting 4-sets

2012-11-06T03:47:03Z

For all even $n \geq 16$, $N:=\binom{n/2}{2}$ is the right answer.

Semi-proof. Let $n=2k$ and observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $1$ element. Now I think that for large $k$ this is not possible, although I am not an extremal set theorist. I would guess that for large $k$ the maximum size of such a family is achieved by taking a family of disjoint $2$-sets and adding the same point to each set. Such a family only has size $k-1$, which would be a contradiction.

Updated proof via Brendan McKay. I claim that for all even $n \geq 16$, $N$ is the right answer. From the semi-proof, it suffices to show that for any $k \geq 8$, the size of the largest family $\mathcal{F}$ of $3$-subsets of $[2k-1]$ (any two of which meet in exactly one point) is at most $k-1$. If $\mathcal{F}$ does not contain a triangle, this is true. So suppose, $123, 345, 561 \in \mathcal{F}$. If every member of $\mathcal{F}$ is contained in $[6]$ we are done. So there exists a set $F \in \mathcal{F}$ so that $F \cap [6] \neq \emptyset$. It follows that $|F \cap [6]|=2$, and by symmetry we may assume $F=174$. Now if all members of $\mathcal{F}$ are contained in $[7]$, then $\mathcal{F}$ is a subfamily of the Fano plane and we are done. Thus, there is a member $F'$ such that $|F' \cap [7]| =2$. Since the lines $123, 561$ and $174$ meet only at the point $1$, and $F'$ must contain a point from each of them, it follows that $1 \in F'$. But since these three lines also contain all points in $[7]$, $F'$ contains no other points of $[7]$. Thus, $|F'\cap [7]|=1$, a contradiction.

Answer by gordon-royle for Intersecting 4-sets

2012-11-06T04:03:29Z

Here's 14 sets on 8 points:

{ 2, 5, 7, 8 }, { 2, 3, 6, 7 }, { 2, 3, 4, 5 }, { 2, 4, 6, 8 }, { 1, 2, 4, 7 }, { 1, 2, 3, 8 }, { 3, 5, 6, 8 }, { 1, 2, 5, 6 }, { 1, 3, 5, 7 }, { 1, 4, 5, 8 }, { 3, 4, 7, 8 }, { 1, 6, 7, 8 }, { 1, 3, 4, 6 }, { 4, 5, 6, 7 }

It is a clique problem in the fusion of 2 classes of an association scheme, so we might be able to get bounds. But given that we don't even know the maximum size of cliques in Johnson graphs, it may be difficult to give the exact answer.

But its not $\binom{n/2}{2}$.

Actually, I retract that. It might be $\binom{n/2}{2}$, but not for small $n$.

Answer by Dima Pasechnik for Intersecting 4-sets

2012-11-06T14:29:27Z

It looks like the conjecture is very close to be right (i.e. $N$ is an upper bound) for $n\geq 12$, as the linear programming (LP) bound equals $N$ for even $n$ even, $500\geq n\geq 12$. When $n$ is odd, there is a gap between the LP bound and $N$, but this is most likely to do with the fact that the optimal solutions are non-integer. The corresponding LP has just 2 variables and 6 constraints, so it should be perfectly possible to derive it by hand for general $n$.

Here one can get Sage code to solve the LP in question: e.g. (it's actually an arbitrary precision solver, it only shows the LP with the floating point...)

sage: load j.sage
sage: A,p,bd=delsarte_bound_J(130,4,[1,3], return_data=True)
sage: bd
2080
sage: binomial(130/2,2)
2080
sage: p.show()
Maximization:
x_0 + x_1 + x_2 + x_3 + x_4
Constraints:
constraint_0: 1 <= x_0 <= 1
constraint_1: 0 <= x_1 <= 0
constraint_2: 0 <= x_3 <= 0
constraint_3: -10836.0 x_0 - 8041.0 x_1 - 5246.0 x_2 - 2451.0 x_3 + 344.0 x_4 <= 0
constraint_4: -52006500.0 x_0 - 25384125.0 x_1 - 7848854.0 x_2 + 599313.0 x_3 - 39624.0 x_4 <= 0
constraint_5: -682329375.0 x_0 - 162459375.0 x_1 + 5285345.0 x_2 - 192855.0 x_3 + 8385.0 x_4 <= 0
constraint_6: -1.79043228e+11 x_0 + 1420978000.0 x_1 - 22735648.0 x_2 + 550056.0 x_3 - 17888.0   x_4 <= 0
Variables:
   x_0 is a continuous variable (min=0, max=+oo)
   ...
   x_4 is a continuous variable (min=0, max=+oo)

Unfortunately, the code will only work in an experimental version of Sage; one needs version 5.4 (with is only in "release candidate" state now), and install this ticket, which is not for faint-hearted...

Answer by Noam D. Elkies for Intersecting 4-sets

2012-11-06T14:45:50Z

The conjectured maximum of $N = \binom{\lfloor n/2\rfloor}{2}$ is correct except for $n=7$, when the maximum is $7$, and $8 \leq n \leq 11$, when the maximum is $14$. The maximal configuration is unique except for $n=12$, $13$, $15$, $16$, and $17$.

Let $L$ be the subgroup of ${\bf Z}^n$ generated by $(2{\bf Z})^n$ and the characteristic functions $e_i + e_j + e_k + e_l$ of each 4-set $\lbrace i,j,k,l \rbrace$ in our family $\cal F$ of subsets of $\lbrace 1,2,\ldots,n \rbrace$. Give $L$ the structure of lattice using the inner product $$ \langle x, y \rangle = \frac12 \sum_{i=1}^n x_i y_i $$ (i.e. half the usual inner product). Then $L$ is generated by vectors $2e_i$ and $e_i + e_j + e_k + e_l$ of norm $2$, any two of which are either orthogonal or have inner product $1$. Hence $L$ is an even integral lattice, with at least $2n+16|{\cal F}|$ roots (vectors of norm 2), namely $\pm 2 e_i$ and $\pm e_i \pm e_j \pm e_k \pm e_l$ for $\lbrace i,j,k,l \rbrace \in \cal F$. Equality holds iff $\cal F$ contains every tetrad $\lbrace i,j,k,l \rbrace$ such that $e_i + e_j + e_k + e_l \in L$.

Now we can use the theory of root systems to partition the set of roots of $L$ into mutually orthogonal simple root systems. Since $L$ contains the root lattice $A_1^n = (2{\bf Z})^n$, the only possible components of the root system of $L$ are $A_1$, $D_{2k}$ for $k \geq 2$, and the exceptional systems $E_7$ and $E_8$. These contribute respectively $0$, $\binom{k}{2}$, $7$ and $14$ tetrads to $\cal F$. Namely, each $A_1$ corresponds to a coordinate that does not appear in $\cal F$; each $D_{2k}$ corresponds to $k$ pairs of coordinates paired in each of $\binom{k}{2}$ possible ways; and $E_7$ and $E_8$ correspond to the tetrads of the Hamming $[7,3,4]$ and extended Hamming $[8,4,4]$ codes respectively.

It is now elementary bookkeeping to obtain the maximum configuration.

$\circ$ Except for $7 \leq n \leq 11$, the maximal $|{\cal F}|$ is $\binom{k}{2}$ for $n = 2k$ or $n = 2k+1$, attained by the $D_{2k}$ configuration.

$\circ$ For $n=7$, the maximum of $7$ is attained by the $E_7$ (Hamming) configuration, and for $8 \leq n \leq 11$, by $E_8 \oplus A_1^{n-8}$ (extended Hamming).

$\circ$ For $n=12$ ($n=13$), the maximum of $15$ is attained by both $D_{12}$ ($D_{12} \oplus A_1$) and $E_8 \oplus D_4$ ($E_8 \oplus D_4 \oplus A_1$).

$\circ$ For $n=15$, the maximum of $21$ is attained by both $D_{14} \oplus A_1$ and $E_8 \oplus E_7$.

$\circ$ Finally, for $n=16$ ($n=17$), the maximum of $28$ is attained by both $D_{16}$ ($D_{16} \oplus A_1$) and $E_8 \oplus E_8$ ($E_8 \oplus E_8 \oplus A_1$).

[The lattice $L$ corresponds via "construction A" to a binary linear code generated by $\cal F$, which is doubly even by hypothesis. Koch developed a theory of "tetrad systems" of such codes that could be used to give a more direct but less familiar derivation of this answer.]