Covering with most possible equal size subsets having pairwise singleton intersections

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

Solution 1:

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

Solution 2:

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

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

Solution 3:

Adding to @hardmath's aside. An interesting family of solutions in addition to the finite projective spaces are the dual finite affine planes (2-d vector spaces) over finite fields: $GF(q)^2$ . In those, it holds that

(a) two distinct points share exactly one line.

(b) each line contains exactly $q$ points,

(c) each point is incident with exactly $q+1$ lines.

(d) There are $q(q+1)$ total lines, and $q^2$ total points.

Not every two lines intersect, but as the accepted answer's aside mentioned, if we take the dual space, (a) implies (1p), and (c) implies (1u). So to connect to the original question, the set $S$ is the set of all lines. The subsets would be indexed by each point $i$:

$S_i=\{l \in S | I(i,l)\}$ - the set of lines intersecting with point $i$.

$\forall_i|S_i|=q+1$. And $S_i \cap S_{j}=$the single line connecting $i$ and $j$, so $|S_p \cap S_{p'}|=1$.

So this is a family of solutions with: $x=q(q+1),\space y=q+1,\space n=q^2$ for all $q$ which is a prime power. Not 100% sure this is maximal, though it sounds like it should be.

Edit: Just realized that in the same way that the affine plane is obtained from the projective plane by removing one line and all the points incident with it, so we can continue to remove additional lines and all the points incident with them from the affine plane. Each two remaining points would still be connected with exactly one line, but not every line will contain an equal number of points, but this wasn't a requirement in the original question. This is pretty wasteful, since it removes many points for each line, but maybe still finds solutions.