Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?
Collisions in independent hashing
computability;data structures;probability theory;hash;hash tables
You can upper-bound your probability using a union bound.  In particular,$$\Pr[\exists x \in S . \phi(x)] \le \sum_{x \in S} \Pr[\phi(x)].$$Using a union bound we obtain ${M^s \choose 2}$ terms in the sum, and each term is upper-bounded by $1/N^s$, so we find that your probability is at most$${M^s \choose 2}/N^s.$$If $M < \sqrt{N}$, then this probability will be at most $1/2$.  If $M \gg \sqrt{N}$, then this probability is close to $1$.(Qualitatively, this upper bound is fairly close to tight for a wide range of settings of $M,N$.  I am not going to prove this fact, but you can take my word on it.  So there's not much hope for a significantly better bound using some other proof technique.)In short: as Yuval Filmus says, unless $M$ is very small, your event is actually pretty likely.No, something stronger than $s$-independence will not help.  Even if you assume that $h$ is generated uniformly at random from the set of all hash functions with the right signature (something that is not actually implementable), you don't get a much better bound.The only plausible approach I can see is to choose a hash function $h$ that does not have any collisions at all: e.g., choose $h$ from a family of injections, or use a perfect hash.  Each of these has serious shortcomings: the former requires $M<N$, and the latter typically requires you to know in advance the full set of values that you will ever compute $h$ on.