Is there any english, preferably simple proof of Deza's theorem?

159 Views Asked by At

One of the theorem I find most fasicnating is Deza's theorems: We are given $S$, a $d$ uniform family of subsets of $[n]$, such that there exists a number $a$ so that for any two elements of $S$, $s_1$ and $s_2$, their intersection is of size $a$. Deza's theorem then says that if $|S|>d^2-d+1$, then $S$ is a sunflower: the intersection of all its elements is the same as the intersection of any $2$ of its elements. This is tight in some cases (for example when we have a project plane, its lines give a tight example).

However, for some darn reason, his original paper was in French, and I can find no good source online. Help please.

1

There are 1 best solutions below

1
On BEST ANSWER

Here are some statements of results from the paper. Each result here has its own proof, some long, some short. If you can say one proof in particular that you need translated, I'll see what I can do. Keep in mind, I don't actually know French, so I make no guarantees as to speed.

Lemma 3.1: For every $(m,2k,n)$-code, and every integer $1\leq s\leq n$, we have: $t_s(m-t_s)\leq mk$.

(very short proof)

Lemma 3.2: For every $(m,2k,n)$-code $X$ such that:

$$t_s\leq \frac{m+2k-1}{k+1}-1$$

(for all $1\leq s\leq n$), we have $t_s\leq 1$ for all $1\leq s\leq n$.

(long proof)

Lemma 3.3: Every $(m,2k,n)$-code, such that $m\not\in[4,k^2+k+2]$ satisfies the condition $t_s\leq 1$ for $s\in [1,n]$.

(fairly short proof, using 2 previous lemmas)

Lemma 3.4: An $(m,2k,n)$-code is trivial if and only if $t_s\leq 1$ for $1\leq s\leq n$.

(shortish proof)

Lemma 3.5: If $m\geq 4$ and there exists a non-trivial $(m,2k)$-code, then, for every $m'\in[4,m]$, there exists a non-trivial $(m',2k)$-code.

(shortish proof)

Lemma 3.6: If there exists a non-trivial $(m,2k)$-code, we have $N(m,k)<mk$. Otherwise, we have $N(m,k)=mk$.

(shortish proof)

After this, there's a paragraph saying it would be interesting to find certain spectra of numbers for which non-trivial codes exist, and then the real proof occurs in a paragraph on p. 350 beginning "Passons maintenant..."

Statement of the main theorem:

Theorem 1.1: Let $m$ and $k$ be two integers such that $m>k \geq 1$; then we have:

i) There exists a number $N(m,k)$ such that a necessary and sufficient condition for the existence of an $(m,2k,n)$-code is that $n\geq N(m,k)$

ii) $N(m,k)\leq mk$ and there exists a number $f(k)$ such that $f(k)\geq 4$ and $N(m,k)=mk$ if and only if $m\in [4,f(k)]$

iii) There exists a trivial $(m,2k)$-code and its length is greater than or equal to $mk$. There exists an $(m,2k)$-code, different from a trivial code, if and only if $m\in[4,f(k)]$.

iv) $f(k)\leq k^2+k+2$ and $f(k)=k^2+k+2$ if there exists a $PG(2,k)$.