Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
1  
You are asking for the maximum number of words of weight in a self-orthogonal binary code. And it seems you could reduce to the case where the minimum distance is four. (But then I am stuck.) –  Chris Godsil Nov 6 '12 at 2:45
    
Yes, that's about where I got stuck. –  Brendan McKay Nov 6 '12 at 3:26
add comment

5 Answers 5

up vote 15 down vote accepted

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.]

share|improve this answer
    
Cool! Interestingly, the LP bounds computed in my answer are tight (also for small $n$). It's not so usual occurrence. –  Dima Pasechnik Nov 6 '12 at 15:11
2  
That seems to be a close approximation of wonderful! Thanks! –  Brendan McKay Nov 6 '12 at 18:49
    
You're welcome, and thank you! What was the context for this question? –  Noam D. Elkies Nov 7 '12 at 1:28
add comment

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.

share|improve this answer
    
Maybe this just means you want to tweak your hypotheses? –  Patricia Hersh Nov 6 '12 at 2:39
    
@Patricia: Can you do it with $n$ even? That's the case I actually need and I added in the odd case as an afterthought. –  Brendan McKay Nov 6 '12 at 2:43
    
Here's a bigger example for $n=7$, which makes me wonder if for $n$ odd, maybe you just need to change the floor into a ceiling? Take $S_1=1345, S_2=2356, S_3=5617, S_4=4527, S_5=2713, S_6=1264$. –  Patricia Hersh Nov 6 '12 at 3:17
1  
@Patricia: We can get 7 sets in this case. Take the complements of the lines of a Fano geometry. –  Brendan McKay Nov 6 '12 at 3:25
3  
Actually $14$ sets for $n=8$, from the extended Hamming code: label the 8 coordinates by $({\bf Z}/2{\bf Z})^3$ and consider all subsets consisting of four elements that sum to zero. –  Noam D. Elkies Nov 6 '12 at 6:05
show 4 more comments

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.

share|improve this answer
    
Although mildly tedious, there is an argument which shows k cannot be larger than 4. Let A and B be two 3-sets which intersect in point c. Now there are at most 4 other 3-sets which intersect both A and B (and each other) in one point and miss c. Given there is at least one which misses c, use symmetry to get k is at most 4. Otherwise all the 3-sets contain c. Gerhard "And Robert's Your Mother's Brother" Paseman, 2012.11.05 –  Gerhard Paseman Nov 6 '12 at 5:37
    
Nice answer, Tony. If you build a set of 3-subsets with each pair meeting in a unique point, then you're basically building a projective plane. You either get the Fano plane, with 7 points/lines or you get a degenerate projective plane with all lines through a common point. –  Gordon Royle Nov 6 '12 at 8:51
2  
Consider 3-sets that pairwise intersect in 1 point. If three of the 3-sets form a triangle, there are no more than 7 3-sets and the only way to do that is a Fano plane (which has 7 points). We can add isolated points as well. This beats $k-1$ 3-sets in $2k-1$ points for $k\le 7$ and equals it for $k=8$. So I think this argument shows that $N$ is optimal for $k\ge 8$. I suspect that looking in more detail at $k=5,6,7$ will show they can't occur, but I'm not sure. @Gerhard: I don't get your argument. –  Brendan McKay Nov 6 '12 at 9:17
    
Continuing: Actually Gordon and Noam's example of 14 sets in 8 points also beats $N$ for $n=10$, i.e. $k=5$. So only $k=6,7$ remain. –  Brendan McKay Nov 6 '12 at 9:23
    
Brendan, sorry for the confusion. I am taking Tony's assumption of more than N sets which leads to at least k 4-sets sharing d, which is one of 2k points, and then removing d and focussing on the system of (1-intersecting) 3-sets and their union. They either all share a point c, making their union too big, or there are at most 7 of them, with their union being size 7. From there I should have said k at most 7, but I was thinking 2k at most 7+1. This fragment along with Tony's analysis and one for the 14 set system appeals to me. Gerhard "Noam's Post Seems OK Too" Paseman, 2012.11.06 –  Gerhard Paseman Nov 6 '12 at 16:36
show 4 more comments

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$.

share|improve this answer
    
indeed, an LP bound (due to Delsarte and Schrijver) should be workable for general $n$, although it's hard to guess how good it will be, without actually doing the work. –  Dima Pasechnik Nov 6 '12 at 7:40
add comment

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...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.