1
$\begingroup$

My question arises from chapter 7 in Peter Cameron's "Combinatorics." In it, he defines a family $\mathcal F$ of subsets of a set $X$ to be regular if every point lies in a constant number $r$ of elements of $\mathcal F$. Furthermore, he says that $\mathcal F$ is intersecting if $a,B\in\mathcal F\Rightarrow A\cap B\ne\emptyset$. Exercise 5 from chapter 7 then asks the reader to prove that regular intersecting families of subsets of an $n$-set having size $2^{n-1}$ can be constructed if $n$ is not a power of $2$, and subsequently asks the reader to show that the same cannot be done if $n=2,4$, or $8$. I did this, although the proof for the second part relied on brute force checking, which brings me to my question(s):

Is it true in general that there do not exist regular intersecting families of subsets of an $n$-set having size $2^{n-1}$ if $n$ is a power of $2$? If so, how does one go about proving this?

I have a vague intuition (which seems increasingly wrong) about how to go about providing a proof, but I haven't been able to get thing to work out. To begin, I assume for a contradiction that I have a family $\mathcal F$ of subsets of an $n$-set $X$ where $\mathcal F$ satisfies the desired properties but $n$ is a power of $2$. Since any intersecting family cannot contain both a set and its complement, but we want the size of $\mathcal F$ to be $2^{n-1}$, for every $A\subseteq X$ exactly one of the following holds: \begin{align*} A&\in\mathcal F\\ (A\setminus X)&\in\mathcal F. \end{align*} Let $n=2m$, and suppose that for all $A\subseteq X$ with $|A|>m$, $A\in\mathcal F$. Notice that if you take all the subsets of a given size, they form a regular family. Since the union of some number of regular families with a family which in not regular will clearly not be regular, the subsets of size $m$ which are in $\mathcal F$ must form a regular family.

However, this means that each of the $n$ elements in $X$ must appear the same number of times in the $\frac12\binom nm$ subsets of size $m$. But $\frac12\binom{2k}k$ is even iff $k$ is not a power of $2$ (this is the previous exercise in Cameron). Thus since $n$ is a power of $2$, $\frac12\binom nm$ is odd. Thus $n$ does not divide $\frac m2\binom nm$; contradiction.

Therefore, we know that $\mathcal F$ must include some subset of $X$ with cardinality less than $m$. But (inuitively speaking) the smaller the sets you include in $\mathcal F$ are, the more trouble you will have simultaneously maintaining the regularity and intersection conditions. More rigorously, if $A\in\mathcal F$ for some $A\subset X$ with $|A|<m-1$, it follows that for all $A_i\in X$ with $A\subset A_i$ and $|A_i|<m$, we have $A_i\in\mathcal F$, as the intersection condition demands that $(A_i\setminus X)\not\in\mathcal F$ for all $i$. Furthermore it is easy to there is no intersecting regular family of subsets of size exactly $m-1$; these last two results can be combined to show that there is no intersecting family composed of subsets of size less than $m$.

Now I get stuck. Ideally, it would be possible to complete the proof by showing that there is no way to "balance out" the irregularities of the subsets of $X$ whose cardinality is less than $m$ with irregularities of the subsets of $X$ whose cardinality is greater than $m-1$. However, I can't think of any way to do this. Futhermore, what worries me (and eventually caused me to give up trying to solve the problem on my own and post it here) is the possibility that the greater degrees of freedom allowed by large enough $n$ means that the claim that I am trying to prove is not even true.

$\endgroup$
3
  • $\begingroup$ Out of interest I don't suppose you remember the rough solution to $n=8$? It's a tricky one :) $\endgroup$
    – cb7
    Mar 30 '21 at 23:46
  • $\begingroup$ @cb7 I'm afraid I don't remember, beyond what I said in the question (lots of brute force checking). Worse, I went and dug up my homework solutions from FA16, and it looks like I skipped the $n=8$ case entirely. (My guess is either I spotted an error in my solution when I decided to type it up, or possibly I just decided typing it up was too much trouble.) $\endgroup$
    – A. Howells
    Apr 1 '21 at 18:51
  • $\begingroup$ No worries - must say I didn't have much hope after such time anyway! Thanks $\endgroup$
    – cb7
    Apr 2 '21 at 0:22
1
$\begingroup$

P.J. Cameron, P. Frankl, and W.M. Kantor, Intersecting Families of Finite Sets and Fixed-point-Free $2$-Elements [PDF], shows that if $n$ is an even power of $2$, there is no transitive intersecting family on $[n]$ of cardinality $2^{n-1}$, where transitivity is strictly stronger than regularity. If $n$ is odd, the family of subsets of $[n]$ of cardinality greater than $\frac{n}2$ is a transitive (hence regular) intersecting family of cardinality $2^{n-1}$, and it follows from Theorem $\mathbf{2.8}$ that if $n$ is even and not a power of $2$, there is a regular intersecting family on $[n]$ of cardinality $2^{n-1}$. This takes care of all $n$ that are not even powers of $2$.

Problem $\mathbf{2.9}$ asks whether the same is true for even powers of $2$, the authors noting that it is not true for $n\in\{2,4,8\}$. Thus, yours was an open question as of this paper, which appeared in $1989$ in the European Journal of Combinatorics (vol. $10$, pp. $149$-$160$). I have no idea whether more is known now.

$\endgroup$
1
$\begingroup$

Some further digging turned up a paper by Aaron Meyerowitz, which appears to prove that there do exist regular intersecting families of subsets of an $n$-set having size $2^{n-1}$ if $n$ is a power of $2$ as long as $n$ is bigger than $8$ (See page 497). I haven't had the chance to read and digest the proof, but at least now I know that the result I was trying to prove is false, and (due to Brian Scott's answer) that any sort of proof is out of my league as a student in my first combinatorics class (after all, the author of my textbook tried and failed in the 1989 paper Brian links to).

http://www.sciencedirect.com/science/article/pii/0195669895900047

$\endgroup$
1
  • $\begingroup$ Nice find. (+1) $\endgroup$ Sep 18 '16 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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