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.

Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = \cup S_i$, and I'm embarrassed that I forgot to include that) such that:

  • $ |S_i| = y, \forall 1 \le i \le n$ (The cardinality of each subset is fixed)
  • $|S_i \cap S_j| = 1, \forall 1 \le i,j \le n, i \neq j$ (Each subset has exactly 1 element in common with any other subset)

Edit: The second condition above excludes the possiblility of a pairwise disjoint division of subsets.

Is there a way to determine the maximum value of $n$ (the number of possible subsets), given $x$ and $y$?

share|improve this question
    
Are there any constraints on $x$ and $y$? For example with $x = 1$ and $y = 2013$ you might have some trouble doing that. –  dtldarek Jul 12 '13 at 13:35
    
@dtldarek If we don't require $S=\bigcup S_i$, then this merely implies that $n=0$ is maximal for such $(x,y)$. –  Hagen von Eitzen Jul 12 '13 at 13:37
    
@HagenvonEitzen Well, I would say that the phrase "divide the set $S$ into subsets..." does imply $S = \bigcup S_i$. –  dtldarek Jul 12 '13 at 13:39
    
@dtldarek Then again, I'd also say that divide implies $S_i\cap S_j=\emptyset$ ... –  Hagen von Eitzen Jul 12 '13 at 13:40
2  
Whatever it is, I'd be great if OP could clarify ;-) –  dtldarek Jul 12 '13 at 13:42

2 Answers 2

Update: After filling up several sheets of scratch notes, and much Internet browsing, it dawned on me that the dual of the designs considered here are pairwise balanced designs on $n$ "points" (namely the sets $S_i$ described in the Question). Another way to put this insight is to say that if the original points of $S$ which are covered by only one set $S_i$, the reduced design that remains would be the dual of a linear space, rehabilitating the idea I broached as an Aside at the bottom of my first post. I'm working on integrating this new insight into a revised Answer.


The combinatorial objects described here can be approached from several directions. Perhaps most natural is (finite) incidence geometry, treating the finite set $S$ as the set of $x$ "points" and the $n$ subsets $S_i$ as "lines". Other approaches include covering 1-designs and hypergraph incidence matrices.

A partial linear space is an elementary kind of incidence geometry, satisfying two (redundant) axioms:

(1a) Two distinct lines meet in at most one point.

(1b) Through two distinct points there exists at most one line.

Here we have two specializations, specifically that:

(1p) Two lines meet in exactly one point.

(2u) Every line contain exactly y points.

Terminology for this precise combination of specialized partial linear spaces does not seem to be well established. For (2u) one can speak of a uniform partial linear space, those whose "block sizes" are uniform (equal). For (1p) the term that comes to mind most readily would be "projective", as projective planes are well-known for their absence of parallel lines (lines that do not meet), but trying to use that term here proves tricky because a projective geometry has also the unwanted property that there is one line through every pair of distinct points. So far the most concise yet precise phrase I can coin for the objects under study is uniform partial linear spaces with no parallel lines.

If the goal is to obtain as many lines $n$ as possible, then certainly the finite projective planes provide one family of maximal examples. It is well-known that a projective plane of order $q$ exists for each prime power $q$, and it is conjectured that these are the only ones. For a projective plane of order $q$, there are $x = q^2 + q + 1$ points, each line contains $y = q+1$ points, and there are $n = x$ equally many lines as points.

Unfortunately this is essentially a one-parameter family of solution sizes (although two projective planes of equal order and size need not be isomorphic). Designs with fewer lines than points are possible, and these must be considered where $x$ and $y$ differ from the projective plane possibilities. I've assembled a short table of the maximum $n$ for certain small values of $x$ and $y$ (still preliminary), highlighting the projective plane cases with a dagger ($\dagger$).

$$ \begin{array} {|r|c|c|c|c|} \hline \text{ x \ y}& 2 & 3 & 4 & 5 \\ \hline 2\; & 1 & \text{---} & \text{---} & \text{---} \\ 3\; & 3^\dagger & 1 & \text{---} & \text{---} \\ 4\; & 3 & \text{---} & 1 & \text{---} \\ 5\; & 4 & 2 & \text{---} & 1 \\ 6\; & 5 & 4 & \text{---} & \text{---} \\ 7\; & 6 & 7^\dagger & 2 & \text{---} \\ 8\; & 7 & \text{---} & \text{---} & \text{---} \\ 9\; & 8 & 4 & 3 & 2 \\ 10\; & 9 & \text{---} & 4 & \text{---} \\ 11\; & 10 & 5 & 4 & \text{---} \\ 12\; & 11 & \text{---} & 5 & 3 \\ 13\; & 12 & 6 & 13^\dagger & 3 \\ 14\; & 13 & \text{---} & 7 & 4 \\ 15\; & 14 & 7 & \text{?} & 6 \\ 16\; & 15 & \text{---} & \text{?} & \text{?} \\ \hline \end{array} $$

Aside: A linear space is a partial linear space satisfying additional assumptions:

(L1) Two distinct points share exactly one line.

(L2) Every line contains at least two points.

(L3) There are at least two lines.

At first it appears we might adopt the terminology of dual linear space, a derived notion where the roles of "point" and "line" interchange. Then (L1) would become the (1p) that we want (and (L3) is unobjectionable). Unfortunately (L2) would in dual terms say every point is covered by at least two lines, which though not necessarily a bad thing if you want more lines, still lies apart from the assumptions proscribed by the Question. It also makes it awkward to include the term "uniform" in a phrase as ambigous whether we mean the dual of a uniform (partial) linear space or a dual linear space that happens to be uniform (it is this latter we would want to convey).

share|improve this answer

To add to what @hardmath had written, Fisher's inequality guarantees $n \leq x$.

See, e.g., here for a statement and a proof.

share|improve this answer
    
Thanks! I thought I'd said so, but clearly I got lost wandering around in the vast realm of incidence structures. –  hardmath May 14 at 11:42

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.