Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Today I came up with this problem:

Find all natural numbers $n$ such that there exist a family of $3$-element subsets of the set $\{1,2,...,n\}$ like $\mathbf F$ such that:

a) For all distinct $1\le a,b \le n$ there exists a unique element of $\mathbf F$ like $\mathbf A$ such that it contains both $a$ and $b$.

b) If $1\le a,b,c,x,y,z \le n$ are distinct and $\{a,b,x\},\{b,c,y\},\{c,a,z\}\in \mathbf F$, then $\{x,y,z\}\in \mathbf F$.

It's easy to prove that $n$ should be of forms $6k+1$ or $6k+3$. For $n=3$ it's obvious and for $n=7$ I found this example:

$\{1,2,4\},\{2,3,5\},\{3,1,6\},\{4,5,6\},\{7,1,5\},\{7,2,6\},\{7,3,4\}$.

But I couldn't go any further. Would anyone please tell me, how can I construct such examples for larger $n$'s? Or prove there is no such examples? Thanks

share|improve this question
1  
A system of subsets that satisfies (a) is called a "Steiner (2,3,n) system" (or a Steiner triple system on $n$). Haven't thought about whether condition (b) is then forced. You can find information on Steiner systems in Wikipedia. –  Arturo Magidin Mar 25 '12 at 4:56
2  
A family of $3$-element subsets satisfing your condition $1$ is what's called a Steiner triple system. The example you found for $n=7$ is the unique such system. A configuration such as the one in your 2nd condition is what is called a Pasch configuration. Google for these keywords :) –  Mariano Suárez-Alvarez Mar 25 '12 at 4:58
    
Your $n=7$ example is known as the Fano plane. It shows up often in combinatorial constructions. –  Jyrki Lahtonen Mar 25 '12 at 7:19
    
It would be interesting if you edited the question to explain how you came to this problem, by the way! –  Mariano Suárez-Alvarez Mar 25 '12 at 9:03

1 Answer 1

up vote 3 down vote accepted

Let $E$ be a finite set, and let $S$ be a set of $3$-element subsets of $E$ satisfying your conditions. Let $0$ be a new symbol and let $V=E\cup\{0\}$.

Let $\star:V\times V\to V$ be the operation defined as follows:

  • first, the element $0$ is a zero for $\star$, so that $0\star v=v\star 0=v$ for all $v\in V$;

  • second, if $e\in E$, we let $e\star e=0$;

  • finally and most interestingly, if $x$, $y\in E$ are different, we define $x\star y$ to be the unique element of $E$ such that $\{x,y,x\star y\}$ is an element of $S$.

I claim that your second condition implies that $\star$ is associative—this can be proved by considering several cases (reflecting the form of the definition of $\star$) and I will leave all the fun to you. In any case, it follows immediately from the construction that then $(V,\star,0)$ is in fact an abelian group of exponent $2$. In particular, its order is of the form $2^m$ for some $n$. Consequently, $E$ has $2^m-1$ elements.

More: it follows from this construction that we can reconstruct all such systems $(E,S)$. Indeed, we can deduce from all this that for each $m\geq1$ there is exactly one Steiner triple system satisfying your 2nd condition of order $2^m-1$, which can be constructed as follows: $E$ is the set of points of the projective space $P^m(\mathbb F_2)$ of dimension $m$ over the field $\mathbf F_2$ with two elements, and $S$ is the set of projective lines in $E$. There are no systems satisfying your conditions for other orders.

N.B. These things can be constructed concretely pretty easily. Given $m$, let $E=\{1,\dots,2^m-1\}$, which is precisely the set of positive integers which can be represented in binary with at most $m$ digits and let $S$ be the set of all $3$-element subsets $\{a,b,c\}$ of $E$ such that $a\oplus b\oplus c=0$, where $\oplus$ denotes the bitwise XOR operation.

share|improve this answer
    
+1: I want to remark that the construction in the last paragraph is the set of (supports of) words of weight 3 in a Hamming code. –  Jyrki Lahtonen Mar 25 '12 at 7:23

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.