# maximum size of intersecting set families

Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that (1) $|S_i| = k$ for all $i$, (2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$. What's the maximum possible value of $m$?

(I just need to know the growth order of $m$ depending on $n$ and $k$. For instance, when $k=2$, we have $m = \binom{n}{2} \sim n^2$.)

I tried to look it up in the literature, but it looks like this is different from the classical intersecting family that I have an upper bound on the size of intersection of a pair of sets instead of a lower bound.

-
I am not sure that there is an easy answer. This is design theory: see mathoverflow.net/questions/160787/… for a recent related question. – Ben Barber Mar 23 '14 at 11:00
@BenBarber Actually, design theory deals with families that have more structure than OP is assuming. It's more of a near-linear space thing actually, imho. – Felix Goldberg Mar 23 '14 at 11:14
Every $k$ element set has $\binom{k}{2}$ subsets of size $2$, and all the subsets of size $2$ from the $m$-sets we have should be distinct. Therefore $m\binom{k}{2} \le \binom{n}{2}$, or $m\le n(n-1)/(k(k-1))$. Are you looking for such upper bounds for $m$, or for constructions giving lower bounds for $m$? – Lucia Mar 23 '14 at 14:07
@Lucia Yes, I'm looking for such upper bounds. Of course the smaller the upper bound the better. Your upper bound is of order $n^2/k^2$, which is better than the $n^2/k$ that a simple inclusion-exclusion gives in an answer. This looks possibly a right order. Do you see a matching lower bound of the same order? – user58955 Mar 23 '14 at 15:37
Some common names which are used in literature for such families: partial linear spaces, near linear spaces, linear hypergraphs. – Anurag Jan 12 '15 at 14:26

I noted the simple upper bound $m\le \binom{n}{2}/\binom{k}{2}= n(n-1)/(k(k-1))$ in my comment above. It seems that Wilson proved that if $k-1$ divides $n-1$, and $\binom{k}{2}$ divides $\binom{n}{2}$ then for large $n$ this upper bound is attained. See page 1424 of this interesting ICM article of Peter Frankl which discusses many such related problems: http://www.mathunion.org/ICM/ICM1986.2/Main/icm1986.2.1419.1430.ocr.pdf
More generally, let $m(n,k,t)$ denote the size of the largest collection of $k$ element subsets of $\{1,\ldots, n\}$ such that any two sets intersect in at most $t-1$ elements. (Or equivalently, every $t$ element set is a subset of at most one set from our collection.) The simple argument in my comment gives that $m(n,k,t)\le \binom{n}{t}/\binom{k}{t}$. Proving a conjecture of Erdos and Hanani, Rodl proved that for fixed $k$ and $t$ and as $n\to \infty$ one has $$m(n,k,t) \sim \frac{\binom{n}{t}}{\binom{k}{t}}.$$ Rodl's paper (which is known as the nibble method) is here: http://ac.els-cdn.com/S0195669885800238/1-s2.0-S0195669885800238-main.pdf?_tid=f54a0e4c-b2d2-11e3-8c9e-00000aab0f26&acdnat=1395610668_3702554a6f59cc9472eb480547147639