# Intersecting group orbits

Given a group $G$ acting transitively on a set $X$ of $n$ points, consider the induced action on the set $\binom{X}{k}$ of $k$-element subsets of $X$. Obviously, if $k>n/2$, the orbit of any set is intersecting, i.e., every two sets in the orbit intersect. How much better than $n/2$ can we do?

For an example to see what I am talking about, considering the action of $\text{PSL}_3(\mathbf{F}_p)$ on lines in $\mathbf{P}^2(\mathbf{F}_p)$ gives an example with $k\approx \sqrt{n}$. Is $k\approx n^{1/3}$ possible? What about $k\approx \log n$?

I am interested in asymptotics, so take $n$ to be large but otherwise however you like. You may also take $G$ to be any transitive subgroup of $S_n$.

The square root of $n$ is the best you can get. To see this, consider a set $A$ whose size $k$ is as small as possible for an intersecting orbit. For any $x\in X$, let $c$ be the number of sets from the orbit of $A$ that contain $x$; as the action is transitive, you get the same $c$ for every $x$. Now count in two ways the pairs $(y,B)$ such that $B$ is in the orbit of $A$ and $y\in B-A$. There are $n-k$ possibilities for $y$ (all the points in $X-A$), and for each of these there are $c$ possibilities for $B$, so the total count is $(n-k)c$.
For the second count, notice that each relevant $B$ must intersect $A$ (because we have an intersecting orbit) but be distinct from $A$. Each point $x\in A$ belongs to $c-1$ such sets $B$, so there are at most $k(c-1)$ such $B$'s altogether. (It's "at most" not "exactly" because some $B$ might intersect $A$ at more than one point $x$.) Each such $B$ contributes at most $k-1$ pairs $(y,B)$ to our count, because $B$ has $k$ elements, at least one of which is in $A$ and so cannot serve as $y$. Thus, the total count is at most $k(c-1)(k-1)$.
Comparing the two counts, we get $$(n-k)c\leq k(k-1)(c-1)\leq k(k-1)c.$$ Cancelling $c$ and then $-k$, we get $n\leq k^2$.
• I needed this nice fact again today. For reference, here is an argument I find easier to remember. Fix a set $A$ as above, and pick $g$ uniformly at random from $G$. If $A$ is intersecting then $A \cap gA$ is always nonempty, so there exists $x,y \in A$ such that $gx = y$. The probability of this event is $1/n$, and there are $k^2$ such events, so $k^2/n \geq 1$. – Sean Eberhard Aug 14 '16 at 12:23