5
$\begingroup$

Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?.

Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=\{Y\subset X: Y\text{ contains exactly $4$ elements}.\}$$

I want to partition $\mathcal A$ into groups $A_1,A_2,\dots, A_m\subset \mathcal A$ (each of them is a collection of $4$-subsets of $X$) such that $\bigcup_{i=1}^m A_i=\mathcal A$ and such that the intersection of any two distinct $4$-subsets in each $A_k$ has cardinality at most $1$, i.e. such that for all $i\in\{1,\dots,m\}$ and $Y_1, Y_2\in A_i$, we have $$Y_1\neq Y_2 \implies \lvert Y_1\cap Y_2\rvert \le 1.$$

My question: What can be said about the smallest $m$ (depending on $n$) such that such a partition exists?


My thoughts: I was expecting that each $A_i$ can contain "roughly" $\frac n4$ elements, so we would have $$m(n)=\Theta\left(\frac{\binom n4}{\frac n4}\right)=\Theta(n^3).$$ In particular, we would have $m(n)\le c n^3$ for some constant $c\in\mathbb R$.

However, I am neither sure if this is correct, nor how to formalize this.

$\endgroup$
  • 5
    $\begingroup$ For every pair of elements of $X$, the 4-subsets containing them must be in distinct $A_i$, implying that $m(n)\geq \frac{(n-2)(n-3)}2$. $\endgroup$ – Max Alekseyev Jun 14 at 17:09
  • 1
    $\begingroup$ We can show that if $n$ is a power of an odd prime then $m(n)\le n^2$. $\endgroup$ – Alex Ravsky Jun 15 at 18:53
  • $\begingroup$ By the way, $\binom X 4$ is a handy and fairly well understood notation for the set of $4$-subsets of $X$. $\endgroup$ – LSpice Jun 16 at 16:00
7
$\begingroup$

This problem can be reformulated in terms of graph coloring:

Let the graph $G=(V,E)$, $V=\mathcal A$, $(x,y)\in E \leftrightarrow x \cap y \geq 2$

Then a partition of $\mathcal{A}$ into groups $A_1,A_2,…,A_m$ corresponds to a $m$-coloring of $G$.

The graph $G$ has degree no more than $6{n\choose 2}$, so $G$ can be colored in no more than $6{n\choose 2}+1$ colors by Brooks' theorem.

A lower bound of $\chi$ is presented in Max Alekseyev's comment, which can be interpreted as a clique of $G$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The degree of every node is $$\binom{4}{2}\binom{n-4}{2}+\binom{4}{3}\binom{n-4}{1}=(3n-11)(n-4).$$ $\endgroup$ – RobPratt Jun 16 at 1:55
  • $\begingroup$ @RobPratt Oh yes you are right, thanks! $\endgroup$ – ArtOfProblemSolving Jun 16 at 12:33

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.