3
$\begingroup$

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$.

$\endgroup$
8
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ This, along with the projective plane example, was actually going to be in a paper I'm writing. Fortunately, the main topic of the paper is something else, so the paper won't lose much by omitting this. $\endgroup$ – Andreas Blass Mar 10 '12 at 17:05
  • $\begingroup$ 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$. $\endgroup$ – Sean Eberhard Aug 14 '16 at 12:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.