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

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

share|improve this question
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
    
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. –  Andreas Blass Mar 10 '12 at 17:05
    
Thank you for this very clear answer! –  Sean Eberhard Mar 10 '12 at 17:47
add comment

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.