11
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I am not sure that there is an easy answer. This is design theory: see mathoverflow.net/questions/160787/… for a recent related question. $\endgroup$
    – Ben Barber
    Commented Mar 23, 2014 at 11:00
  • 1
    $\begingroup$ @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. $\endgroup$
    – Felix Goldberg
    Commented Mar 23, 2014 at 11:14
  • 4
    $\begingroup$ 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$? $\endgroup$
    – Lucia
    Commented Mar 23, 2014 at 14:07
  • $\begingroup$ @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? $\endgroup$
    – user58955
    Commented Mar 23, 2014 at 15:37
  • $\begingroup$ Some common names which are used in literature for such families: partial linear spaces, near linear spaces, linear hypergraphs. $\endgroup$
    – Anurag
    Commented Jan 12, 2015 at 14:26

1 Answer 1

Reset to default
15
$\begingroup$

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 Péter Frankl's ICM article Intersection Theorems for Finite Sets and Geometric Applications, which discusses many such related problems.

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 Erdős and Hanani, Rödl 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}}. $$ Rödl's paper (which is known as the nibble method) is here.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A bit sharper bound is $$m\leq \left\lfloor \frac{n}{k} \left\lfloor \frac{n-1}{k-1}\right\rfloor \right\rfloor.$$ $\endgroup$
    – Max Alekseyev
    Commented Aug 19, 2020 at 18:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .