1
$\begingroup$

Suppose we have a set of $n$ elements. We want to know the maximum number of subsets of $3$ elements we can find of this set such that no two subsets have an intersection with $2$ or more elements.

The question arises from trying to count the number of subgroups isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_2$ in a group with $n$ elements of order $2$ such that the product of any two such elements has also order $2$.

$\endgroup$
6
  • $\begingroup$ Actually you title is unclear. There are eight subsets and you want the ones that are disjoint. Disjoint from what? Or whose intersection is a singleton. Intersection with what? Do you men how many pairs of subsets? Or how many sets of subsets? $\endgroup$
    – fleablood
    Commented Jan 9, 2018 at 22:20
  • $\begingroup$ Subsets of what? $\endgroup$
    – BallBoy
    Commented Jan 9, 2018 at 22:21
  • $\begingroup$ ... oh.... do you mean the subsets have three elements? Or the super set has three elements. $\endgroup$
    – fleablood
    Commented Jan 9, 2018 at 22:22
  • $\begingroup$ @bof yeah that is right, sorry for the confusion $\endgroup$ Commented Jan 9, 2018 at 22:24
  • $\begingroup$ I interpretted it very differently than bof. I assume the OP meant you have a set $U$ with $3$ elements, and he wants to know how many pairs of subsets $A \subset U$ and $B \subset U$ with $|A\cap B| = 1$ or $2$. $\endgroup$
    – fleablood
    Commented Jan 9, 2018 at 22:24

1 Answer 1

1
$\begingroup$

The maximum possible size of a family of $3$-element subsets of an $n$-element set, no two of which have more than one element in common, is $$\left\lfloor\frac n3\left\lfloor\frac{n-1}2\right\rfloor\right\rfloor-\varepsilon$$ where $\varepsilon=1$ if $n\equiv5\pmod6$ and $\varepsilon=0$ otherwise. This is OEIS sequence A001839.

References.

T. P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. J. 2 (1947), 191–204.

J. Schönheim, On maximal systems of $k$-tuples, Studia Sci. Math. Hungar. 1 (1946), 363–368.

Richard K. Guy, A problem of Zarankiewicz, in: Theory of Graphs (Proc. Colloq., Tihany 1966; P. Erdős and G. Katona, eds.), Academic Press, New York, 1968, pp. 119—150.

Joel Spencer, Maximal consistent families of triples, J. Combin. Theory 5 (1968), 1–8.

J. C. Swift, Quasi Steiner systems, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. 44 (1968), 563–569.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .