Skip to main content
1 of 2
Sfarla
  • 307
  • 1
  • 4

On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.

We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we have:

  • $|A_i|=t$ for every $A_i\in W$;
  • $|A_i\cap A_j|\leq 1$ for every $A_i, A_j\in W$ with $i\neq j$;
  • $W$ is maximal with respect to $\subset$.

(Sorry for the name quasi-partition but I didn't know how to name this kind of sets)

I would like to determine (or to give an upper bound) the number

$$a_{n,t}:= \max_{W \;q-p\; of \; A } |W| $$

Note: This problem should be equal to finding the clique number $\omega(G)$ of the graph $G$, where $G$ is the generalized Kneser graph $KG(n,t,1)$. An upper bound could be given by its chromatic number $\chi(G)$. If $n=(t-1)s+r$ with $0\leq t < t-1$
$$ \chi(G) = (t-1)\dbinom{s}{2}+rs,$$ (see http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190090204/abstract, but unfortunately I don't have the permission to get it) but I don't think it is an optimal bound.

Could anybody help me? Thanks in advance for every comment.

Sfarla
  • 307
  • 1
  • 4