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

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.

share|improve this question
    
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 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 at 11:14
2  
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 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 at 15:37

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer

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.